广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列 

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列

栈和队列

§3.1 栈

栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。

出栈 入栈 栈的特点：后进先出（Last In First Out），简称：LIFO。

栈顶 an ……

栈的表示和实现 a1 栈底 和线性表类似，栈也有两种存储结构。 a2 （1）．顺序栈

顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。

采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。

在一个程序中，常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。

所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。 栈1 栈2

栈1底 栈1顶 栈2顶 栈2底

（2）．链栈

采用链式存储结构的栈简称链栈。

对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。

【练习】 回文串识别

输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：

ten animals I slam in a net. （我将十只动物装在网里） 输入：一字符串 输出：Yes或No

1 / 12

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列 §3.2 队列

队列（queue）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。 队列的特点：先进先出（|First In First Out），简称：FIFO。

出队列 出队列

a1 a2 a3 …… an

队头 队尾

队列的表示和实现

和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。

在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。

队头

队尾

【例3.2.1】逐行打印二项展开式 (a + b)i 的系数： 杨辉三角形 (Pascal’s triangle)

1 1 i = 1

1 2 1 2

1 5 5 1 3

1 4 6 4 1 4 1 5 10 10 5 1 5

1 6 15 20 15 6 1 6

要求：采用队列实现！

输入： n ——层数（n<50）25 输出：如上图的数字阵列 【算法思路】

分析第 i 行元素与第 i+1行元素的关系

目的是从前一行的数据可以计算下一行的数据 从第 i 行数据计算并存放第 i+1 行数据

2 / 12

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列

从数据结构上，可设计一个足够长的一维数组，以实现上述算法。

【练习】根据上述思路分析，用队列的方法完成例3.2.1。 【练习】再用二维数组，用其它方法完成例3.2.1。

【练习】侦察兵队列

有一个侦察班，由11人组成，其中6名是老侦察员，5名是新侦察员。一次执勤要穿越敌人的一道封锁线。根据当时的情况，队伍只能单线纵向排列，且前面第一、二人越过后，第三个人要返回报告情况，该侦察员随后编到队伍的末尾。接着第四、五人越过，第六人报告并排到末尾。依此类推。最后三人一齐顺次过去。越过封锁线后，队伍便形成老、新交替的队形。请问，穿越前队伍该怎样排？ 要求：采用队列实现！

输出：O表示老队员，Y表示新队员

【练习】倒水问题 [问题描述]

有三个分别装有a升水、b升水和c升水的量筒（c>b>a>0，且b与a互质）, 如果c筒装满水，a与b均为空筒，三个筒相互倒水且不准把水倒往三个筒之外，一个往另一个筒倒水记为一次倒水。问是否能量出d升水(c>d>0)，若能，请求出最少的倒水次数使它能倒出容量为d的水的方案。

3 / 12

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列

[输入格式]

数据存放在当前目录下的文本文件“water.in”中。

文件中以一行的形式存放四个正整数，分别a、b、c、d的值。 [输出格式]

答案输出到当前目录下的文本文件“water.out”中。 第一次行是最少的倒水次数Q，第二起的Q行是每次例水时量简的水量，依次为a、b、c （输入与输出数据中同一行相邻两个数之间用空格区分。） [输入输出举例] water.in

3 7 10 5 water.out

10 9

0 0 10 0 0 10 3 0 7 0 7 3 0 3 7 3 4 3 3 3 4 0 4 6 0 6 4 3 1 6 3 6 1 0 1 9 2 7 1 1 0 9 2 0 8 1 7 2 0 2 8 3 5 2 3 2 5 （仅有第二组才是最优的一个解。）

§3.3 栈的应用实例

§3.3.1 中缀表达式和后缀表达式 对于高级语言程序中的表达式，在编译时求解用栈来实现。任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。

运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。求值时，一般会有运算符号的优先权和结合权问题。例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。

4 / 12

广东省汕头市金山中学高中信息技术信息学竞赛班数据结构专项培训教程03栈和队列 而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。 下表是中缀表达式所对应的后缀表达式： 中缀表达式 A + B * C B * (D-C) + A 40.+ (10.-8.) * 2. -16. / 8. 后缀表达式 ABC * + BDC-*A+ 40.10.8.-2. * + 16. 8. / -

(一)、将中缀表达式转换成后缀表达式

在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。

运算符 优先级 ^ (乘方) 3 * , / 2 + , - 1 【例3.3.1】将中缀表达式转换成后缀表达式。 输入： 中缀表达式，如： B * (D-C) + A 输出： 后缀表达式，如： BDC-*A+ 【算法思想】

设立一个栈来实现中缀表达式变后缀表达式。

设中缀表达式在字符数组E中，E的末尾再加‘#’作为结束符，将转成后缀表达式，存于字符串A中。

对E中表达式自左向右扫描，遇数直接送到A中，若遇

扫描E 栈S 转换至A

到运算符就考虑进栈，进栈的原则是保持栈顶的运算符

B * B

优先级最高。即若欲进栈的算符是 ‘( ’或欲进栈的运

* * ( B

算符优先级大于栈顶运算符的优先级，则将算符入栈，

( * ( B

否则从栈中退出算符送至A中，直至欲进栈的算符优先

D * ( - BD 级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。

- * ( - BD 若遇到‘)’时，将栈中算符退出送入A中，直至退出‘( ’

C * BDC 为止。若遇表达式结束符‘#’，则依次退出栈中算符送

) + BDC- 入A中。

+ + BDC-* 根据上述算法，将中缀表达式B * (D-C) + A转换成后

A BDC-*A 缀表达式BDC-*A+ 的过程图3_1所示。

# BDC-*A+

图3_1

【参考程序段】

const m=100;

var E , A , S : array [1..m] of char; { E中为中缀式，A中为后缀式，S为栈} i , j , t : integer; procedure postexp;

5 / 12