数据结构与算法 课件 第三章栈和队列

全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第三章栈和队列学习目标掌握栈和队列的逻辑定义、特点及基本操作，了解它们的逻辑表示方法及使用场掌握栈的两种存储方式及各自的特点，掌握两种方式下基本操作的实现及复杂度分析掌握队列的两种存储方式及各自的特点，掌握两种方式下基本操作的实现，重点掌握循环队列的实现及复杂度分析掌握结合了栈和队列特点的双端队列了解线性表与栈及队列的关系灵活运用栈和队列的基本操作，设计算法解决与此相关的实际问题本章主要内容栈12进一步讨论栈与队列3队列4栈和队列的应用栈和队列是线性表的两个经典特例，它们都是操作受限的线性表，即操作的位置需要满足各自的条件因为这些条件的特殊性，使得实现各自的操作时过程简捷，效率更高第一节

栈栈是一种特殊的线性表，它的特殊性体现在操作的位置上。在含n个元素的线性表中进行插入或删除时，操作位置可以有n+1个或n个当将操作位置限定在线性表的同一端时，得到的数据结构就是栈它是一种受限的线性表栈的定义及其基本操作定义3-1栈（stack）是限定仅在一端进行插入和删除的线性表能进行插入和删除的这一端称为栈顶，线性表的另一端称为栈底在栈顶插入一个元素称为入栈（push）、进栈或压栈，从栈顶删除一个元素称为出栈（pop）或退栈栈的表示将栈S表示为：S=(a0,a1,…,an-1)

通常指定an-1一端为栈顶，a0一端是栈底栈中元素个数n称为栈的长度，当n=0时，称为空栈栈具有后进先出（LIFO，LastInFirstOut）的特性只要栈不空，就允许出栈只要栈不满，就允许入栈当没有其他的特殊限制时，对于同一个入栈序列，可能会得到很多个合理正确的出栈序列栈的基本操作出栈序列个数

例3-1设有5个元素1,2,3,4,5依次入栈，以push(x)表示x入栈，pop(x)表示x出栈，试写出得到出栈序列2,1,4,3,5的操作过程操作过程为push(1),push(2),pop(2),pop(1),push(3),

push(4),pop(4),pop(3),push(5),pop(5)例3-2依次读入数据元素序列a,b,c,d,e,f,g并入栈。下列选项中，不可能是出栈序列的是（）A．d,e,c,f,b,g,aB．c,d,b,e,f,a,gC．e,f,d,g,c,b,aD．f,e,g,d,a,c,b答案为D例3-3一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是n，则第i（1<i≤n）个输出的元素是（）A．不确定B．n-i+1C．iD．n-i答案为B例3-4元素a,b,c,d,e依次进入初始为空的栈中，在所有可能的出栈序列中，以元素d开头的序列个数是（）A．3 B．4 C．5 D．6

答案为B例3-5入栈序列是1,2,3,4，出栈序列是2,4,3,1，则栈的容量最小是（）。A．1B．2C．3D．4答案为C栈的存储及其实现栈有两种主要的存储方式顺序存储链式存储顺序存储方式使用数组保存栈元素，得到的是顺序栈链式存储方式使用单链表保存栈元素，得到的是链式栈顺序栈及其实现在顺序栈中，栈中的元素保存在一维数组中，将栈底定义在数组下标为0的位置同时使用一个变量标记栈顶的位置，即栈顶位置栈顶位置也称为栈顶指针顺序栈的定义typedefintELEMType; //以int类型为例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是数组最大容量，已定义的常量 inttop; //栈顶位置}SeqStack;顺序栈的基本操作栈顶位置top的两种定义方式本书采用(a)的方式初始化栈、清空栈判空、判满入栈入栈时，新元素放在element[top]处，然后top加1第1个元素入栈时放在数组下标为0的位置因为数组空间有限，最大容量是maxSize，所以入栈时需要判定栈不能是满的出栈出栈时，需要先将top值减1，然后将element[top]处的值通过参数x返回出栈时需要判定栈不是空的获取栈顶元素效率top的值既是保存下一个入栈元素的位置，也是栈中所含元素个数的计数器因为栈的入栈操作及出栈操作都在栈顶进行，所以入栈、出栈、获取栈顶元素时都不需要移动栈中已有的元素，故时间复杂度都是O(1)判定栈空及栈满等操作的时间复杂度也是O(1)例3-6也可以将数组下标最大的一端作为栈底若一个栈保存在数组V[0..n-1]中，初始时栈顶指针top为n，则下列选项中，能够正确实现x入栈操作的语句序列是（）。A．top=top+1;V[top]=x;B．V[top]=x;top=top+1;C．top=top-1;V[top]=x;D．V[top]=x;top=top-1;答案为C对顶栈数组的两个端点分别作为两个栈的栈底左侧栈占用数组0到k的单元，栈顶在k+1位置右侧栈占用数组m-1到h的单元，栈顶在h-1位置此时必须满足k<h，才能保证两个栈不会重叠栈S1入栈时，栈顶值增大，出栈时栈顶值减小栈S2刚好相反，入栈时栈顶值减小，出栈时栈顶值增大例3-7若栈采用顺序存储方式存储，现有两个栈共享空间V[0..m-1]，栈1的底在v[0]，栈2的底在V[m-1]，初始时，栈1的栈顶top1=0，栈2的栈顶top2=m-1。则栈满的条件是（）A．|top2-top1|==0B．top1==top2+1C．top1+top2==m-1D．top1==top2答案为B链式栈所谓的链式栈，可以看作是一个仅在表头位置进行操作的单链表将头指针所指的这一端作为栈顶，表尾一端作为栈底入栈操作及出栈操作都可以通过头指针完成。所以，在链式栈中，可以只定义头指针，尾指针及头结点都可以不定义链式栈的定义typedefintELEMType;typedefstructnode{ //链式栈结点 ELEMTypedata; structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack; //链式栈初始化栈初始时是个空栈，所以指向栈顶的指针赋值NULL出栈仅当栈不为空时才能执行出栈操作，所以pop函数中要先判断栈不为空出栈后，将栈顶元素的值通过x返回给调用者元素所占用的空间要释放掉清空栈及判栈空入栈入栈时，需要创建一个新结点，并将新结点插入在栈顶位置顺序栈与链式栈的比较实现顺序栈和链式栈的所有操作都只需要常数时间，因此栈的两种实现方式的优劣仅体现在它们的存储效率上顺序栈需要预先申请一个固定长度的一维数组，并自始至终全部占用，当栈中元素个数相对较少时，空间浪费较大链式栈的长度虽然可变，但是每个元素都需要一个指针域，这又产生了结构性空间开销栈与函数调用栈是保存调用信息的最佳结构系统内部会开辟一个函数调用栈用来保存函数在调用过程中所需要的一些信息第二节

队列队列也是一种特殊的线性表，其特殊性也体现在操作的位置上它具有优先的特性，即先来的先得到服务这种先来先服务的特性称为先进先出（FirstInFirstOut），简称FIFO队列的定义及其基本操作定义3-2队列（queue）是只能在表的一端插入、在另一端删除的线性表能进行插入的一端称为队列尾，简称队尾；能进行删除的一端称为队列头，简称队头在队尾插入元素称为入队（enqueue），从队头删除元素称为出队（dequeue）仍然可以沿用线性表的方法来表示队列，队列Q可以表示为 Q=(a0,a1,…,an-1)a0称为队头元素，an-1称为队尾元素，元素个数n称为队列长度当给定队列的入队序列后，仅能得到一个出队序列，而且是与入队序列完全相同的序列。这是由队列先进先出的特性决定的队列的定义队列中元素的类型是ELEMType，另外，还有指标队头和队尾的两个量定义如下所示typedefintELEMType;intfront,rear; //队头、队尾指针队列的操作定义队列的存储及实现与线性表及栈一样，队列也有两种实现方式，分别得到顺序队列和链式队列顺序队列使用一个一维数组A（下标从0到n-1）来保存队列，假定队列中含有m（m≤n）个元素选择A[0]作为队头，那么A[m-1]就是队尾当出队时，队头A[0]从数组中删除，此时要依次将后面的m-1个元素均前移一个位置这种情况下出队操作的时间开销是O(m)存储结构现在交换队头和队尾的位置，选择A[m-1]是队头，那么A[0]是队尾入队时，队列中原有的m个元素均需后移一个位置，腾出A[0]的位置放置新元素此时入队操作的时间开销将为O(m)存储结构可以使用变量front指示队头位置，使用变量rear指示队尾位置称front为队头指针，rear为队尾指针表示的是数组下标通常，front指示的是队头元素所在的位置，rear指示的是队尾元素后面的空位置按照惯例，还是将第一个入队的元素保存在数组下标0的位置入队的新元素放置到所有元素的后面经过若干次入队、出队操作后，含m个元素的队列的示意图如下所示，其中阴影部分表示队列中的元素实际占用的数组单元

a0…am-1

↑front

↑rear

当再进行若干次入队操作后，rear会到达数组的末尾，即最后一个下标位置。之后再进行入队操作时，导致数组下标越界。但数组的前半段可能会因出队操作而有空闲的单元

x…y

↑front

↑rear可以重复利用数组中前面的空闲单元保存后续入队的元素…v

……u…

↑rear

↑front

例3-8设队列保存在最大容量为7的数组A中，从空队列开始，依次执行下列各步操作，分别画出得到的队列示意图依次将5,12,9,37入队列将5,12依次出队列，并依次将25,8入队列将16入队列，再将9出队列，再将7,4入队列循环队列顺序队列都实现为循环队列在循环队列中，入队操作会涉及到队尾rear值的变化，rear=(rear+1)%n，出队操作会涉及到队头front值的变化，front=(front+1)%n，其中n是数组的大小可以把这个数组想象成一个首尾相接的圆环，A[n-1]的后面是A[0]“循环”一词的含义正是如此空与满数组满时，rear==front条件rear==front也代表空队列解决方法：让数组中始终剩余至少一个空位置。当数组中仅有一个空位置时，就认为已经达到队列的最大长度了，队列已满初始时，front=0且rear=0例3-9已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）A．0,0B．0,n-1C．n-1,0D．n-1,n-1答案是B循环队列的定义typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循环队列初始化构造一个空队列，队头和队尾指针均赋初值0清空队列队列置空也得到一个空队列，可以将队头和队尾指针均赋值0，和初始化队列的结果一样也可以让队头和队尾指针的值相等，表示是一个空队列判空与判满队列为空的条件是rear==front队列为满的条件是(rear+1)%n==front求队列长度入队与出队链式队列链式队列采用带头指针及尾指针的单链表作为队列的存储结构单链表的头指针可以当作队头指针front，尾指针可以当作队尾指针rear链式队列的定义typedefintELEMType;typedefstructnode{ //链式队列中结点 ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //链式队列 LinkQueueNode*front,*rear; //队头指针、队尾指针}LinkQueue;初始化、清空队列判空循环队列中，当队头指针和队尾指针相等时，队列为空空链式队列中，队头指针和队尾指针都为NULL在内存足够大的情况下，链式队列通常不会满入队列出队例3-10若使用不带头结点的单链表存储队列，则进行入队列操作时（）。A．仅需要修改队头指针，不需要修改队尾指针B．仅需要修改队尾指针，不需要修改队头指针C．队尾指针一定要修改，队头指针也一定要修改D．队尾指针一定要修改，队头指针可能要修改答案为D采用链式方式实现队列时，也可以配合使用一个空闲单元链表，使得入队、出队时尽量少地调用malloc函数及free函数在链式队列中，可以将这两个链表合在一起，形成一个圆环，即使用一个循环链表来表示链式队列及对应的空闲单元链表。在这个循环链表中，结点分为两部分，一部分结点用来保存实际数据，另一部分结点是空闲结点带空闲单元链表的链式队列初始状态第一个元素入队第三节

进一步讨论栈与队列双端队列输入受限的双端队列输出受限的双端队列例3-11若以1,2,3,4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（）。A．1,2,3,4B．4,1,3,2C．4,2,3,1D．4,2,1,3答案是C例3-12循环队列存放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。下列判断队空和队满的条件中，正确的是（）。A．队空：end1==end2；队满：end1==(end2+1)modMB．队空：end1==end2；队满：end2==(end1+1)mod(M-1)C．队空：end2==(end1+1)modM；队满：end1==(end2+1)modMD．队空：end1==(end2+1)modM；队满：end2==(end1+1)mod(M-1)答案是A栈与队列的相互模拟使用栈来模拟队列使用栈模拟的队列类型定义typedefstruct{ SeqStackS,T;}simuQueue; //队列typedefintELEMType;初始化入队列出队列判空、判满使用队列来模拟栈使用队列模拟的栈类型typedefstruct{ SeqQueueP,Q;}simuStack; //使用队列来模拟栈typedefintELEMType;初始化、清空栈判空、判满求长度入栈操作出栈第四节

栈和队列的应用——括号的匹配检查程序中有很多符号是成对出现的，并且它们的出现次序必须正确，可以嵌套但不能交错“左”符号称为“开”符号，“右”符号称为“闭”符号如果表达式中符号匹配正确，则表达式称为平衡的表达式可以用栈来实现检验符号平衡性的算法检验括号匹配算法的思想从左至右扫描给定的符号串，忽略所有非括号的符号当遇到开括号时，保存它当遇到一个闭括号时，看看它是否对应于最近遇到的开括号如果是，则丢掉开括号，并继续扫描符号串如果能扫描完整个符号串，且没有遇到不匹配的情况，则给定的符号串代表的表达式是平衡的可以使用栈来保存遇到的开括号表达式不平衡的情况刚扫描到的闭括号与栈顶开括号不匹配，说明括号有交错已扫描到表达式尾，但栈不空，说明开括号数多于闭括号数扫描到闭括号时发现栈为空，说明缺少与此闭括号对应的开括号检验括号平衡性算法的实现检验括号平衡性算法例3-13检查表达式[a+(d+e)]时栈的变化过程例3-14检查表达式{[(])}时栈的变化过程表达式的计算表达式的表示