数据结构（从概念到算法）课件

第3章栈与队列01020304目录CONTENTS栈队列应用实例本章小结01PART栈3.1.1栈的基本概念栈是限定在表尾做插入、删除操作的线性表。向栈中插入元素叫作进栈，从栈中删除元素叫作出栈，栈的表头叫作栈底，栈的表尾叫作栈顶。为了明晰栈底和栈顶的概念，通常使用“井”状图形表示一个栈。进栈：向栈中插入一个元素。其也称为入栈、推入、压入、push。出栈：从栈删除一个元素。其也称为退栈、上托、弹出、pop。栈顶：允许插入、删除元素的一端（表尾）。栈顶元素：处在栈顶位置的元素（表尾元素）。栈底：表中不允许插入、删除元素的一端（表头）。空栈：不含元素的栈。栈中元素的进出原则：“后进先出”（Last

In

First

Out）。栈的别名：“后进先出”表、LIFO

表、反转存储器、堆栈。栈3.1.2栈的抽象数据类型栈3.1.3栈的操作特性下面以火车调度站为例来理解栈的操作特性。假定火车调度站满足栈的插入、删除规则，列车只能在一端进站、出站，现有3辆列车

A、B、C依次进入火车调度站，那么列车A、B、C的出站顺序会有下面几种不同组合：栈3.1.3栈的操作特性第一种组合：输入顺序为A,B,C，产生输出为A,B,C。其过程为：A进栈→A出栈→B进栈→B出栈→C进栈→C出栈。在此进、出栈顺序下，列车出站顺序（栈的输出序列）即为A,B,C。栈3.1.3栈的操作特性第二种组合：输入顺序为A,B,C，产生输出为C,B,A。其过程为：A进栈→B

进栈→C

进栈→C

出栈→B

出栈→A

出栈。在此进、出栈顺序下，列车出站顺序（栈的输出序列）即为C,B,A。类似地，可以得出另外组合：B,C,A、A,C,B

和B,A,C。然而，以A,B,C

为输入序列时，无论采用何种进、出栈顺序都无法产生C,A,B的输出序列。其原因为：C

的输出需要以C

的进栈为前提，输出

C

之前，所有尚未输出的、C

的前序元素（A

和

B）都需要存储在栈中，而输出

C

之后，所有尚未输出的、C

的前序元素均应以逆序顺序输出（即

C,B,A），故无法输出序列C,A,B。扩展上述结论可知，以(…,ai,…,aj,…,ak,…)作为栈的输入序列时，无法得到输出序列(…,ak,…,ai,…,aj,…)。栈3.1.4栈的顺序存储结构使用顺序存储结构构建的栈称为顺序栈。对顺序栈进行操作时，需要考虑以下几点：存储空间的分配方式；栈顶标识top：top是指向栈顶元素还是指向栈顶元素下一位置；满栈和空栈的条件：是top指向栈顶元素情况下的满栈、空栈条件还是top指向栈顶元素下一位置情况下的满栈、空栈条件。栈3.1.4栈的顺序存储结构假定

top

始终指向栈顶元素，任意栈

s

的特征如下。（1）非空栈条件：top>=0（2）满栈条件：top==maxlength-1（3）空栈条件：top==-1（4）进栈过程：先对top加1，使top指向栈顶元素下一空位置，然后将待插入数据赋予s[top]，完成进栈操作（5）出栈过程：先取出栈顶元素s[top]，然后对top减1，使top指向新的栈顶元素，完成出栈操作栈3.1.4栈的顺序存储结构当

top

始终指向栈顶元素下一位置时，任意栈

s

的特征如下。（1）非空栈条件：top>=1（2）满栈条件：top==maxlength（3）空栈条件：top==0（4）进栈过程：先将待插入数据赋予s[top]，然后对top加1，使top指向栈顶元素下一空位置，完成进栈操作（5）出栈过程：对top减1，使top指向原来的栈顶元素栈3.1.4栈的顺序存储结构接下来，介绍顺序栈的静态分配与动态分配。其中，静态分配时需要定义栈的空间和栈顶标识；动态分配需要定义栈的首地址、栈顶标识和当前栈空间的大小。具体分配方式如下：（1）静态分配栈3.1.4栈的顺序存储结构（2）动态分配：对比线性表静态（动态）分配方式与栈的静态（动态）分配方式可知，在栈的分配方式中，使用了栈顶标识top替代线性表分配方式中的表长。根据上述分析，约定top指向栈顶元素下一位置，给出如下动态分配顺序栈的基本操作算法。栈3.1.4栈的顺序存储结构设计动态分配顺序栈的初始化算法——InitStack函数。首先，调用malloc函数为顺序栈分配存储空间，然后为栈顶标识top和当前空间大小stacksize赋值。栈3.1.4栈的顺序存储结构设计进栈算法——Push函数。首先，判断栈是否已满，如果栈已满，就运用realloc函数重新开辟更大的栈空间。如果realloc函数返回值为空，提示溢出，则更新栈的地址以及栈的当前空间大小。最终，新元素入栈，栈顶标识top加1。栈3.1.4栈的顺序存储结构设计出栈算法——Pop函数。首先，根据栈顶标识top判断当前栈是否是一个空栈，如果当前栈是一个空栈，提示下溢，否则，更新栈顶标识，取出栈顶元素。栈3.1.5栈的链式存储结构对于栈的链式存储结构，通常只考虑采用单链表作为栈的存储结构。假定元素进栈顺序为a1,a2,…,an，如果用普通无头结点的单链表表示，按其元素输入顺序表示元素间的线性关系，每个新进入的元素结点应链接在表尾，这样构造得到的链式栈如图所示。栈3.1.5栈的链式存储结构但是，上面的结构进、出栈的时间开销大，时间复杂度为O(n)。为了解决这一问题以提高进、出栈的效率，我们可以将结点指针顺序颠倒过来，即每个元素结点的指针由原来的指向逻辑上直接后继元素结点改成指向逻辑上直接前驱元素的结点，如将top指向

an，同样也能够正确地维护元素间的线性关系。这样进栈时只是简单地将新结点作为首结点，出栈时删除首结点即可，因为栈具有后进先出的特性。那么进、出栈不需要遍历整个链表，时间开销就为常数，时间复杂度为O(1)。栈3.1.6栈的应用栈的“后进先出”特性在实际操作中应用非常广泛。例如，在高级语言中允许函数之间的嵌套调用和函数的递归调用，编译程序就是通过栈这种数据结构来完成这些执行顺序的控制的；借助栈也可以将一些递归算法改写成非递归算法，从而提高算法效率。一般情况下，如果访问到的数据在后续处理中还需继续被访问，此时就需要用某种数据结构将其保存起来。在后续重复访问这些数据时，其顺序是“后保存的数据先被访问，先保存的数据后被访问”，这种情况下可运用栈这个数据结构来保存这些数据和控制相关数据的访问顺序。下面列举了栈的应用实例表达式求值。栈3.1.6栈的应用运用栈来对表达式求值，四则混合运算的规则如下。（1）先乘除，后加减（2）先括号内，后括号外（3）同类运算，从左至右在这里，约定在运算过程中，当两个运算符相邻出现时，q1表示左运算符，q2表示右运算符。另外，新增一个运算符“#”作为一个表达式的开始符和结束符，即将待求值的表达式表示为#待求值的表达式#。栈3.1.6栈的应用运算符的优先级关系表在运算过程中非常重要，它是判定进栈、出栈的重要依据。θ2θ1+-*/()#+>

>

<

<

<

>

>

->

>

<

<

<

>

>

*>

>

>

>

<

>

>

/>

>

>

>

<

>

>

(<

<

<

<

<

=

)>

>

>

>

>

>

#<

<

<

<

<

=栈3.1.6栈的应用下面以分析表达式4+2*3-12/(7-5)为例来说明求解过程，从而总结出表达式求值的算法。求解中设置两个栈：操作数栈和运算符栈。从左至右扫描表达式：#4+2*3-12/(7-5)#，最左边是开始符，最右边是结束符。表达式求值的过程如下表所示：步骤号操作数栈运算符栈输入串下步操作说明0

#4+2*3-12/(7-5)#操作数进栈14#+2*3-12/(7-5)#p(#)<p(+)，进栈24#+2*3-12/(7-5)#操作数进栈342#+*3-12/(7-5)#p(+)<p(*)，进栈442#+*3-12/(7-5)#操作数进栈5423#+*-12/(7-5)#p(*)>p(-)，退栈op=*6423#+-12/(7-5)#操作数退栈，b=3742#+-12/(7-5)#操作数退栈，a=284#+-12/(7-5)#a*b得c=6，进栈946#+-12/(7-5)#p(+)>p(-)，退栈op=+1046#-12/(7-5)#操作数退栈，b=6114#-12/(7-5)#操作数退栈，a=412

#-12/(7-5)#a+b得c=10，进栈1310#-12/(7-5)#p(#)<p(-)，进栈1410#-12/(7-5)#操作数进栈栈151012#-/(7-5)#p(-)<p(/)，进栈161012#-

/(7-5)#p(/)<p(()，进栈171012#-

/(7-5)#操作数进栈1810127#-

/(-5)#p(()<p(-)，进栈1910127#-/(-5)#操作数进栈20101275#-

/(-)#p(-)>p())，退栈op=-21101275#-

/()#操作数退栈，b=52210127#-

/()#操作数退栈，a=7231012#-

/()#a-b得c=2，进栈2410122#-

/()#p(()=p())，去括号2510122#-/#p(/)>p(#，退栈op=/2610122#-#操作数退栈，b=2271012#-#操作数退栈，a=122810#-#a/b得c=6，进栈29106#-#p(-)>p(#)，退栈op=-30106##操作数退栈，b=63110##操作数退栈，a=1032

##a-b得c=4，进栈334##p(#)=p(#)，算法结束栈3.1.6栈的应用通过观察中对一个表达式的求解过程，我们可以发现：扫描到的操作数总是会被推入操作数栈；扫描到的运算符q

2，一般会与运算符栈的栈顶元素q1进行优先级比较，再依据优先级的大小进行不同的操作，直到表达式只剩结束符、运算符栈只剩开始符。操作数栈的元素即是最后表达式的求值。算法的主要思想如下。设s1—操作数栈，存放暂不参与运算的数和中间结果；

s2—运算符栈，存放暂不参与运算的运算符。栈3.1.6栈的应用（1）置s1、s2为空栈；开始符#进s2。（2）从表达式读取w，w可为操作数或运算符。（3）当w!='#'||s2的栈顶运算符!='#'时，重复以下操作。①若w为操作数，则w进s1，读取下一w。②若w为运算符q

2，则：prior(s2

的栈顶运算符q1)<prior(w(q

2))时，w

进s2；读取下一w；prior(s2

的栈顶运算符q1)=prior(w(q

2))，且w=‘)’时，去括号，Pop(s2)；读取下一w；prior(s2

的栈顶运算符(q1))>prior(w(q2))时，Pop(s1,a);Pop(s1,b);Pop(s2,op);c=b

op

a;Push(s1,c);/*op为q1*/q1

和q

2

没定义优先级关系，表达式有语法错误，会报错（4）s1

的栈顶元素为表达式的值。02PART队列3.2.1队列的基本概念队列也是插入和删除操作位置受限的线性表，只允许在表的一端删除元素，在另一端插入元素。队列的别名是“先进先出”表、FIFO表、queue等。与队列有关的概念包括以下几个。空队列：不含元素的队列队首：队列中只允许删除元素的一端。其一般称为head、front。队尾：队列中只允许插入元素的一端。其一般称为rear、tail。队首元素：处于队首的元素队尾元素：处于队尾的元素。进队：插入一个元素到队列中。其也称为入队。出队：从队列中删除一个元素。队列3.2.2队列的抽象数据类型队列3.2.3顺序队列的基本运算及实现顺序队列是指用一片连续的地址空间来存储元素的队列。同样地，为了方便进队和出队操作，我们需要设置两个标识，分别代表队首和队尾。例如，一维数组Q[5]表示顺序队列，设置两个标识f和r，约定f指向队首元素，r指向队尾元素后的一个空单元。这样r减去f就正好表示队列中元素的个数；当f=r时，表示队列为空。进队操作，先将新元素保存在r所标识的单元中，然后向后移动r；出队操作，先取出f指向的队首元素，然后向后移动f。队列3.2.3顺序队列的基本运算及实现在第（5）步，D,E,F

依次进队后，r

往后移动，r

就会指向5

单元后面的单元。如果此时有元素G

进队，就会判断队列已满而出现“溢出”的情况。但这种“溢出”是假溢出，因为其实队列里面还有空单元Q[0]、Q[1]和Q[2]可以用来存放元素。解决假溢出的问题有以下两种解决方案：第一种解决方案是移动元素。在上面的例子中，如果G想进队，就先将D,E,F整体往队列前端空单元处移动，f也移动到指向队首单元；G进队后，r往后移动指向4单元。这种方法比较费时，移动元素的开销较大，需要考虑其他更有效的方案避免元素移动，提高进队与出队的效率。队列3.2.3顺序队列的基本运算及实现第二种解决方案是将队列Q

当循环表使用，从而使得队列成为一个循环队列。接着上面的例子，D,E,F

进队后，r

循环地指向第0

单元；G

进队后存储在0

单元，r

往后移动，并指向1

单元。队列3.2.3顺序队列的基本运算及实现接着上面的例子，目前队列中有D、E、F3个元素，f指向3单元，r指向1单元。如果此时H,I进队，r往后移动，并指向3单元，而f也指向3单元，那么f=r，如图所示。前文中，f=r是空队列的条件，但这里f=r表示满队列，这样就会出现二义性，违反算法的基本特性。队列3.2.3顺序队列的基本运算及实现解决循环队列的二义性问题有两个方案：方案一是增加一个标识变量，例如用一个变量表示队列中元素的个数来区分是满队列还是空队列；方案二是留出一个单元位置不使用，作为元素进队前测试之用，即若(r+1)%maxlength==f，表明还剩最后一个单元可用，此时可以认为队列已满（maxlength是队列最大元素个数）。若队列为Q[maxlength-1]，即系统会为循环队列Q分配maxlength个元素的空间，但只能存储maxlength-1个元素。方案二比较直观，循环队列的入队算法基本采取这种方式。队列3.2.4链式队列的基本运算及实现链式队列是用链式结构存储的队列。一般用带表头结点的单链表来表示队列，但队列的头指针与单链表的头指针有所不同。队列的插入和删除在两端，为提高插入、删除的效率，头指针中设置了Q.front和Q.rear两个指针。Q.front是队首指针，指向表头结点；Q.rear是队尾指针，指向队尾结点。空队列：Q.front和Q.rear均指向表头结点，表头结点的指针域为空。非空队列：Q.front->next指向队首结点a1，Q.rear指向队尾结点

。03PART应用实例3.3.1栈的应用实例编码是信息传输中一种常见的操作。现有一种简易的编码规则为“k[encoded_string]”，它表示其中方括号内部的encoded_string正好重复k次。encoded_string中的基本字符为小写英文字母；数字k（k必须为正整数）表示对应字符串重复出现的次数。利用该编码规则，可以求返回解码后的字符串。例如，字符串2[ab]3[c]def，表示ab出现2次、c出现3次、def出现1次，解码后返回的字符串为ababcccdef。另外，这种编码允许嵌套的表达形式，解码的过程需要由里向外、从左到右进行解码。例

如，字符串3[a2[bc]]2[d]，先对里层的2[bc]进行解码得到3[abcbc]2[d]，再对3[abcbc]解码得到abcbcabcbcabcbc2[d]，最后解码得到的字符串为abcbcabcbcabcbcdd。应用实例3.3.1栈的应用实例通过分析上述解码过程可知，我们可以借助栈来实现嵌套编码的解码。其算法思想如下。（1）初始化两个栈，分别为记录重复次数的数字栈s1和记录字符串的字符串栈s2（2）扫描待解码的字符串。①若当前字符为数字，解析出完整的数字并入栈s1②若当前字符为字母或左中括号，入栈s2③若当前字符为