实验四
实验名称 栈和队列及其应用 实验性质 设计性 实验学时数 4学时
一、实验目的
1．掌握栈与队列的抽象数据类型描述及特点。
2．掌握栈和队列的顺序和链式存储结构与基本算法实现。
3．掌握栈和队列在实际问题中的应用和基本编程技巧。
二、实验内容
1. 栈和队列在不同存储结构上进行插入、删除等操作的算法。
2. 通过栈或队列解决现实中的一些问题。
三、
实
验
过
程
1、实验题目
[问题描述]
以下题目根据自己兴趣和能力可选作一道作为实验题目：
（1）根据栈的数据结构，建立一个顺序栈和链栈并实现对其基本操作；
（2）根据队列的数据结构，建立一个循环队列和链队并实现对其基本操作；
（3）根据教材4.3.3节介绍的思想，设计并实现一个对简化表达式求值的系统
（4）银行业务队列简单模拟。设某银行有A、B两个业务窗口，其中A窗口的处理速度是B窗口的2倍，给定到达银行的顾客序号，请按业务完成的顺序输出顾客序列（假设奇数编号到A窗口办理，偶数编号到B窗口办理，不同窗口同时处理完2个顾客，A窗口优先输出）。
[基本要求]
（1）按实验内容编写完整的程序，并上机验证。
（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。
2、源程序
#include
#include
#define Stack_Size 100
#define StackElementType int
#define TRUE 1 #define FALSE 0
typedef struct //顺序栈
{
StackElementType elem[Stack_Size];
int top;
}SeqStack;
typedef struct node //链栈
{
StackElementType data;
班级：______________________ 姓名：_____________________ 学号：___________________
第三章 栈和队列
一．单项选择题
1.栈的特点是（ ） ，队列的特点是（ ）。
A 先进先出 B 先进后出
2 栈和队列的共同特点是（ ）。
A 都是先进后出 B 都是先进先出
C 只允许在端点处插入和删除元素 D 没有共同点
3 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）。
A edcba B decba C dceab D abcde
4 若已知一个栈的进栈序列是1,2,3，、、、，n，其输出序列为p1,p2,p3,、、、，pn,若p1=n，则pi(1<=i
A i B n=i C n-i+1 D 不确定
5 若已知一个栈的进栈序列是1,2,3，、、、，n，其输出序列为p1,p2,p3,、、、，pn，若pn=n，则pi(1<=i
A i B n=i C n-i+1 D 不确定
6 若已知一个栈的进序列式1,2,3，、、、，n，其输出序列为p1,p2,p3,、、、，pn，则p1=3,则p2为（ ）。
A 可能是2 B 不一定是2 C 可能是1 D 一定时1
7 若已知一个栈的进栈序列是p1,p2,p3,、、、，pn，输出序列是 1,2,3、、、，n，若p3=1，则p1为（ ）。
A 可能是2 B 一定是2 C 不可能是2 D不可能是3
《数据结构（C语言版 第2版）》（严蔚敏 著）
第三章练习题答案
第3章 栈和队列
1．选择题
（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。
A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1
答案：C
解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。
（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
A．i B．n-i C．n-i+1 D．不确定
答案：C
解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n
答案：D
解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。
（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。
A．x=top->data;top=top->link； B．top=top->link;x=top->link；
单元3 拓展训练参考答案
一、单项选择题
1．由两个栈共享一个向量空间的好处是（ B ）。
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
2．若栈采用顺序存储方式存储，现两栈共享空间V[1...m]，top[i]代表第i个
栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B）。
A．|top[2]-top[1]|==0 B．top[1]+1==top[2]
C．top[1]+top[2]==m D．top[1]==top[2]
3．栈在（D）中应用。
A．递归调用 B．子程序调用 C．表达式求值 D．A，B，C
4．设计一个判别表达式中左、右括号是否配对出现的算法，采用（D）数据
结构最佳。
A．线性表的顺序存储结构 B．队列
C．线性表的链式存储结构 D．栈
5．若数组s[0...n-1]为两个栈s1和s2的共用存储空间，且仅当s[0...n-1]全满
时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2
的栈顶指针的初值分别为（C）。
A．1和n+1 B．1和n/2 C．-1和n D．-1和n+1
6．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。
若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，
则当前存于队列中的元素个数为（B）。
A．(rear-front-1)%n B．(rear-front)%n
C．(front-rear+1)%n D．(rear-front+n)%n
7．假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前
一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的
前提下，队列满的判定条件为（D）。
A．rear==front B．(front+1)%n==rear
