第03章栈和队列.ppt

《第03章栈和队列.ppt》由会员分享，可在线阅读，更多相关《第03章栈和队列.ppt（75页珍藏版）》请在第壹文秘上搜索。

1、1第第3 3章章 栈和队列栈和队列 3.2 3.2 队列队列3.1 3.1 栈栈 本章小结本章小结23.1.1 3.1.1 栈的基本概念栈的基本概念 3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构 3.1.3 3.1.3 栈的链式存储结构栈的链式存储结构3.1 3.1 栈栈 3 栈是一种特殊的线性表，这种线性表上的插入栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。表中允许进和删除运算限定在表的某一端进行。表中允许进行插入、删除操作的一端称为行插入、删除操作的一端称为栈顶栈顶；另一端称为；另一端称为栈底栈底。处于栈顶位置的数据元素称为处于栈顶位置的数据元素称为

2、栈顶元素栈顶元素。不含。不含任何数据元素的栈称为任何数据元素的栈称为空栈空栈。栈的插入操作通常称为栈的插入操作通常称为进栈进栈或或入栈入栈,栈的删除栈的删除操作通常称为操作通常称为退栈退栈或或出栈出栈。3.1.1 3.1.1 栈的基本概念栈的基本概念 4 栈的特点是后进先出。举一个例子说明栈结构栈的特点是后进先出。举一个例子说明栈结构的特征，假设有一个很窄的死胡同，胡同里能容纳的特征，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，若干人，但每次只能容许一个人进出。现有五个人，分别编号为分别编号为，按编号的顺序依次进入此胡同，按编号的顺序依次进入此胡同，如图如

3、图3.1所示。此时若编号为所示。此时若编号为的人要退出胡同，的人要退出胡同，必须等必须等退出后才可以。若退出后才可以。若要退出，则必须等到要退出，则必须等到、依次都退出后才行。这里，人进依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。出胡同的原则是后进去的先出来。图图3.1死胡同示意图死胡同示意图5 栈可以比作这里的死胡同，栈顶相当于胡栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除同可看作栈的插入、删除运算。插入、删除运算都在栈顶进行，相当于进出都经过胡同运算都在栈顶进行，相当于进

4、出都经过胡同口。这表明栈修改的原则是口。这表明栈修改的原则是先进后出先进后出（或（或后后进先出进先出）。因此栈又称为后进先出线性表。）。因此栈又称为后进先出线性表。6栈顶栈顶栈底栈底出栈出栈进栈进栈栈示意图栈示意图7 例例1 设有设有4个元素个元素a、b、c、d进栈进栈,给出它们给出它们所有可能的出栈次序。所有可能的出栈次序。答答:所有可能的出栈次序如下所有可能的出栈次序如下:abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba8 例例2 设一个栈的输入序列为设一个栈的输入序列为A,B,C,D,则借助一则借助

5、一个栈所得到的输出序列不可能是个栈所得到的输出序列不可能是 。(A)A,B,C,D(B)D,C,B,A (C)A,C,D,B(D)D,A,B,C 答答:可以简单地推算可以简单地推算,得容易得出得容易得出D,A,B,C是是不可能的不可能的,因为因为D先出来先出来,说明说明A,B,C均在栈中均在栈中,按按照入栈顺序照入栈顺序,在栈中顺序应为在栈中顺序应为D,C,B,A,出栈的顺出栈的顺序只能是序只能是D,C,B,A。所以本题答案为。所以本题答案为D。9 例例3 已知一个栈的进栈序列是已知一个栈的进栈序列是1,2,3,n,其输出序其输出序列是列是p1,p2,pn,若若p1=n,则则pi的值的值 。(

6、A)i (B)n-i (C)n-i+1 (D)不确定不确定 答答:当当p1=n时时,输出序列必是输出序列必是n,n-1,3,2,1,则有则有:p2=n-1,p3=n-2,pn=1推断出推断出pi=n-i+1,所以本题答案为所以本题答案为C。10 例例4 设设n个元素进栈序列是个元素进栈序列是1,2,3,n,其输出序其输出序列是列是p1,p2,pn,若若p1=3,则则p2的值的值 。(A)一定是一定是2(B)一定是一定是1(C)不可能是不可能是1 (D)以上都不对以上都不对 答答:当当p1=3时时,说明说明1,2,3先进栈先进栈,立即出栈立即出栈3,然后可然后可能出栈能出栈,即为即为2,也可能也

7、可能4或后面的元素进栈或后面的元素进栈,再出栈。再出栈。因此因此,p2可能是可能是2,也可能是也可能是4,n,但一定不能是但一定不能是1。所。所以本题答案为以本题答案为C。11栈的基本运算至少应包括以下栈的基本运算至少应包括以下5种种:(1)(1)初始化栈初始化栈InitStack(st):InitStack(st):构造一个空栈构造一个空栈stst。(2)(2)进栈进栈Push(st,x):Push(st,x):将元素将元素x x插入到栈插入到栈stst中作为中作为栈顶元素。栈顶元素。(3)(3)出栈出栈Pop(st,x):Pop(st,x):其作用是当栈其作用是当栈stst不空时，将不空时

8、，将栈顶元素赋给栈顶元素赋给x,x,并从栈中并从栈中删除当前栈顶删除当前栈顶。(4)(4)取栈顶元素取栈顶元素GetTop(st,x):GetTop(st,x):若若stst不空，由不空，由x x返返回当前的栈顶元素回当前的栈顶元素,当栈当栈stst为空时，结果为一特殊标为空时，结果为一特殊标志志(。(5)(5)判断栈是否为空判断栈是否为空StackEmpty(st):StackEmpty(st):若栈若栈stst为为空空,则返回则返回1 1；否则返回；否则返回0 0。12例例3.3 3.3 利用栈的基本运算，编写一个算法输入若干整数，以利用栈的基本运算，编写一个算法输入若干整数，以0 0标识

9、输入结束。然后按与输入相反次序输出这些整数。标识输入结束。然后按与输入相反次序输出这些整数。解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法如下：如下：void Invert()void Invert()int n;int n;cout cout n;cin n;if(n=0)break;/if(n=0)break;/输入值输入值n n为为0 0时退出循环时退出循环 Push(st,n);/nPush(st,n);/n进栈进栈 cout cout “输出序列：输出序列：”；while(!Stac

10、kEmpty(st)/while(!StackEmpty(st)/栈不空时循环栈不空时循环 Pop(st,n);/Pop(st,n);/出栈出栈n n cout n cout n “”;/;/输出输出n n 13 3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构 栈的顺序存储结构称为顺序栈。顺序栈通常由一栈的顺序存储结构称为顺序栈。顺序栈通常由一个个一维数组一维数组和和一个记录栈顶元素位置的变量一个记录栈顶元素位置的变量组成。习组成。习惯上将栈底放在数组下标小的那端。假设用一维数组惯上将栈底放在数组下标小的那端。假设用一维数组sq5sq5表示一个栈，则需使用一个变量表示一个栈，则需使用

11、一个变量toptop记录当前栈记录当前栈顶下标值。顶下标值。图图 (a)(a)表示顺序栈为栈空，这也是初始化运算得表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶下标值到的结果。此时栈顶下标值top=-1top=-1。如果作出栈运算，。如果作出栈运算，则会则会“下溢下溢”。14顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图top-1toptoptop15顺序栈类型定义如下：顺序栈类型定义如下：顺序栈被定义为一个结构体类型，它有两个域：顺序栈被定义为一个结构体类型，它有两个域：datadata和和toptop。DataData为一个一维数组，用于存储栈中元素，为一个一维数组，用于存储栈中元素

12、，ElemTypeElemType为栈元为栈元素的数据类型，可以根据需要而指定为某种具体的类型。素的数据类型，可以根据需要而指定为某种具体的类型。toptop为为intint型，它的实际取值范围为型，它的实际取值范围为0 0 StackSize-1StackSize-1。top=-top=-1 1表示栈空；表示栈空；top=StackSize-1top=StackSize-1表示栈满。表示栈满。const int StackSize=100;/const int StackSize=100;/顺序栈的初始分配空间顺序栈的初始分配空间 typedef struct sqsttypedef str

13、uct sqst ElemType dataStackSizeElemType dataStackSize；/保存栈中元素保存栈中元素 int topint top；/栈指针栈指针 SqStack SqStack；16顺序栈的基本运算算法如下顺序栈的基本运算算法如下:(1)初始化栈运算算法初始化栈运算算法 此算法主要用于创建一个空栈此算法主要用于创建一个空栈,并将栈顶下标并将栈顶下标toptop初始化为初始化为-1-1。void InitStack(SqStack&st)/st为引用型参数为引用型参数 st.top=-1;17 (2)进栈运算算法进栈运算算法 其主要操作是：栈顶下标加其主要操作

14、是：栈顶下标加1,将进栈元素放进栈将进栈元素放进栈顶下标所指的位置上。顶下标所指的位置上。int Push(SqStack&st,ElemType x)if(st.top=StackSize-1)/栈满栈满 return 0;else st.top+;st.datast.top=x;return 1;18 (3)出栈运算算法出栈运算算法 其主要操作是：先将栈顶元素取出，然后将栈顶其主要操作是：先将栈顶元素取出，然后将栈顶下标减下标减1。int Pop(SqStack&st,ElemType&x)/x为引用型参数为引用型参数 if(st.top=-1)return 0;else x=st.dat

15、ast.top;st.top-;return 1;19 (4)取栈顶元素运算算法取栈顶元素运算算法 其主要操作是：将栈中其主要操作是：将栈中top处的元素取出赋给变处的元素取出赋给变量量x。int GetTop(SqStack st,ElemType&x)if(st.top=-1)/栈空栈空 return 0;else x=st.datasq.top;return 1;20 (5)判断栈空运算算法判断栈空运算算法 其主要操作是：若栈为空（其主要操作是：若栈为空（top=-1）则返回值）则返回值1，否则返回，否则返回0。int StackEmpty(SqStack st)if(st.top=-1

16、)return 1;else return 0;21 例例3.4 设计一个算法，判断一个表达式中符号设计一个算法，判断一个表达式中符号“（”与与“）”、“”与与“”、“”与与“”是否匹是否匹配。若匹配，则返回配。若匹配，则返回1；否则返回；否则返回0。解解:设置一个栈设置一个栈st,用用i扫描表达式扫描表达式exps：遇到：遇到(、和和时，将其进栈时，将其进栈,遇到）、遇到）、和和时时,判断栈顶是否判断栈顶是否是匹配的括号。若不是，则退出扫描过程，返回是匹配的括号。若不是，则退出扫描过程，返回0；否则直到否则直到exps扫描完毕为止。若扫描完毕为止。若top=0，则返回，则返回1。对应算法如下：对应算法如下：(以下为完整程序）以下为完整程序）#include const int Max=100;int match(char*exps)char stMax,top=-1,i=0;int nomatch=0;while(expsi!=0&nomatch=0)22 switch(expsi)case(:sttop=expsi;top+;break;case:sttop=expsi;top+;