第
3
章栈和队列
栈和队列是两种特殊的线性结构。从数据结构的角度看,栈和队列也
是一种线性表。它们的特殊性在于栈和队列的操作相比于线性表受到了
一定的限制。因此,栈和队列也称为操作受限的线性表。
生活中栈和队列的使用十分广泛。例如枪膛的子弹与叠起的餐盆,只
在一端进一端出,即为栈;而排队,一端进另一端出,则为队列。栈和队列
因操作受限而有了特殊的特性,在解决问题中起到特殊的工具作用。
本章除了讨论栈和队列的定义和存储结构外,还将侧重介绍栈的“先
进后出”原则和队列的“先进先出”原则,给出一些应用实例,以体会两种特
殊线性表的应用场景。
本章主要知识点
● 栈和队列的结构特性。
● 栈和队列的顺序存储实现。
● 栈和队列的链式存储实现。
本章教学目标
● 掌握栈和队列的结构特性与操作特性。
● 灵活运用栈和队列解决应用问题。
3.栈
1
3.1
栈的定义和特点
1.
栈(stack)是限定只能在一端进行插入或删除操作的线性表。表中允
许进行插入和删除操作的一端称为栈顶(top),另一端相应地称为栈底
(botom )。栈中没有数据元素时称为空栈。栈的插入操作称为入栈/进
栈/压栈(push),栈的删除操作称为出栈/弹栈(pop)。栈结构如图3-1
所示。
64 数据结构原理与应用
图3-1 栈结构示意图
在栈中,无论是存数据还是取数据,都必须遵循“先进后出”原则,即最先入栈的元素
最后出栈。因此,栈又称为先进后出(firstinlastout,FILO)或后进先出的线性表,简称
FILO 线性表。如图3-1所示的栈,从当前数据的存储状态可知,元素a1 是最先入栈的。
因此,当要从栈中取出元素a1 时,需要提前将元素an ,an-1,…,a2 从栈中取出,然后才能
成功取出a1。
图3-2是一个栈的操作示意图,图中箭头表示当前栈顶元素位置。图3-2(a)表示一
个空栈;图3-2(b)表示插入一个元素a 之后栈的状态;图3-2(c)表示插入元素b、c、d 之
后栈的状态;图3-2(d)表示删除一个元素d 之后栈的状态。
图3-2 栈操作示意图
由于栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构,因
此线性表的操作特性它都具备,只是栈的插入和删除操作改名为入栈和出栈。除此之外,
栈的基本操作还包括初始化、判栈空、取栈顶元素等。
下面是栈的抽象数据类型Stack的定义。
ADT Stack {
数据对象: D ={ai |ai ∈ElementSet, i =1, 2, …, n , n ≥0}。
数据关系: R ={<ai - 1, ai >|ai -1, ai ∈D , i =2, …, n },约定an 端为栈顶,a 1 端为栈底。
基本操作:
InitStack(&S) //初始化栈
操作功能: 创建一个空的栈S。
操作输出: 创建成功,返回true;不成功,退出。
DestroyStack(&S) //销毁栈
操作功能: 释放栈S 所占的存储空间。
操作输出: 无。
GetTop(S,&e) //取栈顶元素
操作功能: 读取栈S 的栈顶元素。
操作输出: 如果栈不空,输出栈顶元素,不修改栈顶指针。
Push(&S,e) //入栈
第3 章 栈和队列 65
操作功能: 在栈顶插入新元素e。
操作输出: 插入元素e 为新的栈顶元素。
Pop(&S,&e) //出栈
操作功能: 删除栈顶元素。
操作输出: 删除栈S 的栈顶元素并用e 返回其值。
StackLength(S) //测栈长
操作功能: 求栈S 的长度。
操作输出: 返回栈S 的元素个数。
StackEmpty(S) //判栈空
操作功能: 判断栈S 是否为空。
操作输出: 如果S 是空栈,返回true;否则,返回false。
ClearStack(&S) //清空栈
操作功能: 删除栈S 中的所有元素。
操作输出: 栈S 被置为空栈。
}ADT Stack
【例3-1】 设有4个元素a、b、c、d 进栈,给出它们所有可能的出栈次序。
【解】 栈对线性表的插入和删除位置进行了限制,但并没有对元素进出的时间进行
限制。也就是说,在不是所有元素都进栈的情况下,先进栈的元素也可以出栈,只要保证
是栈顶元素出栈即可。因此,所有可能的出栈次序如下:abcd、abdc、acbd、acdb、adcb、
bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba。
【例3-2】 设n 个元素进栈序列是1,2,…,n,其输出序列是p1,p2,…,pn ,若
p1=3,则p2 的值( )。
(A)一定是2 (B)一定是1 (C)不可能是1 (D)以上都不对
【解】 当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈的为2,也可能为
4或后面的元素进栈,再出栈。因此,p2 可能是2,也可能是4,…,n,但一定不能是1。因
此本题答案为C。
与线性表类似,栈也有两种存储结构,分别称为顺序栈和链栈。
3.1.2 顺序栈
顺序栈(sequentialstack)是用顺序表实现栈的存储结构,即利用一组地址连续的存
储单元依次存放自栈底到栈顶的数据元素。
图3-3 顺序栈存储示意图
连续内存的使用是基于起始地址的,设指针base为这个
存储空间的基地址。栈的操作只能在栈顶进行,为方便操
作,定义一个top变量指示栈顶元素在顺序栈中的位置①。
另设栈的容量为stacksize。顺序栈的存储示意图如图3-3所
示,存储结构定义如下。
template<class DT>
typedef struct
① 也有将栈顶指针设在栈顶元素的上方,此种情况下空栈top=1。解题时,需要了解清楚题目中的设置。
66 数据结构原理与应用
{ DT * base; //栈底指针
int top; //栈顶
int stacksize; //栈可用的最大容量
}SqStack;
由上述定义可知下列语句的含义。
SqStackS表示声明一个顺序栈变量S。
S.base[S.top]表示顺序栈S的栈顶元素。
S.top表示栈顶元素位置。当S.top==-1,表示栈空,无法出栈。
S.stacksize表示顺序栈S的容量。当S.top==S.stacksize-1,表示栈满,无法入栈。
这里约定base为栈底指针,若base的值为NULL,表示栈结构不存在;元素e进栈
时,先将top增1,然后将其放在栈顶指针处;元素要出栈时,先将栈顶指针处的元素取
出,然后top减1。因此,top+1的值实际上反映了栈中元素的个数,与顺序表中length
值的意义相同。
【思考】 因为连续内存单元容量受限,所以在顺序表中设置了表长属性length(线性
表中元素的个数),以指示连续内存中已被用掉的单元并由它判断表空和表满。顺序栈中
没有设置栈的长度,如何判断栈空和栈满?
图3-4所示为栈空、栈满、入栈以及出栈时top的特征及变化。
图3-4 栈顶指针与栈中元素的关系
由于顺序栈的插入和删除操作限制在栈顶进行,因此对应栈的基本操作比顺序表要
简单得多。根据ADTStack中的基本操作定义设置操作参数类型和返回值后,顺序栈的
基本操作的函数定义简述如表3-1所示。
表3-1 顺序栈的基本操作的函数定义
序号函数定义功能说明
1 //初始化顺序栈
boolInitStack(SqStack&S,intm)
创建一个容量为m 的空栈S;创建成功,返回true;否
则,退出
2 //销毁顺序栈
voidDestroyStack(SqStack&S) 释放顺序栈S所占内存空间
3 //取栈顶元素
boolGetTop(SqStackS,DT &e)
判断栈S是否空,空则返回false;否则取栈顶元素赋
给e,返回true
第3 章 栈和队列 67
续表
序号函数定义功能说明
4 //入栈
boolPush(SqStack&S,DTe)
判断栈S是否满,满则返回false;否则在栈顶插入一
个值为e的元素,返回true
5 //出栈
boolPop(SqStack&S,DT &e)
判断栈S是否空,空则返回false;否则删除栈顶元素,
返回true
6 //测栈长
intStackLength(SqStackS) 求顺序栈S的长度,即栈中元素个数
7 //判栈空
boolStackEmpty(SqStackS)
判断顺序栈S是否为空栈。如果是空栈,返回true;否
则,返回false
8 //清空栈
voidClearStack(SqStack&S) 把顺序栈变成空栈
顺序栈部分基本操作的实现算法如下。
1.初始化顺序栈
【算法思想】 申请一组连续的内存空间,用来存放顺序栈,使base指向这段空间的
基址;新栈为空栈,栈顶top设为-1;申请的容量为栈最大可用容量m 。
算法描述与算法步骤如算法3.1所示。
算法3.1 【算法描述】【算法步骤】
01234567
template<class DT>
bool InitStack(SqStack<DT>&S,int m)
{ S.base=new T[m];
if(!base) exit(1);
S.top=-1;
S.stacksize=m;
return true;
}
//创建容量为m 的空栈
//1.申请一组连续的内存空间
//申请失败,退出
//2.申请成功,为栈属性赋值
//3.返回true
2.销毁栈
【算法思想】 对应new申请内存空间命令,用delete释放顺序栈S所占内存空间;
置栈顶top为-1;栈最大可用容量StackSize为0。
算法描述与算法步骤如算法3.2所示。
算法3.2 【算法描述】【算法步骤】
0123456
template<class DT>
void DestroyStack(SqStack<DT>&S)
{
delete []base;
S.top=-1;
S.stacksize=0;
}
//销毁顺序栈
//1.释放顺序栈占用的内存空间
//2.为栈属性赋值
68 数据结构原理与应用
3.入栈
【算法思想】 判断栈是否满,满则返回false;否则将栈顶指针增1,新元素插入栈顶
指针位置。
算法描述与算法步骤如算法3.3所示。
算法3.3 【算法描述】【算法步骤】
012345678
template<class DT>
bool Push(SqStack<DT>&S, DT e)
{
if(S.top==S.stacksize-1)
return false;
S.top++;
S.base[S.top]=e;
return true;
}
//在栈顶插入一个新元素
//1.栈满的情况,即栈上溢出
//无法入栈,返回false;
//2.栈顶指针增1
//元素e 放在栈顶指针处
//3.返回true
4.出栈
【算法思想】 判断栈是否空,空则返回false;否则取栈顶元素赋给e,然后将栈顶指
针减1。
算法描述与算法步骤如算法3.4所示。
算法3.4 【算法描述】【算法步骤】
012345678
template<class DT>
bool Pop(SqStack<DT>&S,DT &e)
{
if(S.top==-1)
return false;
e=S.base[S.top];
S.top--;
return true;
}
//删除栈顶元素
//1.栈空的情况,即栈下溢出
//无法出栈,返回false
//2.取栈顶元素,赋值给e
//栈顶指针减1
//3.返回true
5.取栈顶元素
【算法思想】 判断栈是否空,空则返回false;否则取栈顶元素赋给e。此操作栈顶指
针保持不变。
算法描述与算法步骤如算法3.5所示。
算法3.5 【算法描述】【算法步骤】
012
template<class DT>
bool GetTop(SqStack<DT>S,DT &e)
{
//取栈顶元素
第3 章 栈和队列 69
34567
if(S.top==-1)
return false;
e=S.base[S.top];
return true;
}
//1.栈空的情况,即栈下溢出
//无法出栈,返回false
//2.取栈顶元素,赋值给e
//3.返回true
顺序栈与顺序表一样,操作时会受最大空间容量的限制,虽然在出现“满”的情况时可
以通过重新分配存储空间来扩大容量,但此项工作量大,应尽量避免。如果在一个程序中
需要同时使用具有相同数据类型的两个栈,那么可以为它们各自开辟数组空间,也可以用
一个数组来存储两个栈,具体做法如下。
让一个栈的栈底在数组的始端,即下标为0处;让另一个栈的栈底在数组的末端,即
下标为数组长度n-1处。这样,两个栈如果增加元素,每个栈从各自的端点向中间延
伸。假设top1和top2分别是栈1和栈2的栈顶指针,如图3-5所示。可以想象,只要它
们不“见面”,两个栈就可以一直使用。从这里也就可以分析出来,当top1等于-1时,栈
1为空;当top2等于n 时,栈2为空。那么,什么时候栈满呢?
图3-5 栈顶指针与栈中元素的关系
可以思考极端的情况:若栈2是空栈,栈1的top1等于n-1时,为栈1满;反之,当
栈1为空栈,top2等于0时,为栈2满。但更多的情况是在两个栈“见面”之时,也就是两
个指针之间相差1(即top1+1==top2)时栈满。
此时,只有当整个存储空间都被两个栈占满,才会发生上溢。使用这样的数据结构通
常都是当两个栈的空间需求有相反关系时,也就是一个栈增长时另一个栈在缩短的情况。
这样使用两栈共享存储空间才有较大意义。两栈共享一个长度为n 的存储空间与两个
栈分别占用两个长度为.n/2.和én/2ù①的存储空间相比较,前者发生上溢的概率要比后
者小得多。
在实际应用中,如果应用程序无法预先估计栈可能达到的最大容量,建议使用链栈。
3.1.3 链栈
链栈(linkedstack)是用链表实现栈的存储结构,通常用单链表表示。
对于链栈来说,一般不考虑栈满上溢的情况,除非内存已经没有可以使用的空间。由
于链栈的主要操作是在栈顶进行插入和删除,因此把栈顶放在单链表的头部是最方便的,
这样可以避免实现数据“入栈”和“出栈”时做大量遍历链表的耗时操作。而且,在链栈中
没有必要像单链表那样为操作方便附加一个头结点。因此,链栈实际上是一个只能采用
① .n/2.表示下取整,即不大于n/2的最大整数;én/2ù表示上取整,即不小于n/2的最小整数。
70 数据结构原理与应用
头插法插入或删除数据的单链表。
链栈的存储及操作示意图如图3-6所示。
图3-6 链栈的存储及操作示意图
链栈的结点结构与单链表的结点结构相同,其存储结构定义如下:
template<class DT>
struct SNode //结点类型名
{ DT data; //数据域,存储数据元素
SNode *next; //指针域,指向后继结点
};
标识链栈的是指向栈顶元素结点的头指针。
根据定义,声明一个链栈变量S的语句为SNode*S。
根据ADTStack中的基本操作定义设置操作参数类型和返回值后,链栈的基本操作
的函数定义简述如表3-2所示。
表3-2 链栈的基本操作的函数定义
序号函数定义功能说明
1 //初始化链栈
boolInitStack(SNode*&S) 创建一个空栈S,返回true
2 //销毁链栈
voidDestroyStack(SNode*&S) 释放链栈S所占内存空间
3 //取栈顶元素
boolGetTop(SNode*S,DT &e)
判断栈S是否空,空则返回false;否则取栈顶
元素赋给e,返回true
4 //入栈
boolPush(SNode*&S,DTe) 在栈顶插入一个值为e的元素,返回true
5 //出栈
boolPop(SNode*&S,DT &e)
判断栈S是否空,空则返回false;否则删除栈
顶元素,返回true
6 //测栈长
intStackLength(SNode*S) 求链栈S的长度,即栈中元素个数
第3 章 栈和队列 71
续表
序号函数定义功能说明
7 //判栈空
boolStackEmpty(SNode*S)
判断链栈S 是否为空栈。如果是空栈,返回
true;否则,返回false
8 //清空栈
voidClearStack(SNode*&S) 把链栈变成空栈
下面给出链栈中部分基本操作的实现算法。
1.初始化链栈
【算法思想】 构造一个空栈,直接将栈顶指针置空即可。
算法描述与算法步骤如算法3.6所示。
算法3.6 【算法描述】【算法步骤】
012345
template<class DT>
bool InitStack(SNode<DT>*&S)
{
S=NULL;
return true;
}
//构造一个空栈
//1.栈顶指针置空
//2.返回true
2.销毁栈
【算法思想】 从栈顶结点开始,将栈S中的结点逐个销毁。
算法描述与算法步骤如算法3.7所示。
算法3.7 【算法描述】【算法步骤】
0123456789
template<class DT>
void DestroyStack(SNode<DT>*&S)
{
while(S)
{
p=S;
S=S->next;
delete p;
}
}
//销毁链栈S
//栈非空
//1.取第一个结点
//2.栈顶指针后移
//3.释放原第一个结点
3.入栈
【算法思想】 为入栈元素动态分配一个结点空间p,插入栈顶并修改栈顶指针为p。
算法描述与算法步骤如算法3.8所示。
72 数据结构原理与应用
算法3.8 【算法描述】【算法步骤】
0123456789
template<class DT>
bool Push(SNode<DT>*&S,DT e)
{
p=new SNode<DT>;
if(!p) return false;
p->data=e;
p->next=S;
S=p;
return true;
}
//插入元素e 为新的栈顶元素
//1.生成新结点
//创建失败,返回false
//2.新结点数据域置为e
//将新结点插入栈顶
//修改栈顶指针为p
//3.返回true
4.出栈
【算法思想】 判断栈是否空,空则返回false;否则取栈顶元素赋给e,然后修改栈顶
指针并释放原栈顶元素的空间。
算法描述与算法步骤如算法3.9所示。
算法3.9 【算法描述】【算法步骤】
0123456789
10
template<class DT>
bool Pop(SNode<DT>*&S,DT &e)
{
if(S==NULL)
return false;
p=S;
e=p->data;
S=S->next;
delete p;
return true;
}
//删除S 栈顶元素,e 返回其值
//1.栈空的情况,即栈下溢出
//无法出栈,返回false
//2.p 暂存栈顶结点
//栈顶元素赋值给e
//修改栈顶指针
//释放原栈顶元素的空间
//3.返回true
5.取栈顶元素
【算法思想】 判断栈是否空,空则返回false;否则取栈顶元素赋给e。此操作栈顶指
针保持不变。
算法描述与算法步骤如算法3.10所示。
算法3.10 【算法描述】【算法步骤】
01234
template<class DT>
bool GetTop(SNode<DT>*S,DT &e)
{
if(S==NULL)
return false;
//取栈顶元素
//1.栈空的情况,即栈下溢出
//无法出栈,返回false
第3 章 栈和队列 73
5678
p=S;
e=p->data;
return true;
}
//2.取栈顶元素
//赋值给e
//3.返回true
3.1.4 顺序栈和链栈的比较
顺序栈和链栈基本操作的实现在时间上都是一致的,都是常数级O (1)。在空间上,
初始化一个顺序栈必须先声明一个固定长度,这样在栈不满时,就浪费了一部分存储空
间,并且存在栈满溢出的问题;链栈没有栈满的问题,只有当内存没有可用空间时才会出
现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。因此,当栈的使用过
程中元素个数变化较大时,用链栈是适宜的,反之应该采用顺序栈。
3.1.5 栈的应用
日常生活中栈的应用很常见。例如,洗干净的盘子总是逐个叠放在已经洗好的盘子
上面,使用时从上往下逐个取出;在软件使用中,很多软件都有“撤销”或“后退”操作,可以
像时间倒退一样,返回到之前的某个操作或某个页面。栈的操作特点正是这些实际应用
的抽象。
栈是一种非常重要的数据结构,用途十分广泛。在程序设计中,如果需要对数据存取
采用“先进后出”原则的特点,则可以利用栈来实现。在后续二叉树的各种算法中会大量
使用栈。下面通过括号匹配和算术表达式求值的例子说明栈的应用。
【应用3-1】 括号匹配的校验。
在表达式中经常会用到两种括号:圆括号和方括号。不管使用哪种括号,表达式没
有问题的一个重要因素就是所使用的括号是否能够匹配上。括号可以嵌套,([()])或
([]())等为正确格式,但([)、([]或(()]都不符合要求。
括号匹配要求“就近匹配”,后面的先配,一层层由内而外。因此,可以使用栈的“先进
后出”原则来校验括号是否匹配。每当读入一个左括号,直接入栈,等待相匹配的同类右
括号。每当读入一个右括号,若栈不空且与当前栈顶元素匹配,则将栈顶元素出栈,继续
进行比较;否则返回。
【算法思想】 首先初始化一个空栈S,设置flag标志位,用来标志匹配结果以控制循
环以及返回结果。1表示匹配成功,0表示匹配失败,flag初值置为1。然后从左往右扫
描表达式,依次读入字符ch,如果表达式没有扫描结束或flag非零,则循环执行下列
操作。若
ch是左括号“(”或“[”,ch入栈;若ch是右括号“)”,如栈不空且栈顶元素是“(”,
则匹配成功,栈顶元素出栈后继续扫描,否则匹配失败,flag置为0;若ch是右括号“]”,如
栈不空且栈顶元素是“[”,则匹配成功,栈顶元素出栈后继续扫描,否则匹配失败,flag置
为0。
循环结束后,如果栈空并且flag的值为1,则匹配成功,返回true;否则返回false。
74 数据结构原理与应用
算法描述与算法步骤如算法3.11所示。
算法3.11 【算法描述】【算法步骤】
0123456789
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool match()
{
InitStack<int>(S);
flag=1;
cin>>ch;
while(ch!='#'&& flag==1)
{
switch(ch)
{
case '(':
case '[':
Push(S,ch);
break;
case ')':
GetTop(S,e);
if(!StackEmpty(S) && e=='(')
Pop(S,x);
else
flag=0;
break;
case ']':
GetTop(S,e);
if(!StackEmpty(S) && e=='[')
Pop(S,x);
else
flag=0;
break;
}
cin>>ch;
}
if(StackEmpty(S) && flag)
return true;
else
return false;
}
//括号匹配校验
//1.初始化空栈
//2.标志匹配结果以控制循环以
//及返回结果
//假设表达式以#结尾
//3.左括号入栈
//4.右括号入栈
//4.1 栈非空且栈顶是'(',匹
//配正确,出栈
//4.2 栈空或栈顶不是'(',匹
//配失败
//4.3 栈非空且栈顶是'[',匹
//配正确
//4.4 栈空或栈顶不是'[',匹
//配失败
//5.继续读入下一个字符
//6.匹配成功,返回true
//匹配失败,返回false
【算法分析】 算法执行过程中需要从头到尾扫描表达式中的每个字符,设表达式对
应的字符串长度为n,则算法的时间复杂度为O(n)。算法运行时所占用的辅助存储空间
主要取决于栈S的大小,显然栈S的空间大小不会超过n,因此算法的空间复杂度也为
O(n)。
第
3
章 栈和队列
75
【应用3-2】算术表达式求值。
表达式求值是数学中的一个基本问题,也是程序设计中的一个基本问题。这里我们
仅讨论简单算术表达式的求值问题。表达式包含数字和符号,表达式中处理的符号包括
+、-、*、/、(、)。
根据运算符在操作数中的位置,表达式分为三种形式:前缀表达式(prefix
expeo中缀表达式(nixpeo和后缀表达式(psfxeprsin)。中缀表达
rsin)、ifxersin) otixeo
式就是我们平常用的标准四则运算表达式,运算符在双目操作数中间且带有括号,例如表
达式1+2*(7-4)/3。
(1)中缀表达式求值
表达式求值的一个常用方法是算符优先法,即从左到右扫描表达式,按算符的优先级
高低进行计算。算术四则运算的规则可概括为:从左到右,先括号内,后括号外,先乘除
后加减。在表达式计算的每一步中,任意两个相邻出现的运算符θ1 和θ2 存在如下三种
关系之一。
● θ1<θ2:θ1 的优先权低于θ2;
θ1=θ2:θ1 的优先权等于θ2;
●
● θ1>θ2:θ1 的优先权高于θ2
。
图3-7定义了运算符的优先级关系
。
图3-7 运算符的优先级关系
这里假设所求表达式不会出现语法错误,即不考虑eror的情况。
为实现算符优先算法,设置两个工作栈:运算符栈OP,用于存放暂不进行运算的运
算符;操作数栈OD,用于存放操作数或运算结果。一个运算符是否进行运算取决于其后
出现的运算符,对应的操作分为三种:一是直接入栈(二是直接出栈(三
θ1<θ2); θ2);
θ1=
是将当前栈顶符号出栈(θ1>θ2)并计算,然后根据新的栈顶符号与当前符号的优先级关
系重复操作类型的判断。
【算法思想】初始化OP栈和OD栈,将表达式起始符“#”入OP栈。扫描表达式,
读入第一个字符ch。当读到的字符不是表达式结束符“#”或OP的栈顶元素不是“#”
时,循环执行以下操作。
若ch是操作数,则入OD栈,读入下一个字符ch;
①
则根据OP的栈顶元素(和cθ2) 进行相
②若ch是运算符, θ1) h(的优先级比较结果,
76 数据结构原理与应用
应处理。
● 如果θ1<θ2,则ch入OP栈,读入下一个字符ch;
● 如果θ1=θ2,则OP栈顶元素为'('且ch为')'时,将OP栈顶元素弹出,相当于括号
匹配成功,消去括号,读入下一个字符ch;
● 如果θ1>θ2,则弹出OP栈顶元素,并且从OD栈弹出两个操作数,进行相应运算
并将运算结果入OD栈。
最后操作数栈的栈顶元素即为表达式求值的结果,输出即可。
【例3-3】 给出中缀表达式1+2*(7-4)/3计算中栈的变化。
【解】 根据上述步骤,对表达式1+2*(7-4)/3的计算过程如表3-3所示。
表3-3 1+2*(7-4)/3计算过程中栈的变化
步骤OP栈OD 栈读入字符主要操作
1 OP.Push(‘#’)
2 = 1+2*(7-4)/3= OD.Push(‘1’)
3 = 1 1+2*(7-4)/3= OP.Push(‘+’)
4 = + 1 1+2*(7-4)/3= OD.Push(‘2’)
5 = + 12 1+2*(7-4)/3= OP.Push(‘*’)
6 = +* 12 1+2*(7-4)/3= OP.Push(‘(’)
7 = +*( 12 1+2*(7-4)/3= OD.Push(‘7’)
8 = +*( 127 1+2*(7-4)/3= OP.Push(‘-’)
9 = +*(- 127 1+2*(7-4)/3= OD.Push(‘4’)
10 = +*(- 1274 1+2*(7-4)/3= OP.Pop(),OD.Pop(),OD.Pop(),
OD.Push(7-4)
11 = +*( 123 1+2*(7-4)/3= OP.Pop()
12 = +* 123 1+2*(7-4)/3= OP.Pop(),OD.Pop(),OD.Pop(),
OD.Push(2*3)
13 = + 16 1+2*(7-4)/3= OP.Push(‘/’)
14 = +/ 16 1+2*(7-4)/3= OD.Push(‘3’)
15 = +/ 163 1+2*(7-4)/3= OP.Pop(),OD.Pop(),OD.Pop(),
OD.Push(6/3)
16 = + 12 1+2*(7-4)/3= OP.Pop(),OD.Pop(),OD.Pop(),
OD.Push(1+2)
17 = 3 1+2*(7-4)/3=
算法描述与算法步骤如算法3.12所示。
第3 章 栈和队列 77
算法3.12 【算法描述】【算法步骤】
0123456789
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
char EvaluateExpression()
{
InitStack<char>(OP);
InitStack<int>(OD);
Push(OP,'#');
cin>>ch;
GetTop(OP,e);
while(ch!='#' || e!='#')
{
if(!In(ch))
{
Push(OD,ch);
cin>>ch; }
else
switch(Precede(e,ch))
{
case '<':
Push(OP,ch);
cin>>ch;
break;
case '=':
Pop(OP,x);
cin>>ch;
break;
case '>':
Pop(OP,x);
Pop(OD,b);
Pop(OD,a);
Push(OD,Operate(a,x,b));
break;
}
GetTop(OP,e);
}
GetTop(OD,result);
return result;
}
//表达式求值
//1.初始化OP 栈
//2.初始化OD 栈
//3.表达式起始符"#"入OP 栈
//4.输入表达式,边输入边处理
//5.获取OP 栈顶元素
//6.表达式没有扫描完或OP 的栈顶元
//素不是'#'
//6.1 ch 不是运算符
//6.1.1 入OD 栈
//6.1.2 读入下一个字符
//6.2 ch 是运算符
//比较OP 栈顶元素和ch 的优先级
//6.2.1 栈顶运算符级别低
//ch 入OP 栈
//读入下一个字符ch
//6.2.2 优先级相等
//出栈
//读入下一个字符ch
//6.2.3 栈顶运算符优先级高
//6.2.3.1 运算符出栈
//6.2.3.2 弹出OD 栈顶两个操作数
//6.2.3.3 运算并将运算结果入OD 栈
//6.2.3.4 获取栈顶运算符
//7.OD 栈顶元素为表达式求值的结果
【算法分析】 同样地,算法执行过程中需要从头到尾扫描表达式中的每个字符,若表
达式对应的字符串长度为n,则算法的时间复杂度为O(n)。算法运行时所占用的辅助存
储空间主要取决于OP栈和OD栈的大小,显然它们的空间大小之和不会超过n,所以算
法的空间复杂度也为O(n)。
8
数据结构原理与应用
(2)中缀表达式转换为后缀表达式
后缀表达式是一种把所有运算符都放在操作数后面的式子,因此被称为后缀表达式,
这样就解决了运算优先级和括号的问题。计算机在计算一个标准四则运算表达式时,一
般都是先将中缀表达式转换为后缀表达式,然后进行计算,例如将中缀表达式1+2*
(7-4)/3转换为后缀表达式1274-*3/+。
这是因为计算机处理后缀表达式求值问题是比较方便的。首先扫描后缀表达式,将
遇到的操作数暂存于一个操作数栈中,凡是遇到运算符,便从栈中弹出两个操作数并将运
算结果存于操作数栈中,直到对后缀表达式中最后一个操作数处理完,最后压入栈中的数
就是最后表达式的计算结果。
利用运算符的优先级,我们可以把中缀表达式转换为后缀表达式,其过程如下。
Step1. 创建一个运算符栈。
Step2. 从左到右扫描读取表达式,执行下列运算,直至表达式结束符。
2.则输出;
1 如果是操作数,
2.则把运算符栈的栈顶算符θ1 与θ2 进行比较。
2 如果是运算符θ2,
2.1 若θ1<θ2,
2.则θ2 入运算符栈;
2.2 若θ1=θ2,则遇到“)”时将运算符栈顶元素依次出栈并输出,直至遇到左括号
2.
并将左括号出栈,但不输出;
2.3 若θ1>θ2,则从运算符栈输出所有比θ2 优先级高的算符,直至栈顶算符优先
2.
级小于θ2,
θ2 入运算符栈
。
这里给出一个手动将中缀表达式转换为后缀表达式的方法,如表3-4所示
。
表3-
4
中缀表达式转换为后缀表达式
步骤方法描述示例说明
1 写出中缀表达式1+2*(7-4)/3
2 按运算先后把每一次运算用括号括起(1+((2*(7-4)/3))
3 把算符移至对应的括号的后面(1((2(74)-)*3)/)+
4 去除括号1274-*3/+
(3)后缀表达式求值
将中缀表达式转换成对应的后缀表达式后,对表达式求值时不需要再考虑运算符的
优先级,只需要从左到右扫描一遍后缀表达式即可。后缀表达式的求值过程为:从左到
右读入后缀表达式,若读入的是一个操作数,则将其入操作数栈;若读入的是一个运算符
θ,则从操作数栈中连续出栈两个元素a、b(两个操作数), 进行运算bθa并把运算结果入
操作数栈。重复上述过程直到表达式结束,操作数栈的栈顶元素即为该后缀表达式的计
算结果。
算法描述与算法步骤如算法3.
13 所示。
第3 章 栈和队列 79
算法3.13 【算法描述】【算法步骤】
0123456789
10
11
12
13
14
15
16
17
18
char SuffixExpression()
{
InitStack(OD);
cin>>ch;
while(ch!='#')
{
if(ch 是操作数)
Push(OD,ch);
else
if(ch 是运算符)
{
Pop(OD,a);Pop(OD,b);
Push(OD,Operate(b,ch,a));
}
cin>>ch;
}
GetTop(OD,result);
return result;
}
//后缀表达式求值
//1.初始化栈
//2. 从左到右读入后缀表达式
//2.1 操作数,入栈
//2.2 运算符
//2.2.1 出栈两个元素
//2.2.2 运算后的结果入栈
//2.2.3 读入表达式
//3.栈顶元素为后缀表达式的值
例如后缀表达式1274-*3/+的求值过程如表3-5所示。
表3-5 后缀表达式1274 - *3/+的求值过程
步 骤操作数栈说 明
1 1 1进栈
2 12 2进栈
3 127 7进栈
4 1274 4进栈
5 12 遇-,4、7出栈
6 123 7-4=3,结果入栈
7 1 遇*,3、2出栈
8 16 2*3=6,6入栈
9 163 3入栈
10 1 遇/,3、6出栈
11 12 6/3=2,2入栈
12 遇+,2、1出栈
13 3 1+2=3,3入栈
14 3 扫描结束
80 数据结构原理与应用
最后求得后缀表达式1274- *3/+的结果为3,与用中缀表达式求得的结果一
致,显然后缀表达式的求值要简单得多。
3.2 队列
3.2.1 队列的定义和特点
队列(queue)和栈一样,也是一种操作受限的线性表。但与栈不同的是,队列是一种
先进先出的线性表。它只允许在一端进行插入操作,而在另一端进行删除操作。这里,允
许插入的一端称为队尾(rear),允许删除的一端称为队头或队首(front)。向队列中插入
新元素称为进队或入队(enqueue),新元素入队后就成为新的队尾元素。从队列中删除元
素称为出队(dequeue)或离队,元素出队后,其直接后继元素就成为新的队首元素。队列
结构如图3-8所示。
图3-8 队列结构示意图
图3-9是一个队列的操作示意图,图中front指向队首元素位置,rear指向队尾元素
的下一个位置。图3-9(a)表示一个空队;图3-9(b)表示插入3个元素之后队列的状态;
图3-9(c)表示进行一次出队操作之后队列的状态;图3-9(d)表示再出队一次之后队列的
状态。
图3-9 队列的操作示意图
队列的操作与栈的操作类似,不同的是插入数据只能在队尾进行,删除数据只能在队
头进行。下面是队列的抽象数据类型Queue的定义。
ADT Queue {
数据对象: D ={ai |ai ∈ElementSet, i =1, 2, …, n , n ≥0}。
数据关系: R ={<ai - 1, ai >|a i-1, ai ∈D , i =2, …, n },约定an 端为队尾,a 1 端为队头。
基本操作:
InitQueue(&Q) //初始化队列
操作功能: 创建一个空的队列Q。
操作输出: 创建成功,返回true;不成功,返回false。
DestroyQueue(&Q) //销毁队列
操作功能: 释放队列Q 所占的存储空间。
第3 章 栈和队列 81
操作输出: 无。
GetHead(Q) //取队头元素
操作功能: 读取队列Q 的队头元素。
操作输出: 如果队列不空,输出队头元素。
EnQueue(&Q,e) //入队
操作功能: 在队尾插入新元素e。
操作输出: 插入元素e 为队列Q 新的队尾元素。
DeQueue(&Q,&e) //出队
操作功能: 删除队头元素。
操作输出: 删除队列Q 的队头元素并用e 返回其值。
QueueLength(Q) //测队长
操作功能: 求队列Q 的长度。
操作输出: 返回队列Q 的元素个数。
QueueEmpty(Q) //判队空
操作功能: 判断队列Q 是否为空。
操作输出: 如果Q 是空队,返回true;否则,返回false。
ClearQueue(&Q) //清空队列
操作功能: 删除队列Q 中的所有元素。
操作输出: 队列Q 被置为空队。
}ADT Queue
【例3-4】 若元素入队顺序为1234,能否得到3142的出队顺序?
【解】 入队顺序为1234,那么由队列的先进先出原则,出队顺序也为1234。因此不
能得到3142的出队顺序。
3.2.2 循环队列
队列作为一种特殊线性表,同样也存在顺序存储和链式存储两种方式。我们首先了
解队列的顺序存储结构———顺序队列。
和顺序栈类似,顺序队列(sequentialqueue)是利用一组连续的存储单元存放从队头
至队尾的数据元素。为操作方便,附设两个整型变量front和rear,分别指示队头和队尾
元素的位置。顺序队列定义如下。
template<class DT>
typedef struct
{ DT * base; //存储空间基地址
int front; //队头指针,指向队首元素①
int rear; //队尾指针,指向队尾元素的后面
int queuesize; //队列容量
}SqQueue;
由上述定义可知下列语句的含义。
① 也有将队头元素指向队首元素前和将队尾元素指向队尾元素的,那出队元素与入队元素在位置上是有区
别的。
2
数据结构原理与应用
SqQueue<DT>Q;表示声明一个顺序队列变量Q。
Q.rnt表示队头指针,Q.ae[Q.rnt]表示队首元素,队不空时,即出队该元素。
fobsforar表示队尾指针,如果元素入队,队不满时,存入Q.e[Q.r]处。
Q.ebasrea
这里约定初始化创建空队列时,Q.ot=Q.er0;元素入队时,若队列不满,新入
frnra=
队元素送入Q.r所指单元,队尾指针Q.r增1;元素出队时,若队列不空,从Q.
reareafront
fron
所指单元取出队头元素,队头指针Q.t增1(注意,这与现实生活中队列的队头元素出
队操作不同)。因此,在非空队列中,队头指针始终指向队首元素位置,队尾指针始终指向
队尾元素的下一个位置。
顺序队列结构及操作示意图如图3-10 所示。
图3-10 顺序队列结构及操作示意图
在图3-10(d)中,由于当前队列分配的最大存储空间为6,如有新元素插入,则无法继
续入队,会产生数组越界引起程序非法操作的错误,此现象称为溢出。而实际上,此时队
列中还有可用空闲空间,因此这种现象称为假溢出。
为解决“假溢出”现象,使得数组中的存储空间可以充分利用起来,一种比较巧妙的方
法是假设存储队列的连续存储空间是头尾相接的环状结构,形成一个环形的顺序表,我们
称之为循环队列(circularqueue)。
在循环队列中,头、尾指针以及队列元素之间的关系不变,只是头、尾指针“依环增1”
的操作需要通过模运算来实现。通过取模,循环队列的头指针和尾指针可以在顺序表空
间内以头尾相接的方式“循环”移动。循环队列头、尾指针的调整方法如下。
a=(Q.er+1)%Q.eeie。
● 队尾指针增1:Q.rerraquusz
● 队头指针增1:Q.rn=(Q.ronqueeie。
fotft+1)%Q.usz
如图3-10(d)所示,在元素f入队前,rear的值为5。当元素f入队后,通过模运算,
Q.rerra因此得到rer的值为0,不会出现“假溢出”现象。若此后有元
a=(Q.er+1)%6, a
素g和h相继入队,则队列空间满,此时Q.ot=Q.er。
fot=Q.e
frnra
如图3-10(c)所示,元素c出队,则出现队空的状态,此时Q.rnrar。
由此可见,引入循环队列后,出现了队空与队满的条件一样的情况。那么,如何区分
某一状态是队空还是队满呢? 为解决这一问题,采用的方法之一是牺牲一个存储单元,即
当队尾指针加1等于队首指针时判定为队满。因此,本书约定循环队列中队空和队满的
条件如下。
ot==Q.r。
● 队空:Q.frnrea