《数据结构Python 语言描述》 第3章

第3章栈和队列签到扫码下载文旌课堂APP扫码签到（202X.X.XXXX:00至202X.X.XXXX:10）签到方式教师通过“文旌课堂APP”生成签到二维码，并设置签到时间，学生通过“文旌课堂APP”扫描“签到二维码”进行签到。。栈和队列本章导读栈和队列是两种操作受限的线性表，故栈和队列的基本操作是线性表操作的子集，因此也称栈和队列是限定性的数据结构。栈和队列在程序设计中的应用十分广泛，本章就来介绍这两种数据结构的定义、基本操作，以及它们的存储结构及其基本操作的实现。此外，还简单介绍递归的定义和调用，以及递归过程和递归栈。

第3章栈和队列知识目标

第3章 理解栈和队列的定义及其基本操作。 掌握栈的顺序和链式两种存储结构及其基本操作的实现。 理解递归的定义并掌握递归的调用方法。 掌握队列的顺序和链式两种存储结构及其基本操作的实现。栈和队列技能目标

第3章 能使用栈和队列解决程序设计中的问题。 能使用递归方法解决实际问题，并写出优雅、简洁的代码。栈和队列素质目标

第3章 理解队列的原则，养成遵守规则的良好习惯。 理解递归的核心思想，学会用“分治法”解决实际生活中遇到的问题。Content第3章栈的顺序存储栈概述栈的链式存储栈与递归队列概述队列的顺序存储队列的链式存储3.1栈概述第3章栈和队列3.1栈概述3.1.1栈的定义栈是一种只允许在表的一端进行插入和删除操作的线性表。通常将表中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈的插入操作称为进栈（或入栈），栈的删除操作称为出栈（或退栈）。当栈中没有元素时称为空栈。例如，数据元素a0、a1、…、an-1依次进栈，则称a0为栈底元素，an-1为栈顶元素，如图3-1所示。那么，第一个出栈的元素就是an-1，最后一个出栈的元素就是a0。由于元素的插入和删除操作都是在栈顶进行，故栈顶元素的位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。每次进栈的元素都放在原栈顶元素之上成为新的栈顶元素，而每次出栈的元素都是当前的栈顶元素，即最后进栈的元素。换句话说，最先进栈的元素最后出栈，即元素的进栈和出栈是按照“后进先出（lastinfirstout,LIFO）”的原则进行的，因此，栈又称为“后进先出”的线性表。3.1.2栈的基本操作栈基本操作的定义如表3-1所示。3.1栈概述基本操作说明__init__()初始化栈，即构造一个空栈stackEmpty()栈已存在的前提下，判断栈是否为空push(e)栈已存在的前提下，插入数据元素e成为新的栈顶元素pop()栈已存在的前提下，删除栈顶元素getTop()栈已存在的前提下，返回栈顶元素，即最后进栈的元素length()栈已存在的前提下，返回栈中实际元素的个数表3-1栈基本操作的定义3.2栈的顺序存储——顺序栈第3章栈和队列3.2栈的顺序存储——顺序栈在采用顺序存储结构存储栈中的元素时，由于进栈和出栈操作都是在栈的一端（栈顶）进行，因此需要增加一个栈顶指针top，用于指示某一时刻栈顶元素的位置。top指针指向栈顶元素存储位置的上一个存储位置，当top=0时为空栈。顺序栈中栈顶指针和栈中元素之间的关系如下图所示。3.2.1顺序栈的存储结构由上图可以看出，初始化栈时top=0，当有新的元素进栈时，新元素存入top所指的存储位置，并且top加1；当出栈时，top减1，栈顶元素出栈。3.2栈的顺序存储——顺序栈3.2.2顺序栈中基本操作的实现1．初始化顺序栈初始化顺序栈是为顺序栈动态分配存储空间，其具体步骤如下。（1）设置顺序栈的最大容量。（2）设置顺序栈的存储空间。（3）将顺序栈设置为空。classSqStack: #顺序栈类

def__init__(self,max): #构造方法，定义变量并赋初值

self.max=max #设置顺序栈的最大容量

self.data=[None]*self.max #设置顺序栈的存储空间

self.top=0 #将顺序栈设置为空【算法描述】3.2栈的顺序存储——顺序栈2．判断栈是否为空判断顺序栈是否为空就是判断顺序栈中元素个数是否为0，可以通过top指针是否为0来判断。defstackEmpty(self):returnself.top==0【算法描述】3.2栈的顺序存储——顺序栈3．进栈顺序栈的进栈操作是指将新的元素作为栈顶元素插入顺序栈中，其具体过程如下图所示。3.2栈的顺序存储——顺序栈顺序栈中元素进栈的具体步骤如下。（1）判断顺序栈的存储空间是否已满，若已满，则抛出异常。（2）将新的元素插入top所指的存储位置。（3）top加1。defpush(self,e):ifself.top==self.max:raiseException('栈满，无法插入！！！')self.data[self.top]=e #插入新的元素eself.top+=1 #top加1【算法描述】【算法描述】该算法的时间复杂度为O(1)。3.2栈的顺序存储——顺序栈4．出栈顺序栈的出栈操作是指将栈顶元素从顺序栈中删除，其具体过程如下图所示。3.2栈的顺序存储——顺序栈顺序栈中元素出栈的具体步骤如下。（1）判断顺序栈是否为空，若为空，则抛出异常。（2）top减1。（3）返回top所指存储位置元素的值。defpop(self):ifself.top==0:raiseException('栈为空，无法删除！！！')self.top-=1 #top减1returnself.data[self.top] #返回top所指存储位置元素的值【算法描述】【算法分析】该算法的时间复杂度为O(1)。3.2栈的顺序存储——顺序栈5．取栈顶元素取栈顶元素就是获取顺序栈中最后进栈的元素（但并不删除），如右图所示。顺序栈中取栈顶元素的具体步骤如下。（1）判断顺序栈是否为空，若为空，则抛出异常。（2）返回top所指存储位置的下一个存储位置元素的值。3.2栈的顺序存储——顺序栈defgetTop(self):ifself.top==0:raiseException('栈为空！！！')returnself.data[self.top-1] #取栈顶元素【算法描述】【算法分析】该算法的时间复杂度为O(1)。3.2栈的顺序存储——顺序栈6．求顺序栈的长度求顺序栈的长度就是返回顺序栈中实际元素的个数。deflength(self):returnself.top【算法描述】【算法分析】该算法的时间复杂度为O(1)。同步训练利用顺序栈解决汉诺塔问题【问题描述】已知有3个塔座A、B、C，在塔座A上插有n个直径各不相同的圆盘，并按从大到小的顺序叠放。这些圆盘从小到大依次编号为1、2、3、…、n。现要将塔座A上的n个圆盘全部移到塔座C上，且使它们仍按原来的顺序叠放。圆盘在移动时必须遵循如下规则。（1）每次只允许移动一个圆盘。（2）圆盘可以放置在A、B、C中的任何一个塔座上。（3）较小圆盘必须放置在较大圆盘上。这就是著名的汉诺塔问题。同步训练利用顺序栈解决汉诺塔问题【问题分析】解决汉诺塔问题是需要移动圆盘的，移动规律如下。（1）最小圆盘（1号圆盘）的移动须与其他大圆盘（2～n号圆盘）的移动交叉进行，即移动一次最小圆盘，就要移动一次其他大圆盘。（2）圆盘的移动方向由汉诺塔阶数（圆盘总数）决定。当汉诺塔阶数为奇数时，奇数号的圆盘向左移动（即A→C→B→A→C→B…），偶数号的圆盘向右移动（即A→B→C→A→B→C…）；当汉诺塔阶数为偶数时，奇数号的圆盘向右移动（即A→B→C→A→B→C…），偶数号的圆盘向左移动（即A→C→B→A→C→B…）。同时，最下面的圆盘只移动一次，并且是从A号塔座移到C号塔座（向左移）。下面以n=3为例，分析3阶汉诺塔问题的求解过程，如下图所示。同步训练利用顺序栈解决汉诺塔问题同步训练利用顺序栈解决汉诺塔问题【代码实现】defhanoi_Move(pos1,data,pos2,l):x1,x2=l[pos1],l[pos2] #定义塔座

b=data[pos1][len(data[pos1])-1] #获取塔座顶部元素

c=data[pos2][len(data[pos2])-1]if(b<corc==0)andb!=0: #将第一个塔座顶部元素移到第二个塔座

data[pos2].append(data[pos1].pop())print('从塔座'+x1+'移到塔座'+x2)elif(b>corb==0)andc!=0:同步训练利用顺序栈解决汉诺塔问题

#将第二个塔座顶部元素移到第一个塔座

data[pos1].append(data[pos2].pop())print('从塔座'+x2+'移到塔座'+x1)n=int(input('请输入汉诺塔阶数：'))pillars=[[0],[0],[0]]l=['A','B','C','A'] #阶数为偶数时的塔座编号顺序

foriinrange(n): #遍历所有圆盘

pillars[0].append(n-i) #第一个塔座上的圆盘编号

ifn%2==1: #阶数为奇数时的塔座编号顺序

l=['A','C','B','A']flag=2-n%2 #根据阶数的奇偶判断目标塔座的位置同步训练利用顺序栈解决汉诺塔问题pos_1=0whilen!=0: #当阶数为0时不做任何操作

pillars[pos_1].remove(1) #塔座的圆盘个数减1print('从塔座'+l[pos_1]+'移到塔座'+l[pos_1+1])pos_1=(pos_1+1)%3pillars[pos_1].append(1) #移动到新的塔座的圆盘个数加1 #若目标塔座已经全部放置了圆盘，则停止循环

iflen(pillars[flag])-n-1==0:breakhanoi_Move((pos_1+1)%3,pillars,(pos_1+2)%3,l)同步训练利用顺序栈解决汉诺塔问题【程序测试】程序运行结果如下图所示。3.3栈的链式存储——链栈第3章栈和队列3.3栈的链式存储——链栈3.3.1链栈的存储结构与单链表相同，链栈中元素的存储结构也称为结点，结点由数据域和指针域组成。通常，链栈中的第一个结点为栈顶元素，最后一个结点为栈底元素，故链表的头指针即为栈顶指针top。例如，数据元素a0、a1、…、an-2、an-1依次进栈，则该栈的链式存储结构如右图所示。3.3栈的链式存储——链栈在链栈中，假设每个结点为StackNode类对象，则结点的定义如下。classStackNode: #链栈结点类

def__init__(self,data): #构造方法

self.data=data #data属性

self.next=None #next属性提示由于进栈和出栈操作只能在栈顶进行，不存在其他位置的插入和删除操作，所以链栈中不设置头结点。3.3栈的链式存储——链栈3.3.2链栈中基本操作的实现1．初始化链栈初始化链栈就是构造一个空栈。classLinkStack:def__init__(self):self.top=None #将栈顶指针置为空【算法描述】3.3栈的链式存储——链栈2．判断链栈是否为空判断链栈是否为空就是判断栈顶指针top是否为空。defstackEmpty(self):returnself.topisNone【算法描述】3.3栈的链式存储——链栈3．进栈链栈的进栈操作是指将元素为e的结点作为栈顶元素插入链栈中。例如，在链栈(an-1,an-2,…,a1,a0)中将元素e进栈的过程如下图所示。3.3栈的链式存储——链栈链栈中元素进栈的具体步骤如下。（1）生成一个新结点，并令其数据域为e。（2）将新结点的后继指针指向栈顶元素。（3）将栈顶指针指向新结点。defpush(self,e):s=StackNode(e)s.next=self.topself.top=s【算法描述】【算法分析】该算法的时间复杂度为O(1)。3.3栈的链式存储——链栈4．出栈链栈的出栈操作是指将栈顶结点从链栈中删除。例如，将链栈(an-1,an-2,…,a1,a0)中的元素出栈的过程如下图所示。3.3栈的链式存储——链栈链栈中元素出栈的具体步骤如下。（1）判断链栈是否为空，若为空，则抛出异常。（2）将栈顶指针top指向当前栈顶结点的下一个结点。defpop(self):ifself.stackEmpty():raiseException('栈为空，无法删除！！！')temp=self.topself.top=self.top.nextreturntemp.data【算法描述】【算法分析】该算法的时间复杂度为O(1)。3.3栈的链式存储——链栈5．取栈顶元素取栈顶元素就是获取链栈中最后进栈的元素，其具体步骤如下。（1）判断链栈是否为空，若为空，则抛出异常。（2）返回栈顶指针top所指栈顶结点的值。defgetTop(self):ifself.stackEmpty():raiseException('栈为空!!!')returnself.top.data【算法描述】【算法分析】该算法的时间复杂度为O(1)。同步训练利用链栈实现括号匹配的检验【问题描述】给定一个字符串str，设计算法检验其中的圆括号“()”、花括号“{}”和方括号“[]”是否匹配，规则如下。（1）左括号“(”“{”“[”必须有对应的右括号“)”“}”“]”。（2）右括号“)”“}”“]”必须有对应的左括号“(”“{”“[”。（3）左括号“(”“{”“[”必须在对应的右括号“)”“}”“]”前面。（4）括号可以嵌套，一个右括号须与其前面最近的一个左括号匹配。（5）空字符串也视为合法的括号字符串。例如，字符串“()”和“()[]{}”中的括号匹配，“(]”和“([)]”中的括号不匹配。同步训练利用链栈实现括号匹配的检验【问题分析】使用栈存储字符串中的括号，当遇到左括号“(”“{”“[”时进栈，当遇到右括号“)”“}”“]”时，首先判断当前栈是否为空。如果为空，则表示右括号多余，括号不匹配；如果非空，则判断当前栈顶元素是否为与之对应的左括号。如果是，则将当前栈顶元素出栈；如果不是，则表示括号不匹配。【代码实现】classStackNode: #定义结点类StackNodedef__init__(self,data):self.data=dataself.next=NoneclassLinkStack: #定义链栈类LinkStack同步训练利用链栈实现括号匹配的检验def__init__(self): #初始化链栈

self.top=NonedefstackEmpty(self): #判断链栈是否为空

returnself.topisNonedefpush(self,e): #进栈

s=StackNode(e)s.next=self.topself.top=sdefpop(self): #出栈

ifself.stackEmpty():raiseException('栈为空')同步训练利用链栈实现括号匹配的检验temp=self.topself.top=self.top.nextreturntempdefgetTop(self): #取栈顶元素

ifself.stackEmpty():raiseException('栈为空')returnself.top.dataclassIsMatched: #定义括号匹配类IsMatcheddef__init__(self,str):self.str=str #需要判断的字符串

defismatched(self): #检验括号是否匹配同步训练利用链栈实现括号匹配的检验stack=LinkStack()arr=list(self.str)foriinrange(len(arr)): #遍历字符串

#如果字符为“(”“{”或“[”，进栈

ifarr[i]=='('orarr[i]=='{'orarr[i]=='[':stack.push(arr[i])elifarr[i]==')': #如果字符为“)”ifstack.stackEmpty(): #如果栈为空，不匹配

return'不匹配'else:ifstack.getTop()=='(':#如果栈顶元素为“(”，出栈同步训练利用链栈实现括号匹配的检验

stack.pop()

else:breakelifarr[i]=='}': #如果字符为“}”ifstack.stackEmpty(): #如果栈为空，不匹配

return'不匹配'else: ifstack.getTop()=='{': #如果栈顶元素为“{”，出栈

stack.pop() else:

break同步训练利用链栈实现括号匹配的检验elifarr[i]==']': #如果字符为“]”ifstack.stackEmpty(): #如果栈为空，不匹配

return'不匹配' else: ifstack.getTop()=='[':#如果栈顶元素为“[”，出栈

stack.pop()else:breakifstack.stackEmpty(): #如果栈为空，所有括号都匹配

return'匹配'return'不匹配' #如果栈非空，表示有括号不匹配同步训练利用链栈实现括号匹配的检验str1=''test1=IsMatched(str1)print('空字符串中的括号',test1.ismatched())str2='()[]{}'test2=IsMatched(str2)print('字符串',str2,'中的括号',test2.ismatched())str3='([)]'test3=IsMatched(str3)print('字符串',str3,'中的括号',test3.ismatched())【程序测试】程序运行结果如右图所示。3.4栈与递归第3章栈和队列3.4栈与递归3.4.1递归的定义和调用递归是指一个函数在定义自身的同时又直接或间接地调用自身。在很多情况下都会使用递归的方法，如函数的定义、问题的求解等。1．使用递归定义函数很多数学函数都是使用递归定义的，如阶乘函数（见下图）和斐波那契数列（在同步训练中详细介绍）。3.4栈与递归对于阶乘函数，使用递归方法实现的代码如下。defFact(n):ifn==0:return1returnn*Fact(n-1)print(Fact(3))以上代码执行后，以参数3、2、1、0依次启动递归调用，递归结束条件是参数为0。递归结束后，返回计算结果6，其具体执行过程如下图所示。3.4栈与递归由上图可以看出，阶乘函数的求解是分解为几个较简单的函数解决的，分解后的函数解法相同或类似，且有一个明确结束函数的条件，类似这种分步解决问题的方法称为“分治法”。3.4栈与递归使用递归解决问题的核心思想是“分治法”，也就是分而治之，即将一个问题拆分成多个更易解决的小问题，然后逐个解决。“分治法”是一种通用的问题解决方法。当遇到问题时，如果自身能力小于问题难度，则可以使用“分治法”的思想来解决。正如哲学家、物理学家笛卡尔所说：“将面临的所有问题尽可能地细分，细至能用最佳的方式将其解决为止。”3.4栈与递归2．使用递归求解问题在实际应用中，有些问题使用递归求解更加简单，如迷宫问题、汉诺塔问题等。【实例3-7】使用递归求解汉诺塔问题。【代码实现】#汉诺塔问题递归解法n=int(input('请输入汉诺塔阶数：'))#汉诺塔移动操作，表示将A上的圆盘借助塔座B移到塔座Cdefmove(n,A,B,C): ifn==1: #如果n=1，直接将圆盘从塔座A移到塔座C，递归结束3.4栈与递归print('从塔座'+A+'移到塔座'+C) else: #递归

#将A上编号为1～n-1的圆盘借助塔座C移到塔座Bmove(n-1,A,C,B) #将编号为n的圆盘从A移到Cprint('从塔座'+A+'移到塔座'+C) #将B上编号为1～n-1的圆盘借助塔座A移到塔座Cmove(n-1,B,A,C) move(n,'A','B','C') 3.4栈与递归【程序测试】程序运行结果如下图所示。对比利用顺序栈解决汉诺塔问题的代码可以发现，求解同一个问题时，使用递归方法编写的代码简洁明了且易于理解。3.4栈与递归3.4.2递归过程与递归栈为了保证递归函数的正确执行，系统须设立一个递归栈作为整个递归函数运行期间的数据存储区。每当递归函数被调用时，系统须保存函数的参数和返回地址（即执行进栈操作），并向下一层函数传递参数、分配存储空间，从而控制程序转移到下层函数的入口。每当从被调用函数返回调用函数时，系统将保存被调用函数的计算结果，然后恢复上一层函数的参数（即执行出栈操作），并控制程序转移到保存的返回地址处。例如，假设3.4.1节所讲述的阶乘函数中n=3，print()函数调用Fact(3)时，当函数运行结束后，返回地址Loc1（存储最终计算结果的地址），当递归调用Fact(n-1)时，返回地址Loc2（存储每次递归调用后计算结果的地址）。阶乘函数Fact(3)在递归过程中的进栈和出栈情况如下图所示。3.4栈与递归同步训练利用递归实现斐波那契数列【问题描述】斐波那契数列（Fibonaccisequence）又称为“黄金分割数列”，因数学家莱昂纳多·斐波那契以兔子繁殖为例而引入，故又称为“兔子数列”。斐波那契数列是指这样一个数列：1、1、2、3、5、8、13、21、34、…，这个数列从第3项开始，每一项等于前两项之和，其递推公式如下图所示。给定一个整数n，设计算法输出斐波那契数列的前n项。同步训练利用递归实现斐波那契数列【问题分析】由斐波那契数列递推公式可以看出，数列呈现的规律是第n（n＞2）项的值为第n-1项与第n-2项之和，因此可以使用递归求解。。【代码实现】deffib(n):ifn==1orn==2: #第1项和第2项的值都为1return1else: #从第3项开始，调用递归函数分别计算前两项，并将结果相加

returnfib(n-1)+fib(n-2)同步训练利用递归实现斐波那契数列deffibonacci(n): #输出斐波那契数列的前n项

foriinrange(1,n+1):print('斐波那契数列的第',i,'项=',fib(i),sep='')fibonacci(10)【程序测试】程序运行结果如右图所示。3.5队列概述第3章栈和队列3.5队列概述3.5.1队列的定义与栈类似，队列也是一种操作受限的线性表，不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。通常将表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队列的插入操作称为进队（或入队），队列的删除操作称为出队（或退队）。当队列中没有元素时称为空队。例如，数据元素a0、a1、…、an-1依次进队，则称a0为队头元素，an-1为队尾元素，如右图所示。那么，第一个出队的元素就是a0，最后一个出队的元素就是an-1。3.5队列概述稍有礼仪讲究的地方，通常先来者都会优先于后来者。例如，在餐厅排队打饭时，应遵循先到先得的原则；购买火车票时，也应遵循先到先得的原则等。排队使公共场所有了秩序，使各项服务、工作能有序、高效地运行。正如学生遵守课堂秩序才能保证教学的有序进行，员工遵守企业的规章制度才能保证生产的正常进行，社会有了各种规章制度，人们的生活才能安定有序地进行，国家有了各种法律法规，人们的生活才有了安全保障。3.5队列概述由于队列中插入和删除操作分别在表的两端进行，每次进队的元素总是加入队尾，而每次出队的元素总是队头元素。换句话说，最先进队的元素最先出队，即元素的进队和出队是按照“先进先出（firstinfirstout，FIFO）”的原则进行的，因此，队列又称为“先进先出”的线性表。3.5.2队列的基本操作队列基本操作的定义如表3-2所示。3.5队列概述基本操作说明__init__()初始化队列，即构造一个空队列queueEmpty()队列已存在的前提下，判断队列是否为空inQueue(e)队列已存在的前提下，插入数据元素e成为新的队尾元素deQueue()队列已存在的前提下，删除队头元素getHead()队列已存在的前提下，返回队头元素length()队列已存在的前提下，返回队列中实际元素的个数表3-2队列基本操作的定义3.6队列的顺序存储——顺序队列第3章栈和队列3.6队列的顺序存储——顺序队列3.6.1顺序队列与循环队列由于队列中插入和删除操作分别在表的两端进行，因此需要增加队头指针front和队尾指针rear。其中，front指针指向队头元素的位置，rear指针指向队尾元素存储位置的下一个存储位置。顺序队列中front指针、rear指针和队列中元素之间的关系如下图所示。3.6队列的顺序存储——顺序队列由上图可以看出，初始化队列时front和rear都为0。当有新的元素进队时，新元素存入rear所指的存储位置，并且rear加1；当元素出队时，front所指存储位置的元素出队，并且front加1。随着元素的进队和出队，front指针和rear指针都在增加。但是，当达到最大容量时已经满足队满条件，此时，即使有元素出队而空出存储空间，也无法进行元素的进队操作，从而造成存储空间的浪费，这种现象称为“假溢出”。为了使存储空间得到充分利用，于是引入了循环队列。将队列的存储空间看作一个环状的空间，即将队列的首、尾位置连接起来，这样的结构为循环队列。循环队列中front指针、rear指针和队列中元素之间的关系如下图所示。3.6队列的顺序存储——顺序队列3.6队列的顺序存储——顺序队列由上图可以看出，循环队列为空和为满的判断条件都是front==rear，所以无法根据该条件判断当前队列状态。为此，可规定少用一个元素的存储空间，当rear指针的下一个位置是front指针时，则停止进队操作，此时队列已满，判断条件为(rear+1)%max==front，如下图所示。3.6队列的顺序存储——顺序队列3.6.2循环队列中基本操作的实现1．初始化循环队列初始化循环队列是为循环队列动态分配存储空间，其具体步骤如下。（1）设置循环队列的最大容量。（2）设置循环队列的存储空间。（3）将循环队列设置为空。3.6队列的顺序存储——顺序队列classCirQueue: #循环队列结点类

def__init__(self,max): #构造方法

self.max=max #设置循环队列的最大容量

self.data=[None]*self.max #设置循环队列的存储空间

self.front=0 #将循环队列设置为空

self.rear=0 【算法描述】3.6队列的顺序存储——顺序队列2．判断队列是否为空判断循环队列是否为空就是判断队列中元素个数是否为0，可以通过front指针和rear指针是否相等来判断。defqueueEmpty(self):returnself.front==self.rear【算法描述】3.6队列的顺序存储——顺序队列3．进队循环队列的进队操作是指将新的元素从队尾插入队列中，其具体步骤如下。definQueue(self,e):if(self.rear+1)%self.max==self.front:raiseException('循环队列已满，无法插入！！！')self.data[self.rear]=e #插入新的元素eself.rear=(self.rear+1)%self.max【算法描述】（1）判断循环队列的存储空间是否已满，若已满，则抛出异常。（2）将新的元素插入rear所指的存储位置。（3）rear加1。【算法分析】该算法的时间复杂度为O(1)。3.6队列的顺序存储——顺序队列4．出队循环队列的出队操作是指将元素从队头删除，其具体步骤如下。defdeQueue(self):ifself.rear==self.front:raiseException('循环队列为空，无法删除！！！')e=self.data[self.front] #保存删除前的队头元素

self.front=(self.front+1)%self.maxreturne【算法描述】（1）判断循环队列是否为空，若为空，则抛出异常。（2）保存front所指存储位置元素的值。（3）front加1。【算法分析】该算法的时间复杂度为O(1)。3.6队列的顺序存储——顺序队列5．取队头元素取队头元素就是获取循环队列中front所指存储位置元素的值（但并不删除），其具体步骤如下。defgetHead(self):ifself.rear==self.front:raiseException('循环队列为空！！！')returnself.data[self.front]【算法描述】（1）判断循环队列是否为空，若为空，则抛出异常。（2）返回front所指存储位置元素的值。【算法分析】该算法的时间复杂度为O(1)。3.6队列的顺序存储——顺序队列6．求循环队列的长度求循环队列的长度就是返回队列中实际元素的个数。deflength(self):return(self.rear-self.front+self.max)%self.max【算法描述】【算法分析】该算法的时间复杂度为O(1)。同步训练利用循环队列打印杨辉三角【问题描述】杨辉三角是一个由数字排列而成的三角形数表，它描述的是两个未知数之和的幂次方运算后的系数问题。例如，(x+y)2=x2+2xy+y2，其中系数是{1,2,1}，这就是杨辉三角的其中一行。以此类推，(x+y)3、(x+y)4等的运算结果的各项系数就构成了杨辉三角的其他行，如下图所示。其中，杨辉三角的顶点为0行，往下依次为第1行、第2行、……、第n行。设计一个算法，利用循环队列打印杨辉三角的前n行。同步训练利用循环队列打印杨辉三角【问题描述】杨辉三角的特点是两侧最外层的数字都是1，从第2行开始，其他位置上的数字是其上一行中与之相邻的两个数字之和，因此第n行的n-1个数字可以利用第n-1行的数字得到。因此，利用循环队列求第n（n≥2）行数字的基本思路如下。（1）第n行的第1个数字1进队。（2）对于第n-1行的数字（已经依次存放在循环队列中），依次执行如下操作（除最后一个数字1）。①取队头元素并出队，此时front加1，将队头元素与front所指的元素相加。②将相加后的结果进队rear所指的存储位置，此时rear加1。执行上述步骤后，第n行的中间n-1个数字全部进队。（3）第n-1行的最后一个数字1出队。（4）第n行的最后一个数字1进队。同步训练利用循环队列打印杨辉三角例如，杨辉三角中由第4行数字生成第5行数字的具体过程如下图所示。同步训练利用循环队列打印杨辉三角classCirQueue:def__init__(self,max): #初始化循环队列

self.max=maxself.data=[None]*self.maxself.front=0self.rear=0defqueueEmpty(self): #判断队列是否为空

returnself.rear==self.frontdefinQueue(self,e): #进队

if(self.rear+1)%self.max==self.front:同步训练利用循环队列打印杨辉三角raiseException('循环队列已满，无法插入！！！')self.data[self.rear]=eself.rear=(self.rear+1)%self.maxdefdeQueue(self): #出队

ifself.queueEmpty():raiseException('循环队列为空，无法删除！！！')e=self.data[self.front]self.front=(self.front+1)%self.maxreturnedefyanghui(n): #打印杨辉三角

q=CirQueue(1000) #创建CirQueue对象同步训练利用循环队列打印杨辉三角

foriinrange(n):print('',end='') #每一行的格式

print(1) #输出第0行的1#从第1行开始处理

q.inQueue(0) #将一个0进队，来标志一行的开始

#将第1行数字依次进队

q.inQueue(1) q.inQueue(1)k=0whilek<n:同步训练利用循环队列打印杨辉三角foriinrange(1,n-k): #每行前面的空格数逐渐减1print('',end='')q.inQueue(0) #将一个0进队，来标志一行的结尾

temp=q.deQueue() #保存出队元素

value=q.deQueue() q.inQueue(0) #将一个0进队，来标志一行的开始

whilevalue!=0:print(value,end='')q.inQueue(value+temp)#将出队元素相加得到下次进队的值

temp=valuevalue=q.deQueue()同步训练利用循环队列打印杨辉三角q.inQueue(value+temp) #进队

print('\n',end='')k=k+1q=CirQueue(500) #创建CirQueue对象n=int(input('请输入杨辉三角的行数：')) yanghui(n)【程序测试】程序运行结果如右图所示。3.7队列的链式存储——链队第3章栈和队列3.7队列的链式存储——链队3.7