第3章 栈和队列
50多年前,与同学相约去北京郊区上方山云水洞旅游。当时景区尚未开发,我们拿着
从老乡那里买来的火炬就进了云水洞。为不致迷路,按照当地老乡的嘱咐,我们一路走,一
路在洞壁上、地上做标记,最后依靠这些标记退出洞来。这些标记记忆了回退的路径,实际
上就是一个栈,回退时最先看到的是最后做的标记。
再看日常生活中其他的例子。如银行取款,一进门就需要拿一个号,然后等待叫号。这
就是队列,银行里办理业务至少有5个队列:个人业务、对公业务、VIP、理财金和外币业务。
基本上都是先来先服务。
不要看栈和队列简单,在计算机应用系统中应用极多。Windows操作系统中就用到了
9000多个栈。而且栈与队列都是顺序存取结构,比向量更容易使用。就像结构化编程相对
于普通编程,具有更加优良的程序设计风格。
3.1 栈
栈、队列和双端队列是特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则
较线性表有更多的限制,故又称它们为运算受限的线性表,或限制了存取点的线性表。
3.1.1 栈的概念
1.栈的定义
栈(Stack)是只允许在表的一端进行插入和删除的线性表。允许插入和删除的一端称
图3-1 栈的示意图
为栈顶(top),而不允许插入和删除的另一端称为栈底
(bottom)。当栈中没有任何元素时则成为空栈。
2.栈的后进先出特性
设给定栈S=(a1,a2,…,an),则称最后加入栈中的
元素an 为栈顶。栈中按a1,a2,…,an 的顺序进栈。而
退栈的顺序反过来,an 先退出,然后an-1才能退出,最后
退出a1。换句话说,后进者先出。因此,栈又称为后进
先出(LastInFirstOut,LIFO)的线性表。参看图3-1。
3.栈的主要操作 
(1) void Stack ( Stack& S ); 
先决条件:无。
操作结果:为栈S 分配存储空间,并对各数据成员赋初值。 
(2) bool Push ( Stack& S, SElemType x );

79 
先决条件:栈S 已存在且未满。
操作结果:新元素x 进栈S 并成为新的栈顶。 
(3) bool Pop ( Stack& S, SElemType & x ); 
先决条件:栈S 已存在且栈非空。
操作结果:若栈S 空,则函数返回false,x 不可用;否则栈S 的栈顶元素退栈,退出元
素由x 返回,函数返回true。 
(4) bool GetTop ( Stack& S, SElemType & x ); 
先决条件:栈S 已存在且栈非空。
操作结果:若栈S 空,则函数返回false,x 不可用;否则由引用型参数x 返回栈顶元素
的值但不退栈,函数返回true。 
(5) bool StackEmpty ( Stack& S ); 
先决条件:栈S 已存在。
操作结果:函数测试栈S 空否。若栈空,则函数返回true,否则函数返回false。 
(6) bool StackFull ( Stack& S ); 
先决条件:栈S 已存在。
操作结果:函数测试栈S 满否。若栈满,则函数返回true,否则函数返回false。 
(7) int StackSize ( Stack& S ); 
先决条件:栈S 已存在。
操作结果:函数返回栈S 的长度,即栈S 中元素个数。
举例说明栈的应用。利用栈实现向量A 中所有元素的原地逆置。算法的设计思路是: 
若设向量A 中数据原来的排列是{a1,a2,…,an },执行此算法时,把向量中的元素依次进
栈。再从栈S 中依次退栈,存入向量A,从而使得A 中元素的排列变成{an ,an-1,…,a1}。
所谓“原地”是指逆转后的结果仍占用原来的空间。参看程序3-1。
程序3-1 向量A 中所有元素逆置的算法(存放于prg3-1.cpp) 
#include "SeqStack.cpp" 
void Reverse ( SElemType A[], int n ) { 
Stack S; InitStack(S); int i; 
for ( i = 1; i <= n; i++ ) Push (S, A[i-1]); 
while ( !StackEmpty(S) ) Pop (S, A[i-1]); 
} 
想想看 为何栈元素的数据类型要用SElemType定义? 在何处声明? 
3.1.2 顺序栈
顺序栈是栈的顺序存储表示。实际上,顺序栈是指利用一块连续的存储单元作为栈元
素的存储空间,只不过在C语言中是借用一维数组实现而已。

80 
1.顺序栈的结构定义
在顺序栈中设置一个一维数组elem 存放栈的元素,同时附设指针top指示栈顶元素的
实际位置。在C语言中,栈元素是从elem[0]开始存放的。如图3-2所示。
图3-2 顺序栈的示意图
顺序栈的静态存储结构定义如程序3-2所示。
程序3-2 顺序栈的静态存储结构 
#define maxSize 100 
typedef int SElemType; //栈元素数据类型
typedef struct { 
SElemType elem[maxSize]; 
int top; 
} SeqStack; 
顺序栈的静态存储结构需要预先定义或申请栈的存储空间,也就是说栈空间的容量有
限且一旦装满不能扩充。因此在顺序栈中,当一个元素进栈之前,需要判断是否栈满(栈空
间中没有空闲单元),若栈满,则元素进栈会发生上溢现象。特别需要注意的是栈空情形。
因为向量下标从0开始,栈空时应该S.top<0,因此空栈时栈顶指针S.top== -1。
因为在解决应用问题的系统中往往不能精确估计所需栈容量的大小,需要设置足够大
的空间。如果程序执行过程中发现上溢,系统就会报错而导致程序停止运行。因此,应采用
动态存储分配方式来定义顺序栈,一旦栈满可以自行扩充,避免上溢现象。
顺序栈的动态存储结构定义如程序3-3所示。
程序3-3 顺序栈的动态存储结构(存放于SeqStack.h) 
#include<stdio.h> 
#include <stdlib.h> 
#define initSize 20 //栈空间初始大小
typedef int SElemType; //栈元素数据类型
typedef struct { //顺序栈的结构定义 
SElemType *elem; //栈元素存储数组 
int maxSize; //栈空间最大容量及栈顶指针(下标) 
int top; 
} SeqStack; 
2.顺序栈主要操作的实现
(1)初始化。程序3-4给出动态顺序栈的初始化算法。算法首先按initSize大小为顺
序栈动态分配存储空间,首地址为S.elem,并以initSize作为最初的S.maxSize。最后,置栈
的初始状态为空(top= -1)。top指示栈顶,即最后加入元素的存储位置。

81 
程序3-4 动态顺序栈的初始化(存放于SeqStack.cpp) 
#include "SeqStack.h" 
void initStack ( SeqStack& S ) { 
//建立一个最大尺寸为initSize 的空栈, 若分配不成功则错误处理 
//创建栈空间 
S.elem = ( SElemType* ) malloc ( initSize*sizeof ( SElemType ) ); 
if ( S.elem == NULL ) { printf ( "存储分配失败!\n" ); exit(1); } 
S.maxSize = initSize; S.top = -1; 
}
(2)进栈。程序3-5是动态顺序栈的进栈算法。主要步骤如下: 
① 先判断栈是否已满。若栈顶指针top == maxSize-1,说明栈中所有位置均已使
用,栈已满。这时新元素进栈将发生栈溢出,程序转入溢出处理,否则直接执行②。
② 先让栈顶指针top进1,指到当前可加入新元素的位置,再按栈顶指针所指位置将新
元素插入。这个新插入的元素将成为新的栈顶元素。
程序3-5 顺序栈进栈操作的实现(存放于SeqStack.cpp) 
bool Push( SeqStack& S, SElemType x ) { 
//进栈:若栈不满, 则将元素x 插入到该栈的栈顶, 否则溢出处理后再进栈 
if ( stackFull (S) ) { printf ( "栈满!\n" ); return false; } //栈满 
S.elem[++S.top] = x; //栈顶指针先加1, 再进栈 
return true; 
}
顺序栈进栈操作的示例如图3-3所示。栈顶指针指示最后加入元素位置。
图3-3 顺序栈的进栈
(3)退栈。程序3-6是动态顺序栈的退栈算法。主要步骤如下: 
① 先判断是否栈空。若在退栈时发现栈是空的,则退栈操作将执行栈空处理。栈空处
理通常表明使用这个栈的算法结束。若栈不空,执行②。
② 先将位于栈顶的元素取出,再让栈顶指针减1,使栈顶退到次栈顶位置。
程序3-6 顺序栈退栈操作的实现(存放于SeqStack.cpp) 
bool Pop ( SeqStack& S, SElemType& x ) { 
//退栈:若栈不空则函数通过引用参数x 返回栈顶元素的值, 同时栈顶指针退1,函数返回 
//true;否则函数返回false,且x 的值不可引用 
if ( S.top == -1 ) return false; //判栈空否, 若栈空则函数返回false 
x = S.elem[S.top--]; return true; //先保存栈顶的值,再让栈顶指针退1 
}
顺序栈退栈操作的示例如图3-4所示。位于栈顶指针上方的栈空间中即使有元素,它

82 
们也不是栈的元素了。
图3-4 顺序栈的退栈
(4)顺序栈其他操作的实现。参看程序3-7。需要注意的是GetTop操作与Pop操作
的不同。GetTop操作在读取栈顶元素的值时栈顶元素不退栈,因此栈顶指针不会被修改。
程序3-7 顺序栈其他操作的实现(存放于SeqStack.cpp) 
bool getTop ( SeqStack& S, SElemType& x ) { 
//读取栈顶元素的值:若栈不空则函数返回栈顶元素的值且函数返回true,否则函数返回false 
if ( S.top == -1 ) return false; //判栈空否, 若栈空则函数返回false 
x = S.elem[S.top]; return true; //返回栈顶元素的值
}b
ool stackEmpty ( SeqStack& S ) { 
//函数测试栈S 空否。若栈空,则函数返回true,否则函数返回false 
return S.top == -1; 
}b
ool stackFull ( SeqStack& S ) { 
//函数测试栈S 满否。若栈满,则函数返回true,否则函数返回false 
return S.top == S.maxSize-1; 
}i
nt StackSize ( SeqStack& S ) { 
//函数返回栈S 的长度,即栈S 中元素个数 
return S.top+1; 
}; 
void printStack ( SeqStack& S ) { 
//从栈底到栈顶顺序输出栈内元素的值 
for ( int i = 0; i <= S.top; i++ ) 
printf ( "%d ", S.elem[i] ); 
printf ( "\n" ); 
} 
想想看 为何栈操作只有这几个,表的其他一般操作,如Search、Insert、Remove是
否也可以适用于栈? 
(5)栈的扩充。在进栈时首先要判断是否栈已满? 一旦发现栈已满就要做溢出处理。
一种溢出处理的方法是扩充栈的大小。按2×S.maxSize大小申请新的连续存储空间,把原
来存储空间中存放的所有栈元素转移到新的存储空间后释放原来的存储空间,再让S.elem 
指针指示新的存储空间,并修改S.maxSize=2×S.maxSize,从而解决空间溢出的问题。
程序3-8 进栈时的溢出处理(存放于prg3-8.cpp) 
#include "SeqStack.cpp" 
void OverflowProcess ( SeqStack& S ) {

83 
//溢出处理:扩充栈的存储空间 
SElemType *temp = 
( SElemType* ) malloc ( 2*S.maxSize*sizeof ( SElemType ) ); 
if ( temp == NULL ) { printf ( "存储分配失败!\n" ); exit(1); } 
//传送原栈内的数据 
for ( int i = 0; i <= S.top; i++ ) temp[i] = S.elem[i]; 
free ( S.elem ); //删除原数组 
S.maxSize = 2*S.maxSize; S.elem = temp; //数组最大体积增长一倍
}v
oid Push( SeqStack& S, SElemType x ) { 
//进栈操作:若栈不满, 则将元素x 插入到该栈的栈顶, 否则溢出处理后再进栈 
if ( StackFull(S) ) OverflowProcess(S); //栈满则溢出处理 
S.elem[++S.top] = x; //栈顶指针先加1, 再进栈
}; 
因为S.top存放的是数组元素的下标,而不是实际存储地址,当S.elem 数组扩充后,它
还是保持原栈顶的位置,所以没有修改。
想想看 为何扩充栈空间要扩大为原来的2倍,而不是一点点地扩充? 
3.顺序栈主要操作的性能分析
顺序栈是限定了存取位置的线性表,除溢出处理操作外都只能顺序存取,这决定了各主
要操作的性能都良好,设n 是栈最大容量,则各主要操作的性能如表3-1所示。
表3-1 顺序栈各操作的性能比较
操 作 名时间复杂度空间复杂度操 作 名时间复杂度空间复杂度
初始化InitStack O(1) O(1) 读栈顶GetTop O(1) O(1) 
进栈Push O(1) O(1) 判栈空StackEmpty O(1) O(1) 
溢出处理overflowProcess O(n) O(n) 判栈满StackFull O(1) O(1) 
退栈Pop O(1) O(1) 求栈长StackSize O(1) O(1) 
溢出处理需要开辟一个大小为2×S.maxSize的地址连续的附加存储空间,所以该操作
的空间复杂度较高,还要把原来栈中所有元素复制过去,时间复杂度也较高。除这个操作
外,其他操作的时间和空间复杂度都很低。因此,顺序栈是一种高效的存储结构。
4.双栈共享同一栈空间
程序中往往同时存在几个栈,因为各个栈所需的空间在运行中是动态变化着的。如果
给几个栈分配同样大小的空间,可能在实际运行时,有的栈膨胀得快,很快就产生了溢出,而
其他的栈可能此时还有许多空闲的空间。这时就必须调整栈的空间,防止栈的溢出。
当程序同时使用两个栈时,定义一个足够大的栈空间Vector[maxSize],并将两个栈设
为0号栈和1号栈。该空间的两端的外侧分别设为两个栈的栈底,用b[0](= -1)和b[1] 
(= maxSize)指示。让两个栈的栈顶t[0]和t[1]都向中间伸展,直到两个栈的栈顶相遇,才
认为发生了溢出,如图3-5所示。
进栈情形:对于0号栈,每次进栈时栈顶指针t[0]加1,对于1号栈,每次进栈时栈顶指
针是t[1]减1,当两个栈的栈顶指针相遇,即t[0]+1==t[1],才算栈满。
退栈情形:对于0号栈,每次退栈时栈顶指针是t[0]减1,对于1号栈,每次退栈时栈顶

84 
指针是t[1]加1,只有当栈顶指针退到栈底才算栈空。
图3-5 两个栈共享同一存储空间的情形
两栈的大小不是固定不变的。在实际运算过程中,一个栈有可能进栈元素多而体积大
些,另一个则可能小些。两个栈共用一个栈空间,互相调剂,灵活性强。
两个栈共享一个栈空间时主要栈操作的实现如程序3-9所示。
程序3-9 两栈共享同一栈空间时的进栈和退栈操作的实现(存放于prg3-9.cpp) 
#include<stdio.h> 
#include <stdlib.h> 
#define maxSize 20 //栈存储数组的大小
typedef int SElemType 
typedef struct { //双栈的结构定义 
int top[2], bot[2]; //双栈的栈顶指针和栈底指针 
SElemType elem[maxSize]; //栈数组
} DblStack; 
void initStack ( DblStack& S ) { 
//初始化函数:建立一个尺寸为maxSize 的空栈, 若分配不成功则错误处理。 
S.top[0] = S.bot[0] = -1; S.top[1] = S.bot[1] = maxSize; 
}b
ool Push ( DblStack& S, SElemType x, int d ) { //进栈运算 
if ( S.top[0]+1 == S.top[1] ) ) return false; //栈满则返回false,不能进栈 
if ( d == 0 ) S.elem[++S.top[0]] = x; //d = 0:栈顶指针先加1 再进栈 
else S.elem[--S.top[1]] = x; //d = 1:栈顶指针先减1 再进栈 
return true; 
}b
ool Pop ( DblStack& S, SElemType& x, int d ) { 
//函数通过引用参数x 返回退出栈d 的栈顶元素的元素值,前提是栈不为空 
if ( S.top[d] == S.bot[d] ) return false; //第d 个栈栈空,不能退栈 
if ( d == 0 ) x = S.elem[S.top[0]--]; //栈0:先出栈,栈顶指针减1 
else x = S.elem[S.top[1]++]; //栈1:先出栈,栈顶指针加1 
return true; 
}b
ool getTop ( DblStack& S, SElemType& x, int d ) { 
//函数通过引用参数x 返回栈d 的栈顶元素的元素值,前提是栈不为空 
if ( S.top[d] == S.bot[d] ) ) return false; 
x = S.elem[S.top[i]]; 
return true; 
}
算法的调用方式与顺序栈的基本运算类似,只是在参数表中多了一个d,指示操作对象
是哪一个栈:d =0是0号栈,d =1是1号栈。
如果要求更多的栈共享同一个栈空间,使用顺序存储方式,将使得处理十分复杂。在向
其中一个已满的栈中插入一个新元素时,必须向后或向前寻找未满的栈,成块地移动存储,

85 
压缩未满的栈的空间,为要插入元素的栈腾出空间。这导致大量的时间开销,降低了算法的
时间效率。特别是当整个存储空间即将充满时,这个问题更加严重。解决的办法就是采用
链接方式作为栈的存储表示。
3.1.3 链式栈
链式栈是栈的链接存储表示。采用链式栈来表示一个栈,便于结点的插入与删除。在
程序中同时使用多个栈的情况下,用链接表示不仅能够提高效率,还可以达到共享存储空间
的目的。链式栈的示意图可参看图3-6。
图3-6 链式栈
从图3-6可知,链式栈的栈顶指针在链表头结点,但实际的栈顶结点在头结点后面的首
元结点。因此,新结点的插入和栈顶结点的删除都在链表的首元结点,即栈顶进行。
1.链式栈的结构定义
链式栈用单链表作为它的存储表示,其结构定义如程序3-10所示。它使用了一个链表
的头指针来表示一个栈。对于需要同时使用多个栈的情形,只要我们声明一个链表指针向
量,就能同时定义和使用多个链式栈,并且无须在运算时做存储空间的移动。
程序3-10 链式栈的定义(存放于LinkStack.h) 
#include<stdio.h> 
#include <stdlib.h> 
typedef int SElemType; 
typedef struct node { 
SElemType data; 
struct node *link; 
} LinkNode, *LinkList, *LinkStack; 
2.链式栈主要操作的实现
链式栈主要操作的实现如程序3-11所示。对于链表结构,有一点需要注意:只要存储
中还有可分配的空间,就可以申请和分配新的链表结点,使得链表延伸下去,所以理论上讲, 
链式栈没有栈满问题。但是它有栈空问题。
程序3-11 链式栈主要操作的实现(存放于LinkStack.cpp) 
#include "LinkList.h" 
void initStack ( LinkStack& S ) { 
//链式栈初始化:置栈顶指针,即链表头指针为空。 
S = ( LinkNode* ) malloc ( sizeof ( LinkNode )); //创建头结点 
if ( S == NULL ) { printf ( "存储分配失败!\n" ); exit(1); } 
S->link = NULL; //栈顶置空
}; 
bool Push ( LinkStack& S, SElemType x ) { 
//进栈:将元素x 插入到链式栈的栈顶,即链头 
LinkNode *p = ( LinkNode* ) malloc( sizeof( LinkNode )); //创建新结点*p

86 
p->data = x; p->link = S->link; S->link = p; //新结点插入在链头 
return true; 
}b
ool Pop ( LinkStack& S, SElemType& x ) { 
//退栈:若栈空,函数返回false,参数x 的值不可用;若栈不空,则函数返回true,并通过 
//引用参数x 返回被删栈顶元素的值 
if ( S->link == NULL ) return false; //栈空函数返回false 
LinkNode *p = S->link; x = p->data; //存栈顶元素 
S->link = p->link; free (p); //栈顶指针退到次栈顶 
return true; 
}b
ool GetTop ( LinkStack& S, SElemType& x ) { 
//读取栈顶:若栈不空,函数通过引用参数x 返回栈顶元素的值 
if ( S->link == NULL ) return false; //栈空函数返回false 
x = S->link->data; return true; //栈不空则返回true 
}; 
bool stackEmpty ( LinkStack& S ) { 
//判断栈是否为空:若栈空,则函数返回true,否则函数返回false 
return S->link == NULL; 
}i
nt stackSize ( LinkStack& S ) { 
//求栈的长度:计算栈元素个数 
int k = 0; //逐个结点计数 
for ( LinkNode *p = S->link; p != NULL, p = p->link ) k++; 
return k; 
}v
oid printStack ( LinkStack& S ) { 
for ( LinkNode *p = S->link; p != NULL; p = p->link ) 
printf ( "%d ", p->data ); //逐个结点输出 
printf ( "\n" ); 
}v
oid createLinkStack ( LinkStack& S, SElemType A[ ], int n ) { 
//根据数组A[n]建立单链表S,要求S 已存在并置空 
LinkList p; 
for ( int i = 0; i < n; i++ ) { //头插法 
p = ( LinkNode * ) malloc ( sizeof ( LinkNode ) ); 
p->data = A[i]; p->link = S->link; S->link = p; //链入到头结点之后 
} 
} 
3.链式栈主要操作的性能分析
链式栈主要操作的性能分析如表3-2所示,其中n 是链式栈中元素个数。
除栈清空、栈建立和计算栈长度这三个操作需要逐个结点处理,时间复杂度达到O(n) 
以外,其他操作的时间和空间性能都相当好。此外,如果事先无法根据问题要求确定栈空间
大小时,使用链式栈更好些,因为它没有事先估计栈空间大小的困扰,也不需要事先分配一
块足够大的地址连续的存储空间。但是由于每个结点增加了一个链接指针,导致存储密度
较低,如果问题明确要求最省空间,可以优先考虑顺序栈。

87 
表3-2 链式栈各操作性能的比较
操 作 名时间复杂度空间复杂度操 作 名时间复杂度空间复杂度
初始化InitStack O(1) O(1) 读取栈顶GetTop O(1) O(1) 
清空clearStack O(n) O(1) 判栈空StackEmpty O(1) O(1) 
进栈Push O(1) O(1) 计算栈长StackSize O(n) O(1) 
退栈Pop O(1) O(1) 建栈createLinkStack O(n) O(1) 
如果同时使用n 个链式栈,其头指针数组可以用以下方式定义: 
int i, n = 10; 
LinkNode**st = ( LinkNode**) malloc ( n*sizeof (LinkNode *) ); 
for ( i = 0; i < n; i++ ) { 
//创建第i 个链表的头结点 
st[i] = ( LinkNode *) malloc ( sizeof ( LinkNode ) ); 
st[i]->link = NULL; //置空该链表
}
其中,st[i]是表头指针数组中第i 个链表的表头指针,它指示第i 个链表的头结点。
3.1.4 栈的混洗
设给定一个数据元素的序列,通过控制入栈和退栈的时机,可以得到不同的退栈序列, 
这就称为栈的混洗。在用栈辅助解决问题时,需要考虑混洗问题。那么,对于一个有n 个
元素的序列,如果让各元素按照元素的序号1,2,…,n 的顺序进栈,可能的退栈序列有多少
种? 不可能的退栈序列有多少种? 现在我们来进行讨论。
当进栈序列为1和2时,可能的退栈序列有2种:{1,2}和{2,1};当进栈序列为1、2和
3时,可能的退栈序列有5种:{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,2,1}。注意,{3,1, 
2}是不可能的退栈序列。
一般情形又如何呢? 若设进栈序列为1,2,…,n,可能的退栈序列有mn 种,则
当n=0时无整数进栈,m0=1:退栈序列为{}。
当n=1时1个整数进栈,m1=1:退栈序列为{1}。
当n=2时2个整数进栈,m2=2:退栈序列中1在首位,1左侧有0个数,右侧有1个
数,有m0×m1=1种退栈序列为{1,2};退栈序列中1在末位,1左侧有1个数,右侧有0个
数,有m1×m0=1种退栈序列{2,1};总的可能退栈序列有m0×m1+m1×m0=2种。
当n=3时3个整数进栈,m3=5:退栈序列中1在首位,1左侧有0个数,右侧有2个
数,有m0×m2=2种退栈序列{1,2,3}和{1,3,2};退栈序列中1在第2位,1左侧1个数, 
右侧1个数,有m1×m1=1种退栈序列{2,1,3};退栈序列中1在第3位。1左侧2个数,右
侧0个数,有m2×m0=2种退栈序列{2,3,1}和{3,2,1};因此,总的可能退栈序列有m0× 
m2+m1×m1+m2×m0=5种。
当n=4时有4个整数依次进栈,按照上面的方法推理,可能的退栈序列栈m4=m0× 
m3+m1×m2+m2×m1+m3×m0=1×5+1×2+2×1+5×1=14种。它们是{1,2,3, 
4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,3,2},{2,1,3,4},{2,1,4,3},{2,3,1,4},{3,2,

88 
1,4},{2,3,4,1},{2,4,3,1},{3,2,4,1},{3,4,2,1},{4,3,2,1}。
一般地,设有n 个元素按序号1,2,…,n 进栈,轮流让1在退栈序列的第1,第2,…,第
n 位,则可能的退栈序列数为: 
Σn-1 
i=0
mi ×mn-i-1 = 1 n +1Cn 2n = (2n)(2n -1)…(n +2) 
n! 
再看不可能的退栈序列又是什么情况。设对于初始进栈序列1,2,3,…,n,利用栈得到
可能的退栈序列为p1p2…pi…pn ,如果序号i<j<k,且在进栈序列中pi<pj<pk ,即: 
…pi,…,pj,…,pk (pi <pj <pk) 
则: 
…pk ,…,pi,…,pj 
就是不可能的退栈序列。因为pk 在pi 和pj 之后进栈,又先于pi 和pj 退栈,按照栈
的后进先出的特性,pi 压在pj 的下面,理应pj 先出,所以…pk ,…,pi,…,pj …是不可能
的退栈序列。
那么,设一个进栈序列有n 个互不相等的整数,如何求得所有可能的出栈序列? 
考虑采用递归方法求解。算法需要使用一个辅助栈保存生成的出栈序列。假设n=3, 
进栈序列为1、2和3。若进栈标记为I,出栈标记为O,可用如图3-7所示的状态树来表示
进栈与出栈情形。由于进栈操作(I)在任何情况下都应比它右边的出栈操作(O)多,不合理
的情形都被剪枝,所以在状态树中剪枝部分都没有画出来,树中从左向右的状态分别是
IIIOOO(输出321),IIOIOO(输出231),IIOOIO(输出213),IOIIOO(输出132),IOIOIO 
(输出123)。算法的思路就是遍历此状态树,按向左进栈,向右出栈,出栈时输出的原则进
行处理。每个分支代表一个输出序列。
图3-7 表示进/退栈的状态树
程序3-12 求进栈序列的所有退栈序列(存放于prg3-12.cpp) 
#include "SeqStack.cpp" 
#define N 3 
void allOutSTK( int A[], int C[], SeqStack& S, int i, int k, int& count ) { 
//设进栈序列有N 个不同整数,算法参数表中数组C[N]是进栈序列,A[k]是退栈序列,k 
//是A 中当前形成的序列中元素数(初值为0),i 是C 中当时取元素指针(初值为0),S 
//存放已进栈序列,count 用于统计出栈序列个数(初值为0) 
int x, j;

89 
if ( i == N && stackEmpty (S) ) { //i 已取完进栈元素且栈S 空 
//输出当前形成的退栈序列 
for ( j = 0; j < k; j++ ) printf ( "%d ", C[A[j]] ); 
printf ( "\n" ); 
count++; //退栈序列数加1 
} 
if ( i < N ) { //未取完进栈元素,向左一步 
Push ( S, i ); //取进栈元素指针保存 
allOutSTK ( A, C, S, i+1, k, count ); //递归继续形成退栈序列 
Pop ( S, x ); 
} 
if ( !stackEmpty ( S ) ) { //向右 
Pop ( S, x ); A[k] = x; //退栈 
allOutSTK ( A, C, S, i, k+1, count ); //递归继续形成退栈序列 
Push ( S, x ); 
} 
}
图3-8是对进栈序列{1,2,3}执行程序3-11所得到的结果。
图3-8 求进栈序列的所有退栈序列的示例
设进栈序列有n 个元素,算法的时间复杂度为O(n2),空间复杂度为O(n)。
再看一个n=4的进栈/退栈的例子。设一个进栈序列为abcd,可能的退栈序列有14 
种,即abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、cbad、bcda、bdca、cbda、cdba、dcba; 
不可能的退栈序列有4! -14=24-10=10种,原因参看表3-3。
表3-3 不可能的退栈序列
不可能退栈序列不可能的原因
adbc b 先于c 进栈,d 退栈时b 一定压在c 下,不可能b 先于c 退栈
bdac a 先于c 进栈,d 退栈时a 一定压在c 下,不可能a 先于c 退栈
cabd a 先于b 进栈,c 退栈时a 一定压在b 下,不可能a 先于b 退栈
cadb 同上
cdab 同上
dabc 按照a,b,c,d 顺序进栈,d 先退栈,a,b,c 一定还在栈内,且a 压在最下面,b 压
在c 下面,不可能b 先于c 或a 先于b 退栈
dacb a 先于b 进栈,d 退栈时a 一定压在b 下,不可能a 先于b 退栈
dcab 同上

续表 
90 
不可能退栈序列不可能的原因
dbac a 先于c 进栈,d 退栈时a 一定压在c 下,不可能a 先于c 退栈
dbca b 先于c 进栈,d 退栈时b 一定压在c 下,不可能b 先于c 退栈
3.2 队 列
3.2.1 队列的概念
1.队列的定义和特性
队列(Queue)是另一种限定存取位置的线性表。它只允许在表的一端插入,在另一端
删除。允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。参看图3-9。每
次在队尾加入新元素,因此元素加入队列的顺序依次为a1,a2,a3,…,an 。最先进入队列的
元素最先退出队列,如同在铁路车站售票口排队买票一样。队列所具有的这种特性就称为
先进先出FIFO(FirstIn/FirstOut)。
图3-9 队列的示意图
2.队列的主要操作 
(1) 队列的初始化InitQueue ( Queue& Q ); 
先决条件:无。
操作结果:为队列Q 分配存储空间,并对各数据成员赋初值。 
(2) void EnQueue ( Queue& Q, QElemType x ); 
先决条件:队列Q 已存在且未满。
操作结果:新元素x 进队列Q 并成为新的队尾。 
(3) int DeQueue ( Queue& Q, QElemType& x ); 
先决条件:队列Q 已存在且队列Q 非空。
操作结果:若队列Q 空,则函数返回0,x 不可用;否则队列Q 的队头元素退队列,退出
元素由x 返回,函数返回1。 
(4) int GetFront( Queue& Q, QElemType& x ); 
先决条件:队列Q 已存在且队列非空。
操作结果:若队列Q 空,则函数返回0,x 不可用;否则由引用型参数x 返回队列元素
的值但不退队列,函数返回1。

91 
(5) int QueueEmpty( Queue& Q ); 
先决条件:队列Q 已存在。
操作结果:判队列Q 空否。若队列空,则函数返回1,否则函数返回0。 
(6) int QueueFull( Queue& Q ); 
先决条件:队列Q 已存在。
操作结果:判队列Q 满否。若队列满,则函数返回1,否则函数返回0。 
(7) int QueueSize( Queue& Q ); 
先决条件:队列Q 已存在。
操作结果:函数返回队列Q 的长度,即队列Q 中元素个数。
下面看一个例子。给出一个整数序列,判断它是否中心对称。中心对称是指一个整数
序列以位于中间位置的整数为基准两侧的整数完全对称相等。例如,整数序列{1,3,5,3,1} 
或{1,3,5,5,3,1}即为中心对称,而{1,3,5,7,9}就不是中心对称。
我们可以利用一个队列和一个栈来解决此问题。首先把给定的整数序列分别存入栈和
队列,然后依次从栈和队列中退出一个整数,比较出队列的整数和退栈的整数是否相等。若
不相等,则该整数序列不是中心对称;若相等则从队列和栈中再退出一个整数,重复上述的
比较。如果队列和栈同时为空,则说明对应整数全部相等,该整数序列是中心对称。
算法的实现如程序3-13所示。
程序3-13 检测整数序列A 是否中心对称的算法(存放于prg3-13.cpp) 
#include "SeqStack.cpp" 
#include "CircQueue.cpp" 
bool centroSym ( int A[], int n ) { 
//函数判断整数数组A[n]是否中心对称。是则函数返回true,否则函数返回false 
SeqStack S; initStack(S); //定义一个栈S 并初始化 
CircQueue Q; initQueue(Q); //定义一个队列Q 并初始化 
int i, j; 
for ( i = 0; i < n; i++ ) //逐个整数处理 
{ enQueue ( Q, A[i] ); Push ( S, A[i]); } //分别进队列和进栈 
while ( !stackEmpty(S) && !queueEmpty(Q) ) { //当队列和栈不空时 
Pop ( S, i ); deQueue (Q, j ); //分别退出一个整数 
if ( i != j ) return false; //对应整数不等,不是中心对称 
} 
return true; //全部相等,中心对称
}; 
3.2.2 循环队列
1.循环队列的概念
队列的存储表示也有两种方式:一种是基于数组的存储表示,另一种是基于链表的存
储表示。队列的基于数组的存储表示亦称为顺序队列,它是利用了一个一维数组
elem[maxSize]来存放队列元素,并且设置两个指针front和rear,分别指示队列的队头和队
尾位置。

92 
图3-10即为顺序队列操作的示例。maxSize是数组的最大长度。
从图3-10中可以看到,在队列刚建立时,需要首先对它初始化,令front=rear=0。
每当加入一个新元素时,先将新元素添加到rear所指位置,再让队尾指针rear进1。因
而指针rear指示了实际队尾位置的后一位置,即下一元素应当加入的位置。而队头指针
front则不然,它指示真正队头元素所在位置。
如果要退出队头元素,应当首先把front所指位置上的元素值记录下来,再让队头指针
front进1,指示下一队头元素位置,最后把记录下来的元素值返回。
图3-10 顺序队列的初始化、插入和删除的图示
从图3-10中还可以看到,如果队列指针front== rear,队列为空;而当rear == 
maxSize时,队列满,如果再加入新元素,就会产生“溢出”。
但是,这种“溢出”可能是假溢出,因为在数组的前端可能还有空位置。为了能够充分地
使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形表,即把存储队列元
素的表从逻辑上看成一个环,成为循环队列(CircularQueue)。
如图3-11 所示。循环队列的首尾相接,当队头指针front和队尾指针rear进到
maxSize-1后,再前进一个位置就自动到0。这可以利用整数除取余的运算(%)来实现。
队头指针进1: 
front = (front+1) % maxSize; 
队尾指针进1: 
rear = (rear+1) % maxSize; 
图3-11 循环队列的初始化、插入和删除的示意图
循环队列的队头指针和队尾指针初始化时都置为0:front=rear=0。在队尾插入新
元素和删除队头元素时,两个指针都按顺时针方向进1。当它们进到maxSize-1时,并不

93 
表示表的终结,只要有需要,利用%(取模或取余数)运算可以前进到数组的0号位置。
如果循环队列取出元素的速度快于存入元素的速度,队头指针很快追上了队尾指针,一
旦到达front==rear,队列变空。反之,如果队列存入元素的速度快于取出元素的速度, 
队尾指针很快就赶上了队头指针,使得队列变满。为了区别于队空条件,用(rear+1)% 
maxSize==front来判断是否队满,就是说,让rear指到front的前一位置就认为队已满。
此时,因队尾指针指示实际队尾的后一位置,所以在队满时实际空了一个元素位置。如果不
留这个空位置,让队尾指针一直走到这个位置。必然有rear==front,则队空条件和队满
条件就混淆了。除非另加队空/队满标志,否则无从分辨到底是队空,还是队满。
想想看 在循环队列中,最多只能存放maxSize-1个元素。在设计队列时,若估
计队列需要容纳n 个元素,则队列容量至少应设计多大? 
循环队列还有其他可能的实现方式,如: 
(1)使用队头指针front、队尾指针rear加上一个进队/出队的标志tag,可以实现循环
队列。新元素进队列时置tag=1,以rear==front和tag==1作为判断队列是否为满
的条件;元素出队列时置tag=0,以rear==front和tag==0作为判断队列是否为空
的条件。队列的进队列和出队列操作仍然按加1取模来实现。
(2)使用队尾指针rear和队列长度length,也可实现循环队列。
想想看 使用队尾指针rear时队头在何处? 是在rear+1处,还是在rear-length+1 
处? 是否需要用% maxSize处理一下? 
2.循环队列的结构定义
循环队列使用了一个容量为maxSize的元素数组elem,还需要两个指针front和rear, 
这样可定义如程序3-14所示的循环队列的结构。
程序3-14 循环队列的结构定义(存放于CircQueue.h) 
#include <stdio.h> 
#include <stdlib.h> 
typedef char QElemType; 
typedef struct { 
QElemType *elem; //循环队列的存储空间 
int maxSize; //最大存储单元数 
int front, rear; //front 指示队头、rear 指示队尾
} CircQueue; 
队列有许多实际应用,例如,作为系统的输入缓冲区,一旦队列满,系统将产生中断,直
到队列元素取走为止;作为系统的输出缓冲区,一旦队列空,系统将产生输出中断,直到队列
中重新填充入元素为止。
3.循环队列主要操作的实现
循环队列主要操作的实现如程序3-15所示。注意,队头和队尾指针都在同一方向进1, 
不像栈的栈顶指针那样,进栈和退栈是相反的两个方向。
程序3-15 循环队列主要操作的实现(存放于CircQueue.cpp) 
#include "CircQueue.h" 
void initQueue ( CircQueue& Q ) { / / 循 环队列的初始化

94 
Q.elem = (QElemType*)malloc(queSize*sizeof(QElemType)); 
if ( Q.elem == NULL ) { printf ( "存储分配失败!\n" ); exit(1); } 
Q.maxSize = queSize; Q.front = 0; Q.rear = 0; 
}b
ool queueEmpty ( CircQueue& Q ) { // 判 队 空否,队空则返回true 
return Q.front == Q.rear; 
}b
ool queueFull ( CircQueue& Q ) { //判队满否,队满则返回true 
return (Q.rear+1) % Q.maxSize == Q.front; 
}i
nt queueSize ( CircQueue& Q ) { //求队列元素个数 
return (Q.rear-Q.front+Q.maxSize) % Q.maxSize; 
}b
ool enQueue ( CircQueue& Q, QElemType x ) { 
//若队列不满, 则将元素x 插入队尾, 函数返回true,否则函数返回false,不能进队 
if ( queueFull (Q) ) return false; 
Q.elem[Q.rear] = x; / /按 照队尾指针指示位置插入 
Q.rear = (Q.rear+1) % Q.maxSize; //队尾指针进1 
return true; 
}b
ool deQueue ( CircQueue& Q, QElemType& x ) { 
//若队列已空则不能出队,函数返回false;若队列不空则函数退掉队头元素并通过
//引用参数x 返回出队元素的值,函数返回true 
if ( queueEmpty (Q) ) return false; 
x = Q.elem[Q.front]; //存队头元素的值 
Q.front = (Q.front+1) % Q.maxSize; / /队 头指针进1 
return true; 
}b
ool getFront( CircQueue& Q, QElemType& x ) { 
//若队列不空则函数返回队头元素的值,不退出队头元素 
if ( queueEmpty (Q) ) return false; 
x = Q.elem[Q.front]; return true; / /x 返回队头元素的值
}v
oid printQueue ( CircQueue& Q ) { 
for ( int i = Q.front; i < Q.rear; i = (i+1) % Q.maxSize ) 
printf ( "%c ", Q.elem[i] ); 
printf ( "\n" ); 
} 
想想看 Q.rear-Q.front的结果在什么情况下是正数,在什么情况下是负数? 
4.循环队列主要操作的性能分析
循环队列主要操作的性能如表3-4所示。
表3-4 循环队列各种操作的性能比较
操 作 名时间复杂度空间复杂度操 作 名时间复杂度空间复杂度
初始化initQueue O(1) O(1) 判队列空否QueueEmpty O(1) O(1) 
进队列enQueue O(1) O(1) 判队列满否QueueFull O(1) O(1) 
出队列deQueue O(1) O(1) 求队列长度QueueSize O(1) O(1) 
读取队头getFront O(1) O(1) 输出队列printQueue O(n) O(1)

95 
除输出队列操作外,循环队列所有操作的时间复杂度和空间复杂度都为O(1),其性能
良好。注意,空间复杂度是指操作中所使用的附加空间的复杂度,它是常数级的,包括0个
附加空间。
想想看 在后续章节,如树与二叉树、图、排序等,如果在它们的算法中使用了顺序
栈或循环队列,这些栈或队列是那些算法的附加空间。在这种场合,栈或队列涉及的元素数
组是否应计入算法的空间复杂度度量内? 
3.2.3 双循环队列
假设两个队列共享一个首尾相连的环形向量空间,如图3-12所示,则称其为双循环队
列。好处是两个队列空间的使用可能不相同,一个可能进得多一些,一个可能进得少一些, 
它们共享一个向量空间,可以互相调剂,更有效地利用存储空间。
1.双循环队列的结构定义
双循环队列共享同一存储空间,其结构类型如程序3-16所示。
图3-12 双循环队列的示例
程序3-16 双循环队列的结构定义(存放于DualQueue.h) 
#include<stdio.h> 
#include <stdlib.h> 
typedef int QElemType; 
typedef struct { 
QElemType elem[maxSize]; //共享存储空间 
int front[2], rear[2]; //队列0 和队列1 的队头、队尾指针
} DualQueue; 
初始时,队列0的队头指针front[0]和队尾指针rear[0],队列1的队头指针front[1]和
队尾指针rear[1]各自指向环形存储数组的同一个位置,如图3-12(a)所示,它们相距
maxSize/2个位置。在使用两个队列的过程中,它们的队头、队尾指针都向顺时针方向移
动,如图3-12(b)所示。若一个队列编号为0,那么另一个队列的编号就为1。在程序中用i 
(=0或1)和1-i(=1或0)代表它们的编号。
进队方式是先让队尾指针进1,再按队尾指针所指位置将新元素进队,出队方式是先让
队头指针进1,再把队头元素取出。这样,队列i 的队尾指针rear[i]指示实际队尾元素位
置,队头指针front[i]指示实际队头元素的前一位置,队列i 空的条件为rear[i]=front[i],队
列i 满的条件为rear[i]=front[1-i],表明另一个的队尾追上了本队列的队头。
为充分利用存储空间,在队列i 满的情况下,若又有新元素要进队,应当再判断另一个

96 
队列是否已满,若未满,可以把另一个队列顺时针移动一个元素位置,为队列i 空出一个位
置,以插入新元素;若另一个队列已满,则报错。
2.队列运算的实现
共享存储空间采用静态存储分配,在程序运行期间空间大小不会改变。所以存储空间
被视为首尾相连的环形数组,类似于循环队列,指针顺时针移动时走到maxSize-1位置,下
一步将进到0位置,这就用到整数的除余运算(%)。相应算法的实现参看程序3-17。
程序3-17 双循环队列主要操作的实现(存放于DualQueue.cpp) 
#include "DualQueue.h" 
void initQueue ( DualQueue& Q ) { //双循环队列的初始化 
Q.front[0] = 0; Q.rear[0] = 0; 
Q.front[1] = maxSize/2; Q.rear[1] = maxSize/2; 
}b
ool queueFull ( DualQueue Q, int i ) { //队列i 判满 
return Q.rear[i] == Q.front[1-i] || Q.rear[1-i] == Q.front[i]; 
}b
ool queueEmpty ( DualQueue Q, int i ) { //队列i 判空 
return Q.front[i] == Q.rear[i]; 
}b
ool enQueue ( DualQueue& Q, int i, QElemType x ) { 
//将x 进到双循环队列Q 中,i 指定进0 号还是1 号队列。若进队列成功函数返回true 
if ( i < 0 || i > 1 ) return false; 
if ( Q.rear[i] == Q.front[1-i] ) { 
if ( Q.rear[1-i] == Q.front[i] ) return false; //另一队列也满返回0 
int j = Q.rear[1-i]; //另一队列前移一个位置 
while ( j > Q.front[1-i] ) { 
Q.elem[(j+1) % maxSize] = Q.elem[j]; //顺时针前移元素 
j = ( j-1+maxSize ) % maxSize; 
} 
Q.rear[1-i] = ( Q.rear[1-i]+1 ) % maxSize; //修改队列1-i 的指针 
Q.front[1-i] = ( Q.front[1-i]+1 ) % maxSize; 
} 
Q.rear[i] = ( Q.rear[i]+1 ) % maxSize; //队列i 的队尾指针进1 
Q.elem[Q.rear[i]] = x; 
return true; 
}b
ool deQueue ( DualQueue& Q, int i, QElemType& x ) { 
//从指定第i 号队列中退出队头元素,且通过引用参数x 返回其值,函数返回
//true;否则函数返回false,引用参数x 的值不可用 
if ( i < 0 || i > 1 ) return false; 
Q.front[i] = ( Q.front[i]+1 ) % maxSize; 
x = Q.elem[Q.front[i]]; 
return true; 
}
进队和出队算法的时间复杂度和空间复杂度均为O(1)。
3.2.4 链式队列
1.链式队列的概念
链式队列是队列的基于单链表的存储表示,如图3-13所示。在单链表的每一个结点中

97 
有两个域:data域存放队列元素的值,link域存放单链表下一个结点的地址。
图3-13 链式队列
为了操作方便,通常链式队列不设头结点,队列的队头指针直接指向单链表的首元结
点,这意味着实际队头就在链表的首元结点。若要从队列中退出一个元素,只需从单链表中
删除首元结点即可。而队列的队尾指针指向单链表的尾结点,存放新元素的结点应插在队
列的队尾,即单链表的最后一个结点后面,这个新结点将成为新的队尾。
用单链表表示的链式队列特别适合于数据元素变动比较大的情形,而且不存在队列满
而产生溢出的情况。另外,假若程序中要使用多个队列,与多个栈的情形一样,最好使用链
式队列。这样不会出现存储分配不合理的问题,也不需要进行存储的移动。
2.链式队列的结构定义
链式队列实际上就是单链表,每个结点的定义与单链表结点相同,而链表则设置了两个
指针:队头指针front指向链表的头结点,而头结点的下一结点才是队列的队头结点;队尾
指针rear指向链尾结点。队列所有结点的访问都必须从队头开始顺序访问。队列的结构
定义如程序3-18所示。
程序3-18 链式队列的结构定义(存放于LinkQueue.h) 
#include<stdio.h> 
#include <stdlib.h> 
typedef int QElemType; 
typedef struct Node { //链式队列结点定义 
QElemType data; //结点的数据 
struct Node *link; //结点的链接指针
} LinkNode; 
typedef struct { //链式队列定义 
LinkNode *front, *rear; //队列的队头和队尾指针
} LinkQueue; 
3.链式队列主要操作的实现
链式队列主要操作的实现如程序3-19所示,与单链表不同的是,插入和删除仅限于链
表的两端:插入(进队列)在链尾,新结点成为新的链尾;删除(出队列)在链头,删除链表的
首元结点,而首元结点的下一结点成为新的首元结点。
程序3-19 链式队列主要操作的实现(存放于LinkQueue.cpp) 
#include "LinkQueue.h" 
void initQueue ( LinkQueue& Q ) { //队列初始化 
Q.front = Q.rear = NULL; //队头与队尾指针初始化
}; 
void clearQueue ( LinkQueue& Q ) { //清空队列 
LinkNode *p; 
while ( Q.front != NULL ) { //逐个删除队列中的结点 
p = Q.front->link; Q.front = p->link; //摘下首元结点,修改队头 
free (p);