第3章栈与队列

栈和队列是两种存取受到限制的线性数据结构。本章介绍栈和队列的定义、存储结构
和基本操作,并以算术表达式求值为例介绍栈和队列的应用。

3.栈的基本概念
1 

3.1 
栈的定义与特点
1.
栈(stacks)是限定在一端插入和删除的线性表。允许插入和删除的一端称为栈顶
(top),另一端称为栈底(botom )。栈的修改是按照后进先出
(t,的原则进行的,因此栈又称为后进先出

lastinfirstouLIFO)
(或先进后出)1所示。

线性表。栈的基本结构如图3.

3.2 
栈的两类存储结构
1.
与线性表类似,栈也有顺序存储结构和链式存储结构。

1.顺序栈
顺序栈,即栈的顺序存储结构。顺序栈利用一组地址连续
的存储单元依次存储由栈底到栈顶的数据元素,同时附加top指
针指示栈顶元素在顺序栈中的位置。顺序栈结构如图3.

2所示。
1 栈的基本结构

利用栈底位置相对不变这个特点,两个顺序栈可以共享一图3.
个一维数据空间来互补余缺。其实现方法是将两个栈的栈底分
设在一维数据空间的两端,并让它们各自的栈顶由两端向中间延伸,3所示。这样,

如图3.
两栈可以相互协调空间的使用,只有当整个数据空间被这两栈占满时才发生上溢。因此,上
溢出现的频率比将这个一维数据空间一分为二给两个栈使用时要小。


图3.

2 顺序栈示意图


图3.

3 两个栈共享空间示意图


72 
2.链栈
链栈,即栈的链式存储结构。链栈动态分配元素存储空间,链栈无栈满问题,操作时无
须考虑上溢问题,而且克服了顺序栈操作带来的数据元素移动问题。
由于栈的操作仅限制在栈顶进行,因此不必设置头结点,头指针即栈顶指针。链栈结构
如图3.4所示。
图3.4 链栈示意图
3.2 顺序栈的算法实现
遵照和第2章类似的思路,在设计栈的结构及功能时,仍需要遵循面向对象的类的设计
方法。首先,根据上面顺序栈的结构设计对应的类。
由于顺序栈本质上仍使用顺序表的存储结构,因此不妨直接继承第2章中已经定义的
顺序表类,在此基础上添加或修改函数实现栈的不同功能。
同时,将顺序表的末端作为栈顶,如果需要栈顶元素,则直接将顺序表中的最后一个元
素返回。在后续的功能补充当中,时刻注意顺序栈作为顺序表的派生类,拥有顺序表的所有
属性和方法,并可调用顺序表的公有属性与方法。如果代码中出现读者未见过的函数,不妨
回顾顺序表的定义进行检查。
顺序栈类定义如下。 
1. #include "../Vector/Vector.h" 
2. 
3. //以顺序表为基类,派生出栈模板类
4. template <typename T> 
5. class Stack : public Vector<T> 
6. { //将顺序表的末端作为栈顶
7. public: 
8. //查看栈顶元素
9. T top() { return this->get_elem(this->size()); } 
10. }; 
11. //size()、empty()功能与原顺序表相同,直接继承
3.2.1 顺序栈的建立和顺序栈入栈
1.算法功能 
构造一个空栈s,插入元素作为新的栈顶元素,实现栈的建立。
2.算法思路
顺序栈入栈时栈顶指针top先增1,再将新元素按top指示位置插入。注意,若栈满时
再进栈,顺序表将进行扩容,避免了溢出错误。

73 
3.实例描述
建立一个顺序栈,依次将1、2、3、4顺序进栈,建栈过程如图3.5所示。
图3.5 顺序栈建立和元素入栈过程
4.参考程序
类中的相关函数如下。 
1. public: 
2. //入栈即将新元素插入顺序表末端
3. void push(T const &e) { this->insert(e); } 
定义文件中的主程序如下。 
1. #include <iostream> 
2. #include "Stack.h" 
3. 
4. using namespace std; 
5. 
6. void create_Stack(Stack<int>&s) 
7. { 
8. int e; 
9. cout <<"请输入数据(以Ctrl+Z 结束输入):\n"; 
10. while (cin >>e) s.push(e);

74 
11. cin.clear(); //更改cin 的状态标识符
12. rewind(stdin); //清空输入缓存区
13. } 
14. 
15. int main() 
16. { 
17. Stack<int>stk; 
18. create_Stack(stk); 
19. 
20. return 0; 
21. } 
5.运行结果
依次输入数据1、2、3、4,按Ctrl+Z组合键结束输入,建立顺序栈和元素入栈的过程如
图3.6所示。
图3.6 建立顺序栈和元素入栈过程
3.2.2 顺序栈出栈
1.算法功能 
输出已知的顺序栈中的元素。
2.算法思路
顺序栈出栈时,按栈顶指针top指示位置输出元素,并将栈顶指针top减1。当栈为空
时,则出栈结束。
3.实例描述
将顺序栈s={1,2,3,4,5,6}中的元素逐个出栈,直到栈空,如图3.7所示。
4.参考程序
类中的相关函数如下。 
1. public: 
2. //出栈即删除末端元素并返回其值
3. T pop() { return this->remove(this->size()); } 
定义文件中增添的相关函数和主函数修改如下。 
1. void print_Stack(Stack<int>&s) { 
2. cout <<"清空并输出,栈内共有" <<s.size() <<"个元素:\n"; 
3. while (!s.empty()) cout <<s.pop() <<' '; 
4. cout <<endl; 
5. } 
6. 
7. int main() { 
8. Stack<int>stk;

75 
9. create_Stack(stk); 
10. print_Stack(stk); 
11. 
12. return 0; 
13. } 
图3.7 顺序栈出栈过程
5.运行结果
顺序栈s={1,2,3,4,5,6}的元素出栈过程如图3.8所示。
图3.8 顺序栈出栈算法演示

以上介绍的是顺序栈的功能及实现。顺序栈最终的Sh头文件及定义文件结构如

tack.

图3.10 所示。

9和图3.


图3.

9 顺序栈的头文件结构


图3.

10 顺序栈的定义文件结构

另外,链栈的操作是单链表操作的特例,因此链栈的操作易于实现,在此不作赘述。

3.队列的基本概念
3 

3.1 
队列的定义与特点
3.
队列是只允许在一端删除,在另一端插入的线性表。允许删除的一端称为队头

(t), r), 11 所示。队列的修改是按照先进先出
fron允许插入的一端称为队尾(rea如图3.
(的原则进行的。

firstinfirstout,FIFO) 


图3.

11 队列

队列数据结构在日常生活中随处可见。例如,在食堂排队买饭、在超市排队付钱等,遵
守的规则都是先到先服务,这与队列的先进先出特点是一致的。

76 

3.2 
队列的存储结构
3.
1. 
顺序队列
顺序队列,即队列的顺序存储结构,也是利用一组地址连续的存储单元存放队列中的元
素。由于队列中元素的插入和删除是在表的两端进行,因此必须设置队头指针q
和队尾指针q->rear,分别指示当前的队头元素和队尾元素。
>front 

2. 
循环队列
顺序队列会发生溢出现象。队满时再进行入队操作称为“上溢”,而队空时再进行出队
操作称为“下溢”。上溢有两种情况。

一种是真正的溢出,如图3.即队尾指针q->rear和队头指针q->front存

12 所示, 
在如下关系:q->rear-q->front=maxSize,这时队列已满,不再有可供使用的数据
空间。


图3.

12 已满的顺序队列

另一种是假溢出,如图3.即q->rear=maxSize, >rear-q->

13 所示, 但是qfront<maxSize,这时仍有可用的数据空间,只不过队尾指针已经达界限的最大值而无法接
纳入队的数据。假溢出是由于被删除的队列元素所占用的空间无法继续使用造成的。
解决假溢出的方法是将顺序队列设想成一个首尾相接的圆环,称为循环队列,如图3.

14 

所示。


图3.13 顺序队列假溢出图3.

14 循环队列

循环队列中,队空和队满的条件都是q->rear=q->front,因而无法区别队空和队
满。解决这一问题的方法是浪费一个数据空间,将队满的条件改为(q->rear+1)% 
maxSize=q->front,而队空的条件不变。

3. 
链队列
链队列,即队列的链式存储结构。链队列也需要标识队头和队尾的指针。与单链表相
同,为了操作方便,一般使用带有头结点的链队列,并令头指针指向头结点。链队列在进队
时无队满问题,但有队空问题。队空的条件是头指针和尾指针均指向头结点。链队列如

77 

78 
图3.15所示。
图3.15 链队列
3.4 顺序队列的算法实现
首先,进行顺序队列的类设计。
根据上述顺序队列的结构,顺序队列应该和顺序表类似,应该包括最大容量、存储顺序
表元素数组的数组指针等属性,具有类似的构造函数、析构函数以及返回长度、是否为空、是
否为满等函数;同时,也应该包括队头指针和队尾指针这两个顺序表中没有的属性。故此处
的顺序队列没有选择继承顺序表,而是选择了重新独立声明。
顺序队列类定义如下。 
1. #define DEFAULT_CAPACITY 10 
2. 
3. //以顺序表的方式实现队列
4. //因为设计有容量限制,所以未继承可扩展的Vector 
5. template<typename T> 
6. class Queue { 
7. protected: 
8. int head, tail; 
9. int capacity; 
10. T *elem; 
11. 
12. public: 
13. int size() const { return tail -head; } //返回规模大小
14. bool empty() const { return !size(); } //判断是否为空
15. bool full() const { return tail >=capacity -1; } //是否队满
16. 
17. //返回队首元素
18. T front() { return elem[head +1]; } 
19. 
20. //返回队尾元素
21. T rear() { return elem[tail]; } 
22. }; 
需要注意的是,由于队头指针和队尾指针的存在,顺序队列类和顺序表类的定义存在不少
差异,最主要的区别是顺序队列类中没有length属性,因为head和tail指针就可以很好地完成
相应的任务。因此,这里没有采用之前顺序栈类以顺序表类为基类派生定义的方法。在这里
也提醒读者,如果希望继承某个类的特性,应该仔细观察派生类和基类的差别,以防出错。

79 
3.4.1 顺序队列的建立和顺序队列入队
1.算法功能 
用尾插法动态建立顺序队列。
2.算法思路
顺序队列入队时队尾指针先增1,再将新元素按队尾指针指示的位置插入。注意,若队
满时再进队将产生溢出错误。
3.实例描述
初始化顺序队列,并使关键字1、2、3、4、7依次入队,如图3.16所示。
图3.16 顺序队列入队过程图示
4.参考程序
Queue@Vector.h文件类中的相关函数如下。 
1. public: 
2. //构造函数初始化

80 
3. Queue(int c =DEFAULT_CAPACITY) : capacity(c) 
4. { 
5. elem =new T[capacity]; 
6. head =tail =-1; 
7. } 
8. ~Queue() { delete[] elem; } //析构函数释放空间
9. 
10. //入队,即未满时在尾部插入
11. void enqueue(T const &e) { elem[++tail] =e; } 
定义文件中的主程序如下。 
1. #include "Queue@Vector.h" 
2. #include <iostream> 
3. using namespace std; 
4. 
5. void create_Queue(Queue<int>&q) { 
6. int e; 
7. cout <<"请输入数据(以Ctrl+Z 结束输入):\n"; 
8. while (cin >>e) 
9. if (q.full()) cout <<"队列已满!\n"; 
10. else q.enqueue(e); 
11. cin.clear(); //更改cin 的状态标识符
12. rewind(stdin); //清空输入缓存区
13. } 
14. 
15. int main() { 
16. Queue<int>que; 
17. create_Queue(que); 
18. return 0; 
19. } 
需要注意的是,在本章队列的程序中,不同队列的定义文件是通用的,后续的程序中读
者可以通过简单修改头文件引用语句直接使用上述的定义文件程序。
5.运行结果
依次输入元素1、2、3、4、7,按Ctrl+Z组合键结束输入,建立顺序队列,程序执行过程和
结果如图3.17所示。
图3.17 顺序队列建立和元素入队算法演示
3.4.2 顺序队列出队
1.算法功能 
输出已知队列队头的元素。

81 
2.算法思路
出队时队头指针先增1,再将队头指针所指示位置的元素输出。注意,若队空时再出队
将做溢出处理。
3.实例描述
将顺序队列q={1,3,2,7}中的元素逐个出队,直到队空为止,如图3.18所示。
图3.18 顺序队列出队过程
4.参考程序
Queue@Vector.h文件类中的相关函数如下。 
1. public: 
2. //出队,弹出首部并返回值
3. T dequeue() { return elem[++head]; } 
定义文件中增添的相关函数和主函数修改如下。 
1. void print_Queue(Queue<int>&q) { 
2. cout <<"清空并输出,队列内共有" <<q.size() <<"个元素:\n"; 
3. while (!q.empty()) cout <<q.dequeue() <<' '; 
4. cout <<endl; 
5. } 
6. 
7. int main() { 
8. Queue<int>que;

82 
9. create_Queue(que); 
10. print_Queue(que); 
11. 
12. return 0; 
13. } 
5.运行结果
顺序输入元素1、3、2、7,按Ctrl+Z组合键结束输入,建立顺序队列,并逐个输出队头元
素,直到队空,如图3.19所示。
图3.19 顺序队列出队算法演示
以上介绍的是为顺序队列的功能及实现。顺序队列最终的头文件结构和定义文件结构
分别如图3.20和图3.21所示。
图3.20 顺序队列最终的头文件结构

83 
图3.21 顺序队列最终的定义文件结构
3.5 循环队列的算法实现
首先,进行循环队列类的设计。
在之前循环队列存储结构的介绍中,如果从属性上看,它与顺序队列的区别并不大,也
包括队首指针、队尾指针、最大容量和数组指针。
循环队列类定义如下。 
1. #define DEFAULT_CAPACITY 10 
2. 
3. template <typename T> 
4. class Queue 
5. { 
6. protected: 
7. int head, tail; 
8. int capacity; 
9. T *elem; 
10. 
11. public: 
12. int size() const //返回规模大小
13. { 
14. return (tail -head +capacity) %capacity; 
15. } 
16. 
17. //返回队首元素
18. T front() { return elem[(head +1) %capacity]; } 
19. 
20. //返回队尾元素
21. T rear() { return elem[tail]; } 
22. }; 
但是,循环队列的结构中着重强调循环队列的环状结构的初始化以及它的队为空、为满
的判定条件,读者需要注意循环队列与顺序队列的不同。
3.5.1 循环队列的建立和循环队列入队
1.算法功能 
循环队列初始化,并在队尾插入新元素。
2.算法思路
存储队列的数组被当成首尾相接的表处理。

84 
队列初始化:front=rear=0。
队尾指针进1:rear=(rear+1)% maxSize。
队满条件:(rear+1)% maxSize=front。
3.实例描述
建立循环队列{2,8,3,6,9},循环队列入队过程如图3.22所示。其中,图3.22(a)为循
环对列初始化,图3.22(b)是2入队,图3.22(c)为8入队,图3.22(d)是3、6、9依次入队。
图3.22 循环队列入队过程
4.参考程序
CQueue.h文件类中相关的函数如下。 
1. public: 
2. Queue(int c =DEFAULT_CAPACITY) :capacity(c) //构造函数初始化
3. { 
4. elem =new T[capacity]; 
5. head =tail =0; 
6. } 
7. 
8. ~Queue() { delete[] elem; } //析构函数释放空间
9. //判断是否为空
10. bool empty() const { return head ==tail; } 
11. //判断是否为满
12. bool full() const { return head ==(tail +1) %capacity; } 
13. 
14. //入队,即未满时在尾部插入
15. void enqueue(T const &e) 
16. { 
17. if (full()) 
18. return; 
19. tail =(tail +1) %capacity; 
20. elem[tail] =e; 
21. } 
对于定义文件,只需要将3.4.1节顺序队列建立和入队功能中定义文件中引入头文件
的include语句修改为如下语句即可。 
1. #include "CQueue.h" //引入循环队列
5.运行结果
依次输入数据元素2、8、3、6、9,以Ctrl+Z结束输入,建立一个循环队列,如图3.23所示。

85 
图3.23 循环队列入队算法演示
3.5.2 循环队列出队
1.算法功能 
循环队列队头元素出队。
2.算法思路
存储队列的数组被当作首尾相接的表处理。
队头指针进1:front=(front+1)% maxSize。
队空条件:front=rear。
3.实例描述
将循环队列q={4,-2,5,1}中的数据元素依次出队,直到该循环队列为空,如图3.24 
所示。其中,图3.24(a)是原始循环队列,图3.24(b)是队头元素4出队,图3.24(c)是队头元
素-2出队,图3.24(d)是队头元素5、1依次出队。
图3.24 循环队列出队过程
4.参考程序
CQueue.h文件类中相关的函数如下。 
1. public: 
2. //出队,非空时弹出首部并返回值
3. T dequeue() 
4. { 
5. if (empty()) return {}; 
6. head =(head +1) %capacity; 
7. return elem[head]; 
8. } 
对于定义文件,将3.4.2节顺序队列出队功能中定义文件中引入头文件的include语句
修改为以下语句即可。 
1. #include "CQueue.h" //引入循环队列
5.运行结果
依次输入元素4、-2、5、1,以Ctrl+Z结束输入,建立一个循环队列,然后将队列中的元

素出队,直到循环队列为空, 25 所示。

如图3.


图3.

25 循环队列出队算法演示
以上介绍的是循环队列的功能及实现。循环队列最终的头文件结构如图3.

26 所示。


86 
图3.

26 循环队列最终的头文件结构


87 
3.6 链队列的算法实现
观察链队列的结构,不难发现它的结构和之前学习过的双向链表的结构具有很高的相
似性。具体来说,如果将双向链表的头结点和尾结点视为链队列的队头指针和队尾指针,那
么双向链表就能够很好地支持链队列的所有功能。在后续的使用中,双向链表派生出的链
队列也将是本书中默认的队列结构。
因此,链队列类以2.4节中的双向链表为基类进行派生,定义如下。 
1. #include "../List/DuList.h" 
2. 
3. //以双向链表为基类,派生出队列模板类
4. template<typename T> 
5. class Queue : public DuList<T>{ 
6. public: 
7. //链式队列不会存在填满的情况
8. bool full() const { return false; } 
9. 
10. //返回队首元素
11. T front() { return this->first()->data; } 
12. 
13. //返回队尾元素
14. T rear() { return this->last()->data; } 
15. }; 
3.6.1 链队列的建立和链队列入队
1.算法功能 
用双向链表存储队列,进行队列初始化并在队尾插入元素。
2.算法思路
利用双向链表类中已经定义好的插入函数insert_last(),使用尾插法创建、插入队列
元素。
3.实例描述
依次输入数据元素7、-8、3、6、2,建立链队列的过程和用尾插法创建一个包含数据元
素7、-8、3、6、2的双向链表的过程完全一致,在此不再赘述。
4.参考程序
Queue.h文件类中相关的函数如下。 
1. public: 
2. //入队,即在尾部插入
3. void enqueue(T const &e) { this->insert_last(e); } 
对于定义文件,将3.4.1 节顺序队列建立和入队功能中定义文件中引入头文件的

88 
include语句修改为以下语句即可。 
1. #include "Queue.h" //引入链队列
5.运行结果
依次在队尾插入数据7、-8、3、6、2,按Ctrl+Z组合键结束输入,建立链队列和元素入
队的过程如图3.27所示。
图3.27 建立链队列和元素入队的过程
3.6.2 链队列出队
1.算法功能 
链队列中的元素出队。
2.算法思路
利用双向链表类中已经定义好的返回链表首个元素的函数first()以及删除函数
remove(),返回并删除链表中的首个元素。
3.实例描述
将链队列{-2,3,5,1,-3}中的数据元素依次出队,直到队空为止,过程类似从头至尾
打印并删除双向链表中的所有元素。
4.参考程序
Queue.h文件类中相关的函数如下。 
1. public: 
2. //出队,弹出队头并返回值
3. T dequeue() { return this->remove(this->first()); } 
对于定义文件,将3.4.2节顺序队列出队功能中定义文件中引入头文件的include语句
修改为以下语句即可。 
1. #include "Queue.h" //引入链队列
5.运行结果
依次输入元素-2、3、5、1、-3,按Ctrl+Z组合键结束输入,建立链队列,然后将队列中
的元素出队,直到队空,如图3.28所示。
图3.28 链队列出队算法演示
以上介绍的是链队列的功能及实现。链队列最终的头文件结构如图3.29所示。

图3.

29 链队列最终的头文件结构

3.栈和队列的应用———算术表达式的转化和求值
7 

1. 
算法功能
算术表达式的表示方法有中缀表达式(x)、前缀表达式(px)和后缀表达式

infirefi(postfix)3种。这里的前、中、后是针对运算符和操作数放置的位置而言的。
中缀表达式是将运算符(operator)写在两个操作数(operand)之间。例如,
A 
+B, 

A+B/(C-D)。
前缀表达式是把运算符写在两个操作数之前。例如,+AB,+A/B-CD 
。
后缀表达式是把运算符写在两个操作数之后。例如,AB+,ABCD-/+。
表达式的转化可以分为中缀转前缀和中缀转后缀,其转换的方法非常类似,只需要在满
足运算符的优先级(priority)的前提下,注意把运算符放在操作数之前或者之后。中缀表达
式A+(B-C×D)/
E 
的转化过程见表3.

1。

表3.1 
中缀表达式A+(B-C×D)/
E 
的转化过程

步骤说明前缀表达式后缀表达式
1 乘法转换A+(B-×CD)/
E 
A+(BCD×)/
E 
2 减法转换A+(-B×CD)/
E 
A+(BCD×-)/
E 
3 除法转换A+/(-B×CD)
E 
A+(BCD×-)E/ 
4 加法转换+A/(-B×CD)
E A 
(BCD×-)E/+ 
5 去括号+A/-B×CDE 
ABCD×-E/+ 

89 


前缀和后缀表达式本质上是将运算顺序用表达式的排列顺序呈现出来,后缀表达式中
越靠前的运算符越优先运算,而前缀表达式中恰好相反。这样一来就省去了括号,也不需要
预先定义运算符的优先顺序,同时对于计算机来说这是一个更加容易处理的方式。由于后
缀表达式比前缀表达式用得普遍,本算法着重介绍算术表达式的中缀表达式如何转换成后
缀表达式,并利用后缀表达式求值。

2. 
算法思路
1)中缀表达式转后缀表达式

如果将中缀表达式分为操作数和运算符两个部分,转换前后操作数的顺序显然是不变
的,因此不妨将所有操作数视为一个队列,先进队的先输出,这样就能保证顺序不改变;而运
算符的顺序则取决于它的优先级,可以将所有运算符用栈来存放,保证栈顶运算符优先级最
高,如果新运算符优先级小于栈顶元素时,就输出栈顶运算符,直到新元素可以入栈为止,这
样就能使运算符按照优先级输出。

为输入输出方便,这里用井号“#”记作表达式的结束符;同时为了算法简洁,在表达式
的最左边也虚设一个#构成整个表达式的一对括号。

此时算法的具体规则如下。

(1)若导入的是操作数,则直接输出到队列。
(2)若当前运算符的优先级高于栈顶运算符的优先级,则入栈。
(3)若当前运算符的优先级低于栈顶运算符的优先级,则栈顶运算符出栈,并输出到队
列,当前运算符再与新的栈顶运算符比较。
(4)若当前运算符的优先级等于栈顶运算符,且栈顶运算符为左圆括号,当前运算符为
右圆括号,则栈顶运算符出栈,继续读下一符号。
(5)若当前运算符的优先级等于栈顶运算符,且栈顶运算符为#,当前运算符也为#, 
则栈顶运算符出栈,输出队列中的数值即可。
运算符的优先级如表3.2所示,其中θ1 为栈顶运算符,

θ2 为当前运算符。

表3.运算符的优先级

2 

θ2 
θ1 + 
-
× / 
( ) 
# 
+ > > < < < > > 
-> > < < < > > 
× > > > > < > > 
/ > > > > < > > 
( < < < < < = 
) > > > > > > 
# < < < < < = 

2)后缀表达式的运算
后缀表达式中所有的运算符的运算都是以它之前紧邻的两个操作数进行的,因此,如果
顺序读取表达式中的元素,将表达式中的操作数依次顺序存放在栈里,那么若遇到运算符, 

90