C H A P T E R3 第3章 栈 和 队 列 栈和队列是两种常用的数据结构，它们的数据元素的逻辑关系也是线性关系，但在运算上不同于线性表。 本章主要学习要点如下。 (1) 栈、队列和线性表的异同，栈和队列抽象数据类型的描述方法。 (2) 顺序栈的基本运算算法的设计方法。 (3) 链栈的基本运算算法的设计方法。 (4) 顺序队的基本运算算法的设计方法。 (5) 链队的基本运算算法的设计方法。 (6) Python中的双端队列（deque）和优先队列（heapq）及其应用。 (7) 综合运用栈和队列解决一些复杂的实际问题。 3.1栈 本节先介绍栈的定义，然后讨论栈的存储结构和基本运算算法设计，最后通过两个综合实例说明栈的应用。 视频讲解 3.1.1栈的定义 先看一个示例，假设有一个田鼠洞，口径只能容纳一只田鼠，有若干只田鼠依次进洞，如图3.1所示，当到达洞底时，这些田鼠只能一只一只地按与原来进洞时相反的次序回退出洞，如图3.2所示。在这个例子中，田鼠洞就是一个栈，由于其口径只能容纳一只田鼠，所以不论洞中有多少只田鼠，它们只能是一只一只地排列，从而构成一种线性关系。再看看田鼠洞的主要操作，显然有进洞和出洞，进洞只能从洞口进，出洞也只能从洞口出。 抽象起来，栈是一种只能在同一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，可以用一个称为栈顶指针的位置指示器来指示。表的另一端称为栈底。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操 图3.1田鼠进洞的情况 图3.2田鼠出洞的情况 作通常称为退栈或出栈。 说明： 对于线性表，可以在中间和两端的任何地方插入和删除元素，而栈只能在同一端插入和删除元素。 栈的主要特点是“后进先出”或者“先进后出”，即后进栈的元素先出栈。每次进栈的元素都放在原当前栈顶元素之前成为新的栈顶元素，每次出栈的元素都是当前栈顶元素，栈顶元素出栈后次栈顶元素变成新的栈顶元素。栈也称为后进先出表。 抽象数据类型栈的定义如下： ADT Stack { 数据对象： D={ai | 0≤i≤n-1，n≥0} 数据关系： R={r} r={ | ai，ai+1∈D，i=0，…，n-2} 基本运算： empty()： 判断栈是否为空，若为空栈返回真，否则返回假。 push(e)： 进栈操作，将元素e插入栈中作为栈顶元素。 pop()： 出栈操作，返回栈顶元素。 gettop()： 取栈顶操作，返回当前的栈顶元素。 } 【例3.1】若元素进栈的顺序为1234，能否得到3142的出栈序列？ 解： 为了让3作为第一个出栈元素，1、2、3依次进栈，再出栈3，接着要么2出栈，要么4进栈后出栈，第2次出栈的元素不可能是1，所以得不到3142的出栈序列。 【例3.2】用S表示进栈操作，X表示出栈操作，若元素进栈 的顺序为1234，为了得到1342的出栈顺序，给出相应的S和X操作串。 解： 为了得到1342的出栈顺序，其操作过程是1进栈，1出栈，2进栈，3进栈，3出栈，4进栈，4出栈，2出栈，因此相应的S和X操作串为SXSSXSXX。 【例3.3】 设n个元素的进栈序列是1，2，3，…，n，通过一个栈得到的出栈序列是p1，p2，p3，…，pn，若p1=n，则pi(2≤i≤n)的值是什么？ 视频讲解 解： 当p1=n时，说明进栈序列的最后一个元素最先出栈，此时出栈序列只有一种， 即n，n-1，…，2，1，或p1=n，p2=n-1，…，pn-1=2，pn=1，也就是说pi+i=n+1，推出pi=n-i+1。 视频讲解 3.1.2栈的顺序存储结构及其基本运算算法的实现 由于栈中元素的逻辑关系与线性表的相同，因此可以借鉴线性表的两种存储结构来存储栈。 在采用顺序存储结构存储时，用列表data来存放栈中元素，称为顺序栈。顺序栈存储结构如图3.3所示，由于Python列表提供了一端动态扩展的功能，为此将data［0］端作为栈底，另外一端data［-1］作为栈顶，其中的元素个数len(data)恰好为栈中实际的元素个数。 图3.3顺序栈的示意图 图3.4所示为一个栈的动态示意图，图3.4(a)表示一个空栈，图3.4(b)表示元素a进栈以后的状态，图3.4(c)表示元素b、c、d进栈以后的状态，图3.4(d)表示出栈元素d以后的状态。 图3.4栈操作示意图 从中看到，顺序栈的四要素如下。 ① 栈空条件： len(data)==0或者not data。 ② 栈满条件： 由于data列表可以动态扩展，所以不必考虑栈满。 ③ 元素e进栈操作： 将e添加到栈顶处。 ④ 出栈操作： 删除栈顶元素并返回该元素。 说明： 顺序栈中的元素始终是向一端生长的，如果采用具有固定容量capacity的列表存放栈元素，需要增加一个指向栈顶元素的栈顶指针top，这样栈中实际的元素个数恰好为top+1，栈满条件改为top==capacity-1。在顺序栈中既可以将data［0］端作为栈底，也可以将data［-1］端作为栈底，但不能将data列表的中间位置作为栈底。 顺序栈类SqStack设计如下： class SqStack: def __init__(self):#构造方法 self.data=［］#存放栈中元素，初始为空 #栈的基本运算算法 顺序栈的基本运算算法如下。 1) 判断栈是否为空： empty() 若len(data)为0表示空栈。对应的算法如下： def empty(self):#判断栈是否为空 if len(self.data)==0: return True return False 2) 进栈： push(e) 元素进栈只能从栈顶进，不能从栈底或中间位置进栈，如图3.5所示。 图3.5元素进栈示意图 元素e进栈可以直接利用data列表的append()方法添加元素e(列表的append（）方法的时间复杂度为O(1))。对应的算法如下： def push(self,e):#元素e进栈 self.data.append(e) 3) 出栈： pop() 元素出栈只能从栈顶出，不能从栈底或中间位置出栈，如图3.6所示。 图3.6元素出栈示意图 在出栈中，当栈空时抛出异常，否则直接利用data列表的pop()方法出栈栈顶元素(列表的pop()方法的时间复杂度为O(1))。对应的算法如下： def pop(self):#元素出栈 assert not self.empty()#检测栈为空 return self.data.pop() 4) 取栈顶元素： gettop() 在栈不为空的条件下，返回栈顶元素data［len(data)-1］，不移动栈顶指针。对应的算法如下： def gettop(self):#取栈顶元素 assert not self.empty()#检测栈为空 return self.data［-1］ 从以上看出，栈的各种基本运算算法的时间复杂度均为O(1)。 3.1.3顺序栈的应用算法设计示例 【例3.4】设计一个算法，利用顺序栈判断用户输入的表达式中的括号是否配对(假设表达式中可能含有圆括号、方括号和花括号)，并用相关数据进行测试。 视频讲解 解： 因为各种括号的匹配过程遵循这样的原则，任何一个右括号与前面最靠近的未匹配的同类左括号进行匹配，所以采用一个栈来实现匹配过程。 用str字符串存放含有各种括号的表达式，建立一个字符顺序栈st，用i遍历str，当遇到各种类型的左括号时进栈，当遇到右括号时，若栈空或者栈顶元素不是匹配的左括号时返回False(中途就可以确定括号不匹配)，如图3.7所示，否则退栈一次继续判断。当str遍历完毕，栈st为空返回True，否则返回False。 图3.7用一个栈判断str中的括号是否匹配 对应的完整程序如下： from SqStack import SqStack#引用顺序栈SqStack def isMatch(str):#判断表达式的各种括号是否匹配的算法 st=SqStack() #建立一个顺序栈 i=0 while i="0" and ch<="9":#判定为数字 d+=ch#提取所有连续的数字字符 i+=1 if i(4,4) print("不存在迷宫路径") 程序执行结果 本程序的执行结果如下： 一条迷宫路径: ［1,1］ ［2,1］ ［3,1］ ［4,1］ ［4,2］ ［4,3］ ［3,3］ ［3,4］ ［4,4］ 该路径如图3.22所示(迷宫路径方块上的箭头指示路径中下一个方块的方位)，显然这个解不是最优解(即不是最短路径)。在后面使用队列求解时可以找出最短路径。 3.2队列 本节先介绍队列的定义，然后讨论队列的存储结构和基本运算算法设计，最后通过迷宫问题的求解说明队列的应用。 视频讲解 3.2.1队列的定义 同样先看一个示例，假设有一座独木桥，桥右侧有一群小兔子要过桥到桥左侧去，桥宽只能容纳一只兔子，那么这群小兔子怎么过桥呢？结论是只能一个接一个地过桥，如图3.23所示。在这个例子中，独木桥就是一个队列，由于其宽度只能容纳一只兔子，所以不论有多少只兔子，它们只能是一只一只地排列过桥，从而构成一种线性关系。再看看独木桥的主要操作，显然有上桥和下桥，上桥表示从桥右侧走到桥上，下桥表示离开桥。 图3.23一群小兔子过独木桥 归纳起来，队列(简称为队)是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，而在表的另一端进行删除。把进行插入的一端称作队尾(rear)，把进行删除的一端称作队头或队首(front)。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素； 从队列中删除元素称为出队或离队，元素出队后，其直接后继元素就成为队首元素。 由于队列的插入和删除操作分别是在表的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表。 抽象数据类型队列的定义如下： ADT Queue { 数据对象： D={ai | 0≤i≤n-1，n≥0} 数据关系： R={r} r={ | ai，ai+1∈D，i=0，…，n-2} 基本运算： empty()： 判断队列是否为空，若队列为空，返回真，否则返回假。 push(E e)： 进队，将元素e进队作为队尾元素。 pop()： 出队，从队头出队一个元素。 gethead()： 取队头，返回队头元素的值而不出队。 } 【例3.10】若元素的进队顺序为1234，能否得到3142的出队序列？ 解： 进队顺序为1234，则出队顺序只能是1234(先进先出)，所以不能得到3142的出队序列。 3.2.2队列的顺序存储结构及其基本运算算法的实现 由于队列中元素的逻辑关系与线性表的相同，所以可以借鉴线性表的两种存储结构来存储队列。 当队列采用顺序存储结构存储时，用列表data来存放队列中的元素，另外设置两个指针，队头指针为front(实际上是队头元素的前一个位置)，队尾指针为rear(正好是队尾元素的位置)。 为了简单起见，这里使用固定容量的列表data(容量为常量MaxSize)，如图3.24所示，队列中从队头到队尾为a0，a1，…，an-1。采用顺序存储结构的队列称为顺序队。 图3.24顺序队示意图 顺序队分为非循环队列和循环队列两种方式，下面先讨论非循环队列，并通过说明该类型队列的缺点引出循环队列。 视频讲解 1. 非循环队列 图3.25是一个非循环队列的动态变化示意图(MaxSize=5)。图3.25(a)表示一个空队； 图3.25(b)表示进队5个元素后的状态； 图3.25(c)表示出队一次后的状态； 图3.25(d)表示再出队4次后的状态。 图3.25队列操作的示意图 从中看到，初始时置front和rear均为-1(front==rear)，非循环队列的四要素如下。 ① 队空条件： front==rear，图3.25(a)和图3.25(d)满足该条件。 ② 队满(队上溢出)条件： rear==MaxSize-1(因为每个元素进队都让rear增1，当rear到达最大下标时不能再增加)，图3.25(d)满足该条件。 ③ 元素e进队操作： 先将队尾指针rear增1，然后将元素e放在该位置(进队的元素总是在尾部插入的)。 ④ 出队操作： 先将队头指针front增1，然后取出该位置的元素(出队的元素总是从头部出来的)。 非循环队列类SqQueue的定义如下： MaxSize=100#假设容量为100 class SqQueue:#非循环队列类 def __init__(self):#构造方法 self.data=［None］*MaxSize#存放队列中的元素 self.front=-1#队头指针 self.rear=-1#队尾指针 #队列的基本运算算法 在非循环队列中实现队列的基本运算算法如下。 1) 判断队列是否为空： empty() 若满足front==rear条件，返回True，否则返回False。对应的算法如下： def empty(self):#判断队列是否为空 return self.front==self.rear 2) 进队运算： push(e) 元素e进队只能从队尾插入，不能从队头或中间位置进队，仅改变队尾指针，如图3.26所示。进队操作是在队不满的条件下先将队尾指针rear增1，然后将元素e放到该位置处，否则抛出异常。对应的算法如下： def push(self,e):#元素e进队 assert not self.rear==MaxSize-1#检测队满 self.rear+=1 self.data［self.rear］=e 图3.26元素进队的示意图 3) 出队： pop() 元素出队只能从队头删除，不能从队尾或中间位置出队，仅改变队头指针，如图3.27所示。 图3.27元素出队的示意图 出队操作是在队列不为空的条件下将队头指针front增1，并返回该位置的元素值，否则抛出异常。对应的算法如下： def pop(self):#出队元素 assert not self.empty()#检测队空 self.front+=1 return self.data［self.front］ 4) 取队头元素： gethead() 与出队类似，但不需要移动队头指针front。对应的算法如下： def gethead(self):#取队头元素 assert not self.empty()#检测队空 return self.data［self.front+1］ 上述算法的时间复杂度均为O(1)。 视频讲解 2. 循环队列 在前面的非循环队列中，元素进队时队尾指针rear增1，元素出队时队头指针front增1，当进队MaxSize个元素后，满足设置的队满条件，即rear==MaxSize-1成立，此时即使出队若干元素，队满条件仍成立(实际上队列中有空位置)，这种队列中有空位置但仍然满足队满条件的上溢出称为假溢出。也就是说，非循环队列存在假溢出现象。为了克服非循环队列的假溢出，充分使用数组中的存储空间，可以把data数组的前端和后端连接起来，形成一个循环数组，即把存储队列元素的表从逻辑上看成一个环，称为循环队列(也称为环形队列)。 循环队列首尾相连，当队尾指针rear=MaxSize-1时，再前进一个位置就应该到达0位置，这可以利用数学上的求余运算(%)实现 。 ① 队首指针循环进1： front=(front+1) % MaxSize。 ② 队尾指针循环进1： rear=(rear+1) % MaxSize。 循环队列的队头指针和队尾指针均初始化为0，即front=rear=0。在进队元素和出队元素时，队头和队尾指针都循环前进一个位置。 那么循环队列的队满和队空的判断条件是什么呢？若设置队空条件是rear==front，如果进队元素的速度快于出队元素的速度，队尾指针很快就赶上了队头指针，此时可以看出循环队列队满时也满足rear==front，所以这种设置无法区分队空和队满。 实际上循环队列的结构与非循环队列相同，也需要通过front和rear标识队列状态，一般是采用它们的相对值 （即|front-rear|）实现的，若data数组的容量为 m，则队列的状态有m+1种，分别是队空、队中有1个元素、队中有2个元素、……、队中有 m个元素(队满)。而front和rear的取值范围均为0~m-1，这样|frontrear|只有m个值，显然m+1种状态不能直接用|frontrear|区分，因为必定有两种状态不能区分。为此让队列中最多只有m-1个元素，这样队列恰好只有m种状态，就可以通过front和rear的相对值区分所有状态了。 在规定队列中最多只有m-1个元素时，设置队空条件仍然是rear==front。当队列中有m-1个元素时一定满足(rear+1)%MaxSize==front。这样循环队列在初始时置front=rear=0，其四要素如下。 ① 队空条件： rear==front。 ② 队满条件： (rear+1)%MaxSize==front(相当于试探进队一次，若rear达到front，则认为队满了)。 ③ 元素e进队操作： rear=(rear+1)%MaxSize，将元素e放置在该位置。 ④ 元素出队操作： front=(front+1)%MaxSize，取出该位置的元素。 图3.28说明了循环队列的几种状态，这里假设MaxSize等于5。图3.28(a)为空队，此时front=rear=0； 图3.28(b)表示队列中有3个元素，当进队元素d后，队中有4个元素，此时满足队满的条件。 图3.28循环队列进队和出队操作示意图 循环队列类CSqQueue的定义如下： MaxSize=100#全局变量，假设容量为100 class CSqQueue:#循环队列类 def __init__(self):#构造方法 self.data=［None］*MaxSize#存放队列中的元素 self.front=0#队头指针 self.rear=0#队尾指针 #队列的基本运算算法 在这样的循环队列中，实现队列的基本运算算法如下。 1) 判断队列是否为空： empty() 若满足front==rear条件，返回True，否则返回False。对应的算法如下： def empty(self):#判断队列是否为空 return self.front==self.rear 2) 进队： push(e) 在队列不满的条件下，先将队尾指针rear循环增1，然后将元素e放到该位置处，否则抛出异常。对应的算法如下： def push(self,e):#元素e进队 assert (self.rear+1)%MaxSize!=self.front #检测队满 self.rear=(self.rear+1)%MaxSize self.data［self.rear］=e 3) 出队： pop() 在队列不为空的条件下将队头指针front循环增1，并返回该位置的元素值，否则抛出异常。对应的算法如下： def pop(self):#出队元素 assert not self.empty()#检测队空 self.front=(self.front+1)%MaxSize return self.data［self.front］ 4) 取队头元素： gethead() 与出队类似，但不需要移动队头指针front。对应的算法如下： def gethead(self):#取队头元素 assert not self.empty()#检测队空 head=(self.front+1)%MaxSize#求队头元素的位置 return self.data［head］ 上述算法的时间复杂度均为O(1)。 3.2.3循环队列的应用算法设计示例 【例3.11】在CSqQueue循环队列类中增加一个求元素个数的算法size()。对于一个整数循环队列qu，利用队列基本运算和size()算法设计进队和出队第k(k≥1，队头元素的序号为1)个元素的算法。 视频讲解 解： 在前面的循环队列中，队头指针front指向队中队头元素的前一个位置，队尾指针rear指向队中的队尾元素，可以求出队中元素个数=(rear-front+MaxSize)%MaxSize。为此在CSqQueue循环队列类中增加size()算法如下： def size(self):#返回队中元素个数 return ((self.rear-self.front+MaxSize)%MaxSize) 在队列中并没有直接取k(k≥1)个元素的基本运算，进队第k个元素e的算法思路是出队前k-1个元素，边出边进，再将元素e进队，将剩下的元素边出边进。该算法如下： def pushk(qu,k,e):#进队第k个元素e n=qu.size() if k<1 or k>n+1: return False#参数k错误返回False if k<=n: for i in range(1,n+1):#循环处理队中的所有元素 if i==k: qu.push(e)#将e元素进队到第k个位置 x=qu.pop()#出队元素x qu.push(x)#进队元素x else: qu.push(e)#k=n+1时直接进队e return True 出队第k(k≥1)个元素e的算法思路是出队前k-1个元素，边出边进，再出队第k个元素e，e不进队，最后将剩下的元素边出边进。该算法如下： def popk(qu,k):#出队第k个元素 n=qu.size() assert k>=1 and k<=n#检测参数k错误 for i in range(1,n+1):#循环处理队中的所有元素 x=qu.pop()#出队元素x if i!=k: qu.push(x)#将非第k个元素进队 else: e=x#取第k个出队的元素 return e 【例3.12】对于循环队列来说，如果知道队头指针和队中元素个数，则可以计算出队尾指针。也就是说，可以用队中元素个数代替队尾指针。设计出这种循环队列的判队空、进队、出队和取队头元素的算法。 视频讲解 解： 本例的循环队列包含data数组、队头指针front和队中元素个数count，可以由front和count求出队尾位置，公式如下。 rear1=(self.front+self.count)%MaxSize 初始时front和count均置为0。队空条件为count==0； 队满条件为count==MaxSize； 元素e进队操作是先根据上述公式求出队尾指针rear1，将rear1循环增1，然后将元素e放置在rear1处； 出队操作是先将队头指针循环增1，然后取出该位置的元素。设计本例的循环队列类CSqQueue1如下： MaxSize=100#全局变量，假设容量为100 class CSqQueue1:#本例的循环队列类 def __init__(self): #构造方法 self.data=［None］*MaxSize#存放队列中的元素 self.front=0#队头指针 self.count=0#队中元素个数 #队列的基本运算算法 def empty(self):#判断队列是否为空 return self.count==0 def push(self,e):#元素e进队 rear1=(self.front+self.count)%MaxSize assert self.count!=MaxSize#检测队满 rear1=(rear1+1) % MaxSize self.data［rear1］=e self.count+=1#元素个数增1 def pop(self):#出队元素 assert not self.empty()#检测队空 self.count-=1#元素个数减1 self.front=(self.front+1)%MaxSize#队头指针循环增1 return self.data［self.front］ def gethead(self):#取队头元素 assert not self.empty()#检测队空 head=(self.front+1)%MaxSize#求队头元素的位置 return self.data［head］ 说明： 本例设计的循环队列中最多可保存MaxSize个元素。 从上述循环队列的设计看出，如果将data数组的容量改为可以扩展的，在队满时新建更大容量的数组newdata后，不能像顺序表、顺序栈那样简单地将data中的元素复制到newdata中，需要按队列操作，将data中的所有元素出队后进队到newdata中，这里不再详述。 3.2.4队列的链式存储结构及其基本运算算法的实现 队列的链式存储结构也是通过由结点构成的单链表实现的，此时只允许在单链表的表首进行删除操作(出队)和在单链表 的表尾进行插入操作(进队)， 视频讲解 这里的单链表是不带头结点的，需要使用两个指针 （即队首指针front和队尾指针rear）来标识，front指向队首结点，rear指向队尾结点。用于存储队列的单链表简称为链队。 链队的存储结构如图3.29所示，链队中存放元素的结点类LinkNode定义如下： class LinkNode:#链队结点类 def __init__(self,data=None):#构造方法 self.data=data #data属性 self.next=None#next属性 图3.29链队存储结构示意图 设计链队类LinkQueue如下： class LinkQueue:#链队类 def __init__(self):#构造方法 self.front=None#队头指针 self.rear=None#队尾指针 #队列的基本运算算法 图3.30说明了一个链队的动态变化过程。图3.30(a)是链队的初始状态，图3.30(b)是进队3个元素后的状态，图3.30(c)是出队两个元素后的状态。 图3.30一个链队的动态变化过程 从图3.30中看到，初始时置front=rear=None。链队的四要素如下。 ① 队空条件： fronr=rear==None，不妨仅以front==None作为队空条件。 ② 队满条件： 由于只有在内存溢出时才出现队满，通常不考虑这样的情况。 ③ 元素e进队操作： 在单链表的尾部插入一个存放e的s结点，并让队尾指针指向它。 ④ 出队操作： 取出队首结点的data值并将其从链队中删除。 对应队列的基本运算算法如下。 1) 判断队列是否为空： empty() 链队的front为空表示队列为空，返回True，否则返回False。对应的算法如下： def empty(self):#判断队列是否为空 return self.front==None 2) 进队： push(e) 创建存放元素e的结点s。若原队列为空，则将front和rear均指向s结点，否则将s结点链接到单链表的末尾，并让rear指向它。对应的算法如下： def push(self,e):#元素e进队 s=LinkNode(e)#新建结点s if self.empty():#原链队为空 self.front=self.rear=s else:#原链队不为空 self.rear.next=s#将s结点链接到rear结点的后面 self.rear=s 3) 出队： pop() 若原队为空，抛出异常； 若队中只有一个结点(此时front和rear都指向该结点)，取首结点的data值赋给e，并删除它，即置front=rear=None； 否则说明链队中有多个结点，取首结点的data值赋给e，并删除它。最后返回e。对应的算法如下： def pop(self):#出队操作 assert not self.empty()#检测队空 if self.front==self.rear:#原链队只有一个结点 e=self.front.data#取首结点值 self.front=self.rear=None#置为空队 else:#原链队有多个结点 e=self.front.data#取首结点值 self.front=self.front.next#front指向下一个结点 return e 4) 取队头元素： gethead() 与出队类似，但不需要删除首结点。对应的算法如下： def gethead(self):#取队头元素 assert not self.empty()#检测队空 e=self.front.data#取首结点值 return e 上述算法的时间复杂度均为O(1)。 3.2.5链队的应用算法设计示例 视频讲解 【例3.13】采用链队求解第2章例2.16的约瑟夫问题。 解： 先定义一个链队qu，对于 (n，m)约瑟夫问题，依次将1~n进队。循环n次出列n个小孩： 依次出队m-1次，将所有出队的元素立即进队(将他们从队头出队后插入队尾)，再出队第m个元素并且输出(出列第m个小孩)。 对应的程序如下： from LinkQueue import LinkQueue def Jsequence(n,m):#求约瑟夫序列 qu=LinkQueue()#定义一个链队 for i in range(1,n+1):#进队编号为1~n的n个小孩 qu.push(i) for i in range(1,n+1):#共出列n个小孩 j=1 while j<=m-1:#出队m-1个小孩，并将他们进队 qu.push(qu.pop()) j+=1 x=qu.pop() #出队第m个小孩 print(x,end=' ') print() #主程序 print() print(" 测试1: n=6,m=3") print(" 出列顺序:",end=' ') Jsequence(6,3) print(" 测试2: n=8,m=4") print(" 出列顺序:",end=' ') Jsequence(8,4) 上述程序的执行结果如下： 测试1: n=6,m=3 出列顺序: 3 6 4 2 5 1 测试2: n=8,m=4 出列顺序: 4 8 5 2 1 3 7 6 说明： 与第2章例2.16相比，这里是用带首尾结点指针的链队替代了循环单链表。 视频讲解 3.2.6Python中的双端队列 双端队列是在队列的基础上扩展而来的，其示意图如图3.31所示。双端队列与队列一样，元素的逻辑关系也是线性关系，但队列只能在一端进队，在另外一端出队，而双端队列可以在两端进行进队和出队操作，具有队列和栈的特性，因此使用更加灵活。 图3.31双端队列示意图 Python提供了一个集合模块collections，里面封装了多个集合类，其中包括deque，即双端队列(doubleended queue)。 1. 创建双端队列 创建一个双端队列的基本方法如下。 1) 创建一个空双端队列 使用的语法格式如下： qu=deque() 此时qu为空，它是一个可以动态扩展的双端队列。 2) 创建一个固定长度的双端队列 使用的语法格式如下： qu=deque(maxlen=N) 此时qu为空，但固定长度为N，当有新的元素加入而双端队列已满时会自动移除最老的那个元素。 3) 由一个列表元素创建一个双端队列 使用的语法格式如下： qu=deque(L) 此时qu包含列表L中的元素。 2. 双端队列的函数 deque没有提供判空方法，可以使用内置函数len()求其他的元素个数，通过len(qu)==0来判断双端队列是否为空，其时间复杂度为O(1)。 3. 双端队列的方法 deque提供的主要方法如下。 ① deque.clear()： 清除双端队列中的所有元素。 ② deque.append(x)： 在双端队列的右端添加元素x，时间复杂度为O(1)。 ③ deque.appendleft(x)： 在双端队列的左端添加元素x，时间复杂度为O(1)。 ④ deque.pop()： 在双端队列的右端出队一个元素，时间复杂度为O(1)。 ⑤ deque.popleft()： 在双端队列的左端出队一个元素，时间复杂度为O(1)。 ⑥ deque.remove(x)： 在双端队列中删除首个和x匹配的元素(从左端开始匹配的)，如果没有找到抛出异常，其时间复杂度为O(n)。 ⑦ deque.count(x)： 计算双端队列中元素为x的个数，时间复杂度为O(n)。 ⑧ deque.extend(L)： 在双端队列的右端添加列表L的元素。例如，qu为空，L=［1，2，3］，执行后qu从左向右为［1，2，3］。 ⑨ deque.extendleft(L)： 在双端队列的左端添加列表L的元素。例如，qu为空，L=［1，2，3］，执行后qu从左向右为［3，2，1］。 ⑩ deque.reverse()： 把双端队列里的所有元素中的逆置。 deque.rotate(n)： 双端队列的移位操作，如果n是正数，则队列中的所有元素向右移动n个位置； 如果是负数，则队列中的所有元素向左移动n个位置。 4. 用双端队列实现栈 栈只在一端进行进栈和出栈操作，若定义st=queue()，也就是用deque实现栈，其两种方式如下： ① 以左端作为栈底(左端保持不动)，右端作为栈顶(右端动态变化，st［-1］为栈顶元素)，栈操作在右端进行，则用append()作为进栈方法，pop()作为出栈方法； ② 以右端作为栈底(右端保持不动)，左端作为栈顶(左端动态变化，st［0］为栈顶元素)，栈操作在左端进行，则用appendleft()作为进栈方法，popleft()作为出栈方法。 例如，以下程序为采用方法①将deque作为栈的使用方法。 from collections import deque#引用deque st=deque() st.append(1) st.append(2) st.append(3) while len(st)>0: print(st.pop(),end=' ')#输出： 3 2 1 print() 5. 用双端队列实现普通队列 普通队列只在一端进行进队操作，在另外一端进行出队操作，若定义qu=queue()，也就是用deque实现队列，其两种方式如下： ① 以左端作为队头(出队端)，右端作为队尾(进队端)，则用popleft()作为出队方法，append()作为进队方法。在队列非空时qu［0］为队头元素，qu［-1］为队尾元素； ② 以右端作为队头(出队端)，左端作为队尾(进队端)，则用pop()作为出队方法，appendleft()作为进队方法。在队列非空时qu［-1］为队头元素，qu［0］为队尾元素。 例如，以下程序为采用方法①将deque作为普通队列的使用方法。 from collections import deque qu=deque() qu.append(1) qu.append(2) qu.append(3) while len(qu)>0: print(qu.popleft(),end=' ')#输出： 1 2 3 print() 3.2.7队列的综合应用 本节通过用队列求解迷宫问题来讨论队列的应用。 视频讲解 问题描述 参见3.1.6节。 迷宫的数据组织 参见3.1.6节。 设计运算算法 用队列求迷宫路径的思路是从入口开始试探，当试探到一个方块b时，若为出口，输出对应的迷宫路径并返回，否则找其所有相邻可走方块，假设找到的顺序为 b1，b2，…，bk，称b方块为这些方块的前驱方块，称这些方块为b方块的后继方块，则按b1，b2，…，bk的顺序试探每一个方块。为此用一个队列存放这些方块，这里采用deque实现队列，定义如下： qu=deque()#定义一个队列 当找到出口后如何求出迷宫路径呢？由于每个试探的方块可能有多个后继方块，但一定只有唯一的前驱方块(除了入口方块外)，为此设置队列中的元素类型如下： class Box:#方块类 def __init__(self,i1,j1):#构造方法 self.i=i1#方块的行号 self.j=j1#方块的列号 self.pre=None#前驱方块 假设当前试探的方块位置是(i，j)，对应的队列元素(Box对象)为b，如图3.32所示，一次性 找它所有的相邻可走方块，假设有4个相邻可走方块(实际上最多3个)，则这4个相邻可走的方块均进队，同时置每个bi的pre属性（即前驱方块）为b，即bi.pre=b。所以找到出口后，从出口通过pre属性回退到入口即找到一条迷宫路径。 图3.32当前方块b和相邻方块 查找一条从(xi，yi)到(xe，ye)的迷宫路径的过程是首先建立入口方块(xi，yi)的Box对象b，将b进队，在队列qu不为空时循环： 出队一次，称该出队的方块b为当前方块，做如下处理。 ① 如果b是出口，则从b出发沿着pre属性回退到出口，找到一条迷宫逆路径path，反向输出该路径后返回True。 ② 否则，按顺时针方向一次性查找方块b的4个方位中的相邻可走方块，每个相邻可走方块均建立一个Box对象b1，置b1.pre=b，将b1进qu队列。与用栈求解一样，一个方块进队后，将其迷宫值置为-1，以避免回过来重复搜索。 如果队空都没有找到出口，表示不存在迷宫路径，返回False。 在图3.17所示的迷宫图中求从入口(1，1)到出口(4，4)迷宫路径的搜索过程如图3.33所示，图中带“×”的方块表示没有相邻可走方块，每个方块旁的数字表示搜索顺序，找到出口后，通过虚线（即pre）找到一条迷宫逆路径。 图3.33用队列求从(1，1)到(4，4)迷宫路径的搜索过程 用队列求解迷宫问题的mgpath()算法如下： def mgpath(xi,yi,xe,ye):#求(xi,yi)到(xe,ye)的一条迷宫路径 global mg#迷宫数组为全局变量 dx=［-1,0,1,0］#x方向的偏移量 dy=［0,1,0,-1］#y方向的偏移量 qu=deque()#定义一个队列 b=Box(xi,yi)#建立入口结点b qu.appendleft(b)#结点b进队 mg［xi］［yi］=-1#进队方块置为-1 while len(qu)!=0:#队不空时循环 b=qu.pop()#出队一个方块b if b.i==xe and b.j==ye:#找到了出口,输出路径 p=b#从b出发回推导出迷宫路径并输出 path=［］#path存放逆路径 while p!=None:#找到入口为止 path.append("［"+str(p.i)+","+str(p.j)+"］") p=p.pre for i in range(len(path)-1,-1,-1):#反向输出path得到正向路径 print(path［i］,end=' ') return True#找到一条路径时返回True for di in range(4):#循环扫描每个相邻方位的方块 i,j=b.i+dx［di］,b.j+dy［di］#找b的di方位的相邻方块(i,j) if mg［i］［j］==0: #找相邻可走方块 b1=Box(i,j)#建立后继方块结点b1 b1.pre=b#设置其前驱方块为b qu.appendleft(b1)#b1进队 mg［i］［j］=-1#进队方块置为-1 return False#未找到任何路径时返回False 设计主程序 设计以下主程序用于求图3.17所示的迷宫图中从(1，1)到(4，4)的一条迷宫路径： xi,yi=1,1 xe,ye=4,4 print("一条迷宫路径:",end=' ') if not mgpath(xi,yi,xe,ye):#(1,1)>(4,4) print("不存在迷宫路径") print() 程序执行结果 本程序的执行结果如下： 一条迷宫路径: ［1,1］ ［2,1］ ［3,1］ ［4,1］ ［4,2］ ［4,3］ ［4,4］ 该路径如图3.34所示，迷宫路径上方块的箭头表示其前驱方块的方位。显然这个解是最优解，也就是最短路径。至于为什么用栈求出的迷宫路径不一定是最短路径，而用队列求出的迷宫路径一定是最短路径，该问题将在第7章中说明。 图3.34用队列求出的一条迷宫路径 视频讲解 3.2.8优先队列 所谓优先队列，就是指定队列中元素的优先级，按优先级越大越优先出队，而普通队列中按进队的先后顺序出队，可以看成进队越早越优先。实际上优先队列就是第9章中讨论的堆，根按照大小分为大根堆和小根堆，大根堆的元素越大越优先出队(即元素越大优先级越大)，小根堆的元素越小越优先出队(即元素越小优先级越大)。 在Python中提供了heapq模块，其中包含的堆的基本操作方法用于创建堆，但只能创建小根堆。其主要方法如下。 ① heapq.heapify(list)： 把列表list调整为堆。 ② heapq.heappush(heap，item)： 向堆heap中插入元素item(进队item元素)，该方法会维护堆的性质。 ③ heapq.heappop(heap)： 从堆heap中删除最小元素并且返回该元素值。 ④ heapq.heapreplace(heap，item)： 从堆heap中删除最小元素并且返回该元素值，同时将item插入并且维护堆的性质。它优于调用函数heappop(heap)和heappush(heap，item)。 ⑤ heapq.heappushpop(heap, item)： 把元素item插入堆heap中，然后从heap中删除最小元素并且返回该元素值。它优于调用函数heappush(heap，item)和heappop(heap)。 ⑥ heapq.nlargest(n，iterable［，key］)： 返回迭代数据集合iterable中第n大的元素，可以指定比较的key。它比通常计算多个list第n大的元素的方法更方便、快捷。 ⑦ heapq.nsmallest(n,iterable［, key］)： 返回迭代数据集合iterable中第n小的元素，可以指定比较的key。它比通常计算多个list第n小的元素的方法更方便、快捷。 ⑧ heapq.merge(*iterables)： 把多个堆合并，并返回一个迭代器。 使用heapq创建优先队列有两种方式，一种是使用一个空列表，然后使用heapq.heappush()添加元素； 另一种是使用heap.heapify(list)方法将list列表转换成堆结构。 例如，定义一个heapq列表，将其调整为小根堆，调用一系列heapq方法如下： import heapq heap=［6,5,4,1,8］#定义一个列表heap heapq.heapify(heap)#将heap列表调整为堆 print(heap)#输出： ［1,5,4,6,8］ heapq.heappush(heap,3)#进队3 print(heap)#输出： ［1,5,3,6,8,4］ print(heapq.heappop(heap))#输出： 1 print(heap)#输出： ［3,5,4,6,8］ print(heapq.heapreplace(heap,2))#输出： 3(出队最小元素，再插入2) print(heap)#输出： ［2,5,4,6,8］ print(heapq.heappushpop(heap,1))#输出： 1(插入1，再出队最小元素) print(heap)#输出： ［2,5,4,6,8］ 由于heapq不支持大根堆，那么如何创建大根堆呢？对于数值类型，一个最大数的相反数就是最小数，可以通过对数值取反，仍然创建小根堆的方式来获取最大数。 例如，一个列表list的元素形如“［年龄，姓名］”，假设所有的年龄都不相同，需要求最大的年龄及对应的姓名。 将所有年龄取相反数，建立相应的小根堆，出队最小元素s，其-s［0］即为最大的年龄，s［1］为对应的姓名。对应的程序及其输出结果如下： import heapq list=［［20,"Mary"］,［24,"John"］,［21,"Smith"］］#定义一个列表 heap=［］ for i in range(len(list)): heap.append(［-list［i］［0］,list［i］［1］］) print(heap)#输出： ［［-20, 'Mary'］, ［-24, 'John'］, ［-21, 'Smith'］］ heapq.heapify(heap)#将heap列表调整为堆 print(heap)#输出： ［［-24, 'John'］, ［-20, 'Mary'］, ［-21, 'Smith'］］ s=heapq.heappop(heap)#出队最大者 print("年龄最大为%d岁，是%s" %(-s［0］,s［1］))#输出： 年龄最大为24岁，是John 3.3练习题 1. 简述线性表、栈和队列的异同。 2. 有5个元素，其进栈次序为abcde，在各种可能的出栈次序中，以元素c、d最先出栈(即c第一个且d第二个出栈)的次序有哪几个？ 3. 假设以I和O分别表示进栈和出栈操作，则初态和终态为栈空的进栈和出栈的操作序列可以表示为仅由I和O组成的序列，称可以实现的栈操作序列为合法序列(例如IIOO为合法序列，IOOI为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则。 4. 什么叫“假溢出”？如何解决假溢出？ 5. 假设循环队列的元素存储空间为data［0..m-1］，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置 (例如data［0..5］，队头元素为data［2］，则front=2，队尾元素为data［3］，则rear=4)，则在少用一个元素空间的前提下表示队空和队满的条件各是什么？ 6. 在算法设计中，有时需要保存一系列临时数据元素，如果先保存的后处理，应该采用什么数据结构存放这些元素？如果先保存的先处理，应该采用什么数据结构存放这些元素？ 7. 给定一个字符串str，设计一个算法采用顺序栈判断str是否为形如“序列1@序列2”的合法字符串，其中序列2是序列1的逆序，在str中恰好只有一个@字符。 8. 设计一个算法利用一个栈将一个循环队列中的所有元素倒过来，队头变队尾，队尾变队头。 9. 对于给定的正整数n(n>2)，利用一个队列输出n阶杨辉三角形，5阶杨辉三角形如图3.35(a)所示，其输出结果如图3.35(b)所示。 图3.355阶杨辉三角形及其输出结果 10. 有一个整数数组a，设计一个算法将所有偶数位元素移动到所有奇数位元素的前面，要求它们的相对次序不改变。例如，a={1，2，3，4，5，6，7，8}，移动后a={2，4，6，8，1，3，5，7}。 11. 设计一个循环队列，用data［0..MaxSize-1］存放队列元素，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空(False)或可能满(True)，这样加上front==rear可以作为队空或队满的条件，要求设计队列的相关基本运算算法。 3.4上机实验题 3.4.1基础实验题 1. 设计整数顺序栈的基本运算程序，并用相关数据进行测试。 2. 设计整数链栈的基本运算程序，并用相关数据进行测试。 3. 设计整数循环队列的基本运算程序，并用相关数据进行测试。 4. 设计整数链队的基本运算程序，并用相关数据进行测试。 3.4.2应用实验题 1. 一个b序列的长度为n，其元素恰好是1~n的某个排列，编写一个实验程序判断b序列是否是以1，2，…，n为进栈序列的出栈序列，如果不是，输出相应的提示信息； 如果是，输出由该进栈序列通过一个栈得到b序列的过程。 2. 改进用栈求解迷宫问题的算法，累计如图3.17所示的迷宫的路径条数，并输出所有迷宫路径。 3. 括号匹配问题： 在某个字符串(长度不超过100)中有左括号、右括号和大/小写字母，规定(与常见的算术表达式一样)任何一个左括号都从内到外与它右边距离最近的右括号匹配。编写一个实验程序，找到无法匹配的左括号和右括号，输出原来的字符串，并在下一行标出不能匹配的括号，不能匹配的左括号用“$”标注，不能匹配的右括号用“?”标注。例如，输出样例如下： ( (ABCD(x) $$ )(rttyy())sss)( ??$ 4. 修改《教程》3.2节中的循环队列算法，使其容量可以动态扩展， 当进队时，若元素当前容量满时按两倍扩大容量； 当出队时，若当前容量大于初始容量并且元素的个数只有当前容量的 1/4，缩小当前容量为一半。通过测试数据说明队列容量变化的情况。 5. 采用不带头结点只有一个尾结点指针rear的循环单链表存储队列，设计出这种链队的进队、出队、判队空和求队中元素个数的算法。 图3.36一个迷宫的示意图 6. 对于如图3.36所示的迷宫图，编写一个实验程序，先采用队列求一条最短迷宫路径长度minlen(路径中经过的方块个数)，再采用栈求所有长度为minlen的最短迷宫路径。在搜索所有路径时进行这样的优化操作： 当前路径尚未到达出口但长度超过minlen ，便结束该路径的搜索。 视频讲解 3.5LeetCode在线编程题 1. LeetCode20——有效的括号 问题描述： 给定一个只包括 '('、')'、'{'、'}'、'［'、'］' 的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。例如，输入字符串"()"，输出为True； 输入字符串"(［)］"，输出为False。要求设计满足题目条件的如下方法： defisValid(self，s: str) > bool: 视频讲解 2. LeetCode150——逆波兰表达式求值 问题描述： 根据逆波兰表示法求表达式的值，有效的运算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。假设给定的逆波兰表达式总是有效的，即表达式总会得出有效数值且不存在除数为0的情况。其中整数除法只保留整数部分。例如，输入［"2"，"1"，"+"，"3"，"*"］，输出结果为9； 输入［"4"，"13"，"5"，"/"，"+"］，输出结果为6。要求设计满足题目条件的如下方法： def evalRPN(self，tokens: List［str］) > int: 视频讲解 3. LeetCode71——简化路径 问题描述： 以UNIX风格给出一个文件的绝对路径，并且简化它 ，也就是说将其转换为规范路径。在UNIX风格的文件系统中，一个点(.)表示当前目录本身， 两个点(..)表示将目录切换到上一级(指向父目录)，两者都可以是复杂相对路径的组成部分。 注意，返回的规范路径必须始终以斜杠（/）开头，并且两个目录名之间只有一个斜杠/，最后一个目录名(如果存在)不能以/结尾。此外，规范路径必须是表示绝对路径的最短字符串。例如，输入字符串"/home/"，输出结果为"/home"，输入字符串"/a//b////c/d//././/.."，输出结果为"/a/b/c"。要求设计满足题目条件的如下方法： def simplifyPath(self，path: str) > str: 4. LeetCode51——n皇后 问题描述： n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的 n皇后问题的棋子放置方案，在该方案中'Q'和'.'分别代表了皇后和空位。例如输入4，输出(共两个解法)结果如下： 视频讲解 ［ ［".Q.."，#解法 1 "...Q"， "Q..."， "..Q."］， ［"..Q."，#解法 2 "Q..."， "...Q"， ".Q.."］ ］ 要求设计满足题目条件的如下方法： def solveNQueens(self，n: int) > List［List［str］］: 5. LeetCode622——设计循环队列 问题描述： 循环队列是一种线性数据结构，其操作表现基于 FIFO(先进先出)原则，并且队尾被连接在队首之后以形成一个循环，它也被称为“环形缓冲器”。循环队列的一个好处是用户可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了就不能插入下一个元素，即使在队列的前面仍有空间，但是在使用循环队列时可以使用这些空间去存储新的值。 设计应该支持如下操作。 ① MyCircularQueue(k)： 构造器，设置队列长度为k。 ② Front()： 从队首获取元素。如果队列为空，返回-1。 ③ Rear()： 获取队尾元素。如果队列为空，返回-1。 ④ enQueue(value)： 向循环队列插入一个元素。如果成功插入，则返回True。 ⑤ deQueue()： 从循环队列中删除一个元素。如果成功删除，则返回True。 ⑥ isEmpty()： 检查循环队列是否为空。 ⑦ isFull()： 检查循环队列是否已满。 视频讲解 例如： MyCircularQueue circularQueue=new MycircularQueue(3) #设置长度为3 circularQueue.enQueue(1)#返回True circularQueue.enQueue(2)#返回True circularQueue.enQueue(3)#返回True circularQueue.enQueue(4)#返回False，队列已满 circularQueue.Rear()#返回3 circularQueue.isFull()#返回True circularQueue.deQueue() #返回True circularQueue.enQueue(4)#返回True circularQueue.Rear()#返回4 提示： 所有的值都在0~1000范围内，操作数将在1~1000范围内，不要使用内置的队列库。 6. LeetCode119——杨辉三角II 问题描述： 给定一个非负索引k，其中k≤33，返回杨辉三角的第k行。在杨辉三角中，每个数是它左上方和右上方的数的和。例如输入整数3，输出为［1，3，3，1］。 要求设计满足题目条件的如下方法： 视频讲解 def getRow(self，rowIndex: int) > List［int］: 7. LeetCode347——前k个高频元素 问题描述： 给定一个非空的整数数组，返回其中出现频率前k个高的元素。例如，输入nums=［1，1，1，2，2，3］， k=2，输出结果为［1，2］； 输入nums=［1］，k=1，输出结果为［1］。 可以假设给定的k总是合理的，且1≤k≤数组中不相同的元素的个数。另外算法的时间复杂度必须优于 O(nlog2n)，n是数组的大小。要求设计满足题目条件的如下方法： 视频讲解 def topKFrequent(self，nums: List［int］，k: int) > List［int］: 8. LeetCode23——合并k个排序链表 问题描述： 合并k个排序链表，返回合并后的排序链表。分析和描述算法的复杂度。例如，输入如下： 视频讲解 ［ 1>4>5， 1>3>4， 2>6 ］ 输出的链表为1>1>2>3>4>4>5>6。要求设计满足题目条件的如下方法： def mergeKLists(self，lists: List［ListNode］) > ListNode: