实验编号：3 四川师大《数据结构》实验报告 2016年10月29日
实验三 栈和队列及其应用_
一．实验目的及要求
（1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活
运用它们；
（2） 本实验训练的要点是“栈”的观点及其典型用法；
（3） 掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化
方法。
二．实验内容
（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈
等）；
（2） 应用栈的基本操作，实现数制转换（任意进制）；
（3） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队
列、出队列）；
（4） 利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5） 利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件
（1） （2）
PC机
Dev C++ ,Visual C++, VS2010等
四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）
（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存：
? 代码部分：
//Main.cpp:
#include\int main() {
SqStack S; SElemType e;
int elect=1; InitStack(S);
cout << \已经创建一个存放字符型的栈\while (elect) {
Muse(); cin >> elect; cout << endl; switch (elect) { case 1:
cout << \cin >> e; Push(S, e); break;
case 2:
if(Pop(S, e))
{cout << e <<\else{cout<<\break;
case 3:
if (StackEmpty(S)) { } else { } break;
cout << \栈未空 \ << endl; cout << \栈空 \ << endl;
}
}
case 4:
GetTop(S, e);
cout << \ break;
case 5:
StackLength(S); break;
case 0:break; }
DestroyStack(S); return OK;
//SStack.cpp:
#include\//输出菜单 void Muse() { } //创建栈
Status InitStack(SqStack &S) {
cout << \请选择功能：\cout << \ 1.入栈\cout << \ 2.出栈\cout << \ 3.判栈空\cout << \ 4.返回栈顶部数据\cout << \ 5.栈长\cout << \ 0.退出系统\cout << \你的选择是：\