一、实验目的和要求
(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。
二、实验环境和方法
实验方法：
（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。
（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
（三）根据实验内容，编译程序。 实验环境：Windows xp Visual C++6.0
三、实验内容及过程描述
实验步骤：
① 进入Visual C++ 6.0集成环境。 ② 输入自己编好的程序。
③ 检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有错，及时改正。
④ 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 ⑤ 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确，应运行多次，分别检查在不同情况下结果是否正确。
实验内容：编译以下题目的程序并调试运行。
1）、编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出出栈序列；
（6）判断栈s是否非空；
（7）释放栈。 图3.1 Proj3_1 工程组成
本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
main InitStack DestroyStack StackEmpty PusPop GetTo 图3.2 Proj3_1工程的程序结构图
其中包含如下函数：
InitStack(SqStack *&s) //初始化栈S DestroyStack(SqStack *&s) //销毁栈s StackEmpty(SqStack *s) //判断栈空 Push(SqStack *&s,ElemType e) //进栈 Pop(SqStack *&s,ElemType &e) //出栈 GetTop(SqStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-1.cpp #include
ElemType data[MaxSize]; int top; //栈顶指针 } SqStack;
void InitStack(SqStack *&s) //初始化栈S { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; //栈顶指针置为-1 }
void DestroyStack(SqStack *&s) //销毁栈s { free(s); }
bool StackEmpty(SqStack *s) //判断栈空 { return(s->top==-1); }
bool Push(SqStack *&s,ElemType e) //进栈
{ if (s->top==MaxSize-1) //栈满的情况，即栈上溢出 return false; s->top++; //栈顶指针增1 s->data[s->top]=e; //元素e放在栈顶指针处 return true; }
bool Pop(SqStack *&s,ElemType &e) //出栈 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; //取栈顶指针元素的元素 s->top--; //栈顶指针减1 return true; }
bool GetTop(SqStack *s,ElemType &e) //取栈顶元素 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; //取栈顶指针元素的元素 return true; }