第栈和队列 3 章 栈和队列是两种特殊的线性结构。从数据结构的角度看,栈和队列也 是一种线性表。它们的特殊性在于栈和队列的操作相比于线性表受到了 一定的限制。因此,栈和队列也称为操作受限的线性表。 生活中栈和队列的使用十分广泛。例如枪膛的子弹与叠起的餐盆,只 在一端进一端出,即为栈;而排队,一端进另一端出,则为队列。栈和队列 因操作受限而有了特殊的特性,在解决问题中起到特殊的作用。 本章除了讨论栈和队列的定义和存储结构外,还将侧重介绍栈的“先 进后出”原则和队列的“先进先出”原则,给出一些应用实例,以体会两种特 殊线性表的应用场景。 本章主要知识点 ● 栈和队列的结构特性。 ● 栈和队列的顺序存储实现。 ● 栈和队列的链式存储实现。 本章教学目标 ● 掌握栈和队列的结构特性与操作特性。 ● 灵活运用栈和队列解决应用问题。 3.栈 1 1.栈的定义和特点 3.1 栈(k)是限定只能在一端进行插入或删除操作的线性表。表中允微课视频 stac 许进行插入和删除操作的一端称为栈顶(top),另一端相应地称为栈底 (botom )。栈中没有数据元素时称为空栈。栈的插入操作称为入栈/进 栈/压栈(push),栈的删除操作称为出栈/弹栈(pop)。栈结构如图3-1 所示。 70 　数据结构原理与应用（第2 版） 图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 ∈D , i =2, …, n },约定an 端为栈顶,a 1 端为栈底。 基本操作: InitStack(&S) //初始化栈 操作功能: 创建一个空的栈S。 操作输出: 创建成功,返回true;不成功,退出。 DestroyStack(&S) //销毁栈 操作功能: 释放栈S 所占的存储空间。 操作输出: 无。 GetTop(S,&e) //取栈顶元素 操作功能: 读取栈S 的栈顶元素。 操作输出: 如果栈不空,输出栈顶元素,不修改栈顶指针。 Push(&S,e) //入栈 操作功能: 在栈顶插入新元素e。 操作输出: 插入元素e 为新的栈顶元素。 Pop(&S,&e) //出栈 第3 章　栈和队列　 71 操作功能: 删除栈顶元素。 操作输出: 删除栈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)是用顺序表实现栈的存储结构,即利用一组地址连续的存 储单元依次存放自栈底到栈顶的数据元素。 连续内存的使用是基于起始地址的,设指针base为这个存储空间的基地址。栈的操 图3-3 顺序栈存储示意图 作只能在栈顶进行,为方便操作,定义一个top变量指示栈顶 元素在顺序栈中的位置①。另设栈的容量为stacksize。顺序 栈的存储示意图如图3-3所示,存储结构定义如下。 template struct SqStack { DT * base; //栈底指针 int top; //栈顶 int stacksize; //栈可用的最大容量 } 由上述定义可知下列语句的含义。 ① 也有将栈顶指针设在栈顶元素的上方,此种情况下空栈top=1。解题时,需要了解清楚题目中的设置。 微课视频 72 　数据结构原理与应用（第2 版） 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(SqStack
S,DT &e) 栈S空返回false;否则取栈顶元素赋给e,返 回true 4 //入栈 boolPush(SqStack
&S,DTe) 栈S满返回false;否则在栈顶插入一个值为e 的元素,返回true 5 //出栈 boolPop(SqStack
&S,DT &e) 栈S空返回false;否则删除栈顶元素,返回true 6 //测栈长 intStackLength(SqStack
S) 求顺序栈S的长度,即栈中元素个数 续表 第3 章　栈和队列　 73 序号函数定义功能说明 7 //判栈空 boolStackEmpty(SqStack
S) 判断顺序栈S是否为空栈。如果是空栈,返回 true;否则,返回false 8 //清空栈 voidClearStack(SqStack
&S) 把顺序栈变成空栈 顺序栈部分基本操作的实现算法如下。 1.初始化顺序栈 【算法思想】 申请一组连续的内存空间,用来存放顺序栈,使base指向这段空间的 基址;新栈为空栈,栈顶top设为-1;申请的容量为栈最大可用容量m 。 算法描述与算法步骤如算法3.1所示。 算法3.1 【算法描述】【算法步骤】 01234567 template bool InitStack(SqStack
&S,int m) { S.base=new DT[m]; if(!S.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 void DestroyStack(SqStack
&S) { delete []S.base; S.top=-1; S.stacksize=0; } //销毁顺序栈 //1.释放顺序栈占用的内存空间 //2.为栈属性赋值 3.入栈 【算法思想】 判断栈是否满,满则返回false;否则将栈顶指针增1,新元素插入栈顶 指针位置。 算法描述与算法步骤如算法3.3所示。 74 　数据结构原理与应用（第2 版） 算法3.3 【算法描述】【算法步骤】 012345678 template bool Push(SqStack
&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 bool Pop(SqStack
&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 bool GetTop(SqStack
S,DT &e) { //取栈顶元素 34567 if(S.top==-1) return false; e=S.base[S.top]; return true; } //1.栈空的情况,即栈下溢出 //无法出栈,返回false //2.取栈顶元素,赋值给e //3.返回true 顺序栈与顺序表一样,操作时会受最大空间容量的限制,虽然在出现“满”的情况时可 以通过重新分配存储空间来扩大容量,但此项工作量大,应尽量避免。如果在一个程序中 第3 章　栈和队列　 75 需要同时使用具有相同数据类型的两个栈,那么可以为它们各自开辟数组空间,也可以用 一个数组来存储两个栈,具体做法如下。 让一个栈的栈底在数组的始端,即下标为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)是用链表实现栈的存储结构,通常用单链表表示。 对于链栈来说,一般不考虑栈满上溢的情况,除非内存已经没有可以使用的空间。由 于链栈的主要操作是在栈顶进行插入和删除,因此把栈顶放在单链表的头部是最方便的, 这样可以避免实现数据“入栈”和“出栈”时做大量遍历链表的耗时操作。而且,在链栈中 没有必要像单链表那样为操作方便附加一个头结点。因此,链栈实际上是一个只能采用 头插法插入或删除数据的单链表。 链栈的存储及操作示意图如图3-6所示。 链栈的结点结构与单链表的结点结构相同,其存储结构定义如下: template struct SNode //结点类型名 { DT data; //数据域,存储数据元素 SNode *next; //指针域,指向后继结点 }; ① .n/2.表示下取整,即不大于n/2的最大整数;én/2ù表示上取整,即不小于n/2的最小整数。 微课视频 76 　数据结构原理与应用（第2 版） 图3-6 链栈的存储及操作示意图 标识链栈的是指向栈顶元素结点的头指针。 根据定义,声明一个链栈变量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) 在栈S的栈顶插入一个值为e的元素,返回 true 5 //出栈 boolPop(SNode
*&S,DT &e) 栈S空返回false;否则删除栈顶元素,返回true 6 //测栈长 intStackLength(SNode
*S) 求链栈S的长度,即栈中元素个数 7 //判栈空 boolStackEmpty(SNode
*S) 判断链栈S 是否为空栈。如果是空栈,返回 true;否则,返回false 8 //清空栈 voidClearStack(SNode
*&S) 把链栈变成空栈 下面给出链栈中部分基本操作的实现算法。 1.初始化链栈 【算法思想】 构造一个空栈,直接将栈顶指针置空即可。 算法描述与算法步骤如算法3.6所示。 第3 章　栈和队列　 77 算法3.6 【算法描述】【算法步骤】 012345 template bool InitStack(SNode
*&S) { S=NULL; return true; } //构造一个空栈 //1.栈顶指针置空 //2.返回true 2.销毁链栈 【算法思想】 从栈顶结点开始,将栈S中的结点逐个销毁。 算法描述与算法步骤如算法3.7所示。 算法3.7 【算法描述】【算法步骤】 0123456789 template void DestroyStack(SNode
*&S) { while(S) { p=S; S=S->next; delete p; } } //销毁链栈S //栈非空 //1.取第一个结点 //2.栈顶指针后移 //3.释放原第一个结点 3.入栈 【算法思想】 为入栈元素动态分配一个结点空间p,插入栈顶并修改栈顶指针为p。 算法描述与算法步骤如算法3.8所示。 算法3.8 【算法描述】【算法步骤】 0123456789 template bool Push(SNode
*&S,DT e) { p=new SNode
; 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所示。 78 　数据结构原理与应用（第2 版） 算法3.9 【算法描述】【算法步骤】 0123456789 10 template bool Pop(SNode
*&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 bool GetTop(SNode
*S,DT &e) { if(S==NULL) return false; //取栈顶元素 //1.栈空的情况,即栈下溢出 //无法出栈,返回false 5678 p=S; e=p->data; return true; } //2.取栈顶元素 //赋值给e //3.返回true 3.1.4 顺序栈和链栈的比较 顺序栈和链栈基本操作的实现在时间上都是一致的,都是常数级O (1)。在空间上, 初始化一个顺序栈必须先声明一个固定长度,这样在栈不满时,就浪费了一部分存储空 间,并且存在栈满溢出的问题;链栈没有栈满的问题,只有当内存没有可用空间时才会出 现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。因此,当栈的使用过 程中元素个数变化较大时,用链栈是适宜的,反之应该采用顺序栈。 3.1.5 栈的应用 日常生活中栈的应用很常见。例如,洗干净的盘子总是逐个叠放在已经洗好的盘子 上面,使用时从上往下逐个取出;在软件使用中,很多软件都有“撤销”或“后退”操作,可以 像时间倒退一样,返回到之前的某个操作或某个页面。栈的操作特点正是这些实际应用 的抽象。 微课视频 第3 章　栈和队列　 79 栈是一种非常重要的数据结构,用途十分广泛。在程序设计中,如果需要对数据存取 采用“先进后出”的特点,则可以利用栈来实现。在后续二叉树的各种算法中会大量使用 栈。下面通过括号匹配和算术表达式求值的例子说明栈的应用。 【应用3-1】 括号匹配的校验。 在表达式中经常会用到两种括号:圆括号和方括号。不管使用哪种括号,表达式没 有问题的一个重要因素就是所使用的括号是否能够匹配上。括号可以嵌套,([()])或 ([]())等为正确格式,但([)、([]或(()]都不符合要求。 括号匹配要求“就近匹配”,后面的先匹配,一层层由内而外。因此,可以使用栈的“先 进后出”原则来校验括号是否匹配。每当读入一个左括号,直接入栈,等待相匹配的同类 右括号。每当读入一个右括号,若栈不空且与当前栈顶元素匹配,则将栈顶元素出栈,继 续进行比较;否则返回。 【算法思想】 首先初始化一个空栈S,设置flag标志位,用来标志匹配结果以控制循 环以及返回结果。1表示匹配成功,0表示匹配失败,flag初值置为1。然后从左往右扫 描表达式,依次读入字符ch,如果表达式没有扫描结束或flag非零,则循环执行下列 操作。若 ch是左括号“(”或“[”,ch入栈;若ch是右括号“)”,如栈不空且栈顶元素是“(”, 则匹配成功,栈顶元素出栈后继续扫描,否则匹配失败,flag置为0;若ch是右括号“]”,如 栈不空且栈顶元素是“[”,则匹配成功,栈顶元素出栈后继续扫描,否则匹配失败,flag置 为0。 循环结束后,如果栈空并且flag的值为1,则匹配成功,返回true;否则返回false。 算法描述与算法步骤如算法3.11所示。 算法3.11 【算法描述】【算法步骤】 0123456789 10 11 12 13 14 15 16 17 18 bool match(string exp) { InitStack(S); flag=1; i=0; ch=exp[i++]; 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; //括号匹配校验 //1.初始化空栈 //2.标志匹配结果以控制循环以 //及返回结果 //假设表达式以#结尾 //3.左括号入栈 //4.右括号入栈 //4.1 栈非空且栈顶是'(',匹 //配正确,出栈 //4.2 栈空或栈顶不是'(',匹 //配失败 80 　数据结构原理与应用（第2 版） 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 break; case ']': GetTop(S,e); if(!StackEmpty(S) && e=='[') Pop(S,x); else flag=0; break; } ch=exp[i++]; } if(StackEmpty(S) && flag) return true; else return false; } //4.3 栈非空且栈顶是'[',匹 //配正确 //4.4 栈空或栈顶不是'[',匹 //配失败 //5.继续读入下一个字符 //6.匹配成功,返回true //匹配失败,返回false 【算法分析】 算法执行过程中需要从头到尾扫描表达式中的每个字符,设表达式对 应的字符串长度为n,则算法的时间复杂度为O(n)。算法运行时所占用的辅助存储空间 主要取决于栈S的大小,显然栈S的空间大小不会超过n,因此算法的空间复杂度也为 O(n)。 【应用3-2】 算术表达式求值。 表达式求值是数学中的一个基本问题,也是程序设计中的一个基本问题。这里仅讨 论简单算术表达式的求值问题。表达式包含数字和符号,表达式中处理的符号包括+、 -、*、/、(、)。 根据运算符在操作数中的位置,表达式分为3 种形式:前缀表达式(prefix expression)、中缀表达式(infixexpression)和后缀表达式(postfixexpression)。中缀表达 式就是平常用的标准四则运算表达式,运算符在双目操作数中间且带有括号,如表达式 1+2*(7-4)/3。 (1)中缀表达式求值。表达式求值的一个常用方法是算符优先法,即从左到右扫描 表达式,按运算符的优先级高低进行计算。算术四则运算的规则可概括为:从左到右,先 括号内后括号外,先乘除后加减。在表达式计算的每一步中,任意两个相邻出现的运算符 θ1 和θ2 存在如下3种关系之一。 ● θ1<θ2:θ1 的优先级低于θ2; ● θ1=θ2:θ1 的优先级等于θ2; ● θ1>θ2:θ1 的优先级高于θ2。 图3-7定义了运算符的优先级关系。 这里假设所求表达式不会出现语法错误,即不考虑error的情况。 为实现算符优先算法,设置两个工作栈:运算符栈OP,用于存放暂不进行运算的运 算符;操作数栈OD,用于存放操作数或运算结果。一个运算符是否进行运算取决于其后 出现的运算符,对应的操作分为3种:一是直接入栈(θ1<θ2);二是直接出栈(θ1=θ2);三 第3 章　栈和队列　 81 图3-7 运算符的优先级关系 是将当前栈顶符号出栈(θ1>θ2)并计算,然后根据新的栈顶符号与当前符号的优先级关 系重复操作类型的判断。 【算法思想】 初始化OP栈和OD栈,将表达式起始符“=”入OP栈。扫描表达式, 读入第一个字符ch。当读到的字符不是表达式结束符“=”或OP的栈顶元素不是“=” 时,循环执行以下操作。 ① 若ch是操作数,则入OD栈,读入下一个字符ch; ② 若ch是运算符,则根据OP的栈顶元素(θ1)和ch(θ2)的优先级比较结果,进行相 应处理。 ● 如果θ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 Push(OP,'=') 2 = 1+2*(7-4)/3= Push(OD,1' ') 3 = 1 1+2*(7-4)/3= Push(OP,'+') 4 = + 1 1+2*(7-4)/3= Push(OD,2' ') 5 = + 12 1+2*(7-4)/3= Push(OP,*' ') 6 = +* 12 1+2*(7-4)/3= Push(OP,'(') 7 = +*( 12 1+2*(7-4)/3= Push(OD,7' ') 8 = +*( 127 1+2*(7-4)/3= Push(OP,'-') 续表 82 　数据结构原理与应用（第2 版） 步骤OP栈OD 栈读入字符主要操作 9 = +*(- 127 1+2*(7-4)/3= Push(OD,4' ') 10 = +*(- 1274 1+2*(7-4)/3= Pop(OP,'-'),Pop(OD,4),Pop(OD,7 ), Push(OD,7-4) 11 = +*( 123 1+2*(7-4)/3= Pop(OP,'(') 12 = +* 123 1+2*(7-4)/3= Pop(OP,'*'),Pop(OD,3),Pop(OD,2), Push(OD,2*3) 13 = + 16 1+2*(7-4)/3= Push(OP,/' ') 14 = +/ 16 1+2*(7-4)/3= Push(OD,3' ') 15 = +/ 163 1+2*(7-4)/3= Pop(OP,/' '),Pop(OD,3),Pop(OD,6), Push(OD,6/3) 16 = + 12 1+2*(7-4)/3= Pop(OP,'+'),Pop(OD,2),Pop(OD,1), Push(OD,1+2) 17 = 3 1+2*(7-4)/3= PoP(OP,'=') 算法描述与算法步骤如算法3.12所示。 算法3.12 【算法描述】【算法步骤】 0123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 float valExp(char*exp) { InitStack(OP); InitStack(OD); Push(OP,'='); ch=*exp++; GetTop(OP,e); while(ch!='='||e!='=') { if(!In(ch)) { Push(OD,ch); ch=*exp++; } else switch(Precede(e,ch)) { case '<': Push(OP,ch); ch=*exp++; break; case '=': Pop(OP,x); ch=*exp++; //表达式求值 //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 第3 章　栈和队列　 83 23 24 25 26 27 28 29 30 31 32 33 34 35 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; } //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)。 (2)中缀表达式转换为后缀表达式。后缀表达式是一种把所有运算符都放在操作数 后面的式子,因此被称为后缀表达式,这样就解决了运算优先级和括号的问题。计算机在 计算一个标准四则运算表达式时,一般都是先将中缀表达式转换为后缀表达式,然后进行 计算,如将中缀表达式1+2*(7-4)/3转换为后缀表达式1274- *3/+。 这是因为计算机处理后缀表达式求值问题是比较方便的。首先扫描后缀表达式,将 遇到的操作数暂存于一个操作数栈中,凡是遇到运算符,便从栈中弹出两个操作数并将运 算结果存于操作数栈中,直到对后缀表达式中最后一个操作数处理完,最后压入栈中的数 就是最后表达式的计算结果。 利用运算符的优先级,可以把中缀表达式转换为后缀表达式,其过程如下。 Step1.创建一个运算符栈,结束符入栈。 Step2.从左到右扫描读取表达式,执行下列运算,直至表达式结束符。 2.1 如果是操作数,则直接输出,读入下一个字符。 2.2 如果是运算符θ2,则把运算符栈栈顶运算符θ1 与θ2 进行比较。 2.2.1 若θ1<θ2,则θ2 入运算符栈,读入下一个字符。 2.2.2 若θ1=θ2,则退栈不输出;若退出的是右括号“)”,则读入下一个字符。 2.2.3 若θ1>θ2,则退栈并输出。 这里给出一个手动将中缀表达式转换为后缀表达式的方法,如表3-4所示。 表3-4 中缀表达式转换为后缀表达式 步 骤方法描述示例说明 1 写出中缀表达式1+2*(7-4)/3 续表 84 　数据结构原理与应用（第2 版） 步 骤方法描述示例说明 2 按运算先后把每一次运算用括号括起(1+((2*(7-4))/3)) 3 把运算符移至对应的括号的后面(1((2(74)-)*3)/)+ 4 去除括号1274- *3/+ (3)后缀表达式求值。将中缀表达式转换成对应的后缀表达式后,对表达式求值时 不需要再考虑运算符的优先级,只需要从左到右扫描一遍后缀表达式即可。后缀表达式 的求值过程为:从左到右读入后缀表达式,若读入的是一个操作数,则将其入操作数栈; 若读入的是一个运算符θ,则从操作数栈中连续出栈两个元素a、b(两个操作数),进行运 算bθa并把运算结果入操作数栈。重复上述过程直到表达式结束,操作数栈的栈顶元素 即为该后缀表达式的计算结果。 算法描述与算法步骤如算法3.13所示。 算法3.13 【算法描述】【算法步骤】 0123456789 10 11 12 13 14 15 16 17 18 float valPostExp(char *postexp) { InitStack(OD); ch=*postexp++; while(ch!='#') { if(ch 是操作数) Push(OD,ch); else if(ch 是运算符) { Pop(OD,a);Pop(OD,b); Push(OD,Operate(b,ch,a)); } ch=*postexp++; } 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进栈 第 3 章　栈和队列　 续表 85 步骤操作数栈说明 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 扫描结束 最后求得后缀表达式1274-*3/+的结果为3,与用中缀表达式求得的结果一 致,显然后缀表达式的求值要简单得多。 3.队列 2 3.1 队列的定义和特点 2. 队列(queue)和栈一样,也是一种操作受限的线性表。但与栈不同的是,队列是一种微课视频 先进先出的线性表。它只允许在一端进行插入操作,而在另一端进行删除操作。这里 , reafron 许插入的一端称为队尾(r), 允许删除的一端称为队头或队首(t)。向队列中插入(允) 新元素称为进队或入队(enqueue), 新元素入队后就成为新的队尾元素。从队列中删除 元 素称为出队(dequeue)或离队,元素出队后,其直接后继元素就成为新的队首元素。队 列 结构如图3-8所示 。 图3- 8 队列结构示意图 图3-9是一个队列的操作示意图,图中front指向队首元素位置,rear指向队尾元素 的下一个位置。图3-9(a)表示一个空队;图3-9(b)表示插入3个元素之后队列的状态; 图3-9(c)表示进行一次出队操作之后队列的状态;图3-9(d)表示再出队一次之后队列的 状态。 队列的操作与栈的操作类似,不同的是插入数据只能在队尾进行,删除数据只能在队 头进行。下面是队列的抽象数据类型Queue的定义。 86 　数据结构原理与应用（第2 版） 图3-9 队列的操作示意图 ADT Queue { 数据对象: D ={ai |ai ∈ElementSet, i =1, 2, …, n , n ≥0}。 数据关系: R ={|a i-1, ai ∈D , i =2, …, n },约定an 端为队尾,a 1 端为队头。 基本操作: InitQueue(&Q) //初始化队列 操作功能: 创建一个空的队列Q。 操作输出: 创建成功,返回true;不成功,返回false。 DestroyQueue(&Q) //销毁队列 操作功能: 释放队列Q 所占的存储空间。 操作输出: 无。 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,分别指示队头和队尾 元素的位置。顺序队列定义如下。 微课视频 第3 章　栈和队列　 87 template struct SqQueue { DT * base; //存储空间基地址 int front; //队头指针,指向队首元素① int rear; //队尾指针,指向队尾元素的后面 int queuesize; //队列容量 } 由上述定义可知下列语句的含义。 SqQueue
Q;表示声明一个顺序队列变量Q。 Q.front表示队头指针,Q.base[Q.front]表示队首元素,队不空时,即出队该元素。 Q.rear表示队尾指针,如果元素入队,队不满时,存入Q.base[Q.rear]处。 这里约定初始化创建空队列时,Q.front=Q.rear=0;元素入队时,若队列不满,新入 队元素送入Q.rear所指单元,队尾指针Q.rear增1;元素出队时,若队列不空,从Q.front 所指单元取出队头元素,队头指针Q.front增1(注意,这与现实生活中队列的队头元素出 队操作不同)。因此,在非空队列中,队头指针始终指向队首元素位置,队尾指针始终指向 队尾元素的下一个位置。 顺序队列结构及操作示意图如图3-10所示。 图3-10 顺序队列结构及操作示意图 在图3-10(d)中,由于当前队列分配的最大存储空间为6,如有新元素插入,则无法继 续入队,会产生数组越界引起程序非法操作的错误,此现象称为溢出。而实际上,此时队 列中还有可用空闲空间,因此这种现象称为假溢出。 为解决“假溢出”现象,使得数组中的存储空间可以充分利用起来,一种比较巧妙的方 法是假设存储队列的连续存储空间是头尾相接的环状结构,形成一个环形的顺序表,称为 循环队列(circularqueue)。 在循环队列中,头、尾指针以及队列元素之间的关系不变,只是头、尾指针“依环增1” 的操作需要通过模运算来实现。通过取模,循环队列的头指针和尾指针可以在顺序表空 间内以头尾相接的方式“循环”移动。循环队列头、尾指针的调整方法如下。 ● 队尾指针增1:Q.rear=(Q.rear+1)%Q.queuesize。 ● 队头指针增1:Q.front=(Q.front+1)%Q.queuesize。 ① 也有将队头元素指向队首元素前和将队尾元素指向队尾元素的,那出队元素与入队元素在位置上是有区 别的。 88 　数据结构原理与应用（第2 版） 如图3-10(d)所示,在元素f 入队前,rear的值为5。当元素f 入队后,通过模运算, Q.rear=(Q.rear+1)%6,因此得到rear的值为0,不会出现“假溢出”现象。若此后有元 素g 和h 相继入队,则队列空间满,此时Q.front=Q.rear。 如图3-10(c)所示,元素c 出队,则出现队空的状态,此时Q.front=Q.rear。 由此可见,引入循环队列后,出现了队空与队满的条件一样的情况。那么,如何区分 某一状态是队空还是队满呢? 为解决这一问题,采用的方法之一是牺牲一个存储单元,即 当队尾指针加1等于队首指针时判定为队满。因此,本书约定循环队列中队空和队满的 条件如下。 ● 队空:Q.front==Q.rear。 ● 队满:(Q.rear+1)%Q.queuesize==Q.front。 循环队列结构及操作示意图如图3-11所示。 图3-11 循环队列结构及操作示意图 类似地,根据ADTQueue中的基本操作定义设置操作参数类型和返回值后,循环队 列的基本操作的函数定义简述如表3-6所示。 表3-6 循环队列的基本操作的函数定义 序号函数定义功能说明 1 //初始化队列 boolInitQueue(SqQueue
&Q,intm) 创建容量为m 的空队列Q;创建成功, 返回true;否则,结束运行 2 //销毁队列 voidDestroyQueue(SqQueue
&Q) 释放队列Q所占内存空间 3 //取队头元素 boolGetHead(SqQueue
Q,DT &e) 队列Q 空,返回false;否则取队头元素 赋给e,返回true 4 //入队 boolEnQueue(SqQueue
&Q,DTe) 队列Q 满,返回false;否则在队尾插入 一个值为e的元素,返回true 5 //出队 boolDeQueue(SqQueue
&Q,DT &e) 队列Q 空,返回false;否则删除队头元 素,返回true 6 //测队长 intQueueLength(SqQueue
Q) 求队列Q的长度,即队中元素个数 7 //判队空 boolQueueEmpty(SqQueue
Q) 判断队列Q是否为空。如果是空队列, 返回true;否则,返回false 8 //清空队 voidClearQueue(SqQueue
&Q) 把队列Q变成空队列 循环队列的类型定义与前面给出的顺序队列的类型定义相同。循环队列部分基本操