数据结构_实验三_栈和队列及其应用

实验编号：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\、h\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\、h\//输出菜单 void Muse() { } //创建栈

Status InitStack(SqStack &S) {

cout << \请选择功能：\cout << \ 1、入栈\cout << \ 2、出栈\cout << \ 3、判栈空\cout << \ 4、返回栈顶部数据\cout << \ 5、栈长\cout << \ 0、退出系统\cout << \您得选择就是：\

S、base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S、base) exit(ERROR); S、top = S、base;

S、stacksize = STACK_INIT_SIZE; return OK;

}

//得到顶部数据

Status GetTop(SqStack S, SElemType &e) { if (S、base == S、top) return ERROR; e = *(S、top - 1); return OK;

} //入栈

Status Push(SqStack &S, SElemType &e) { if (S、top - S、base >= STACK_INIT_SIZE) {

S、base = (SElemType *)realloc(S、STACKINCREMENT) * sizeof(SElemType)); if (!S、base) exit(ERROR); S、top = S、base + S、stacksize; S、stacksize += STACKINCREMENT;

}

*S、top++ = e; return OK;

} //出栈

Status Pop(SqStack &S, SElemType &e) {

base, (STACK_INIT_SIZE +