《第3章 栈和队列(精品).ppt》由会员分享，可在线阅读，更多相关《第3章 栈和队列(精品).ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 栈和队列栈和队列n本章内容本章内容3.1 栈栈3.1.1 栈的定义及基本运算栈的定义及基本运算3.1.2 栈的存储结构和实现栈的存储结构和实现3.1.3 栈的应用栈的应用3.2 队列队列3.2.1 队列的定义及基本运算队列的定义及基本运算3.2.2 队列的存储结构和实现队列的存储结构和实现3.2.3 队列的应用队列的应用13.1.1 栈的定义及基本运算栈的定义及基本运算n栈栈(Stack)的定义的定义 栈栈(Stack)是限制在是限制在表尾表尾进行插进行插入和删除运算的线性表，表尾端入和删除运算的线性表，表尾端称为栈顶称为栈顶(top),表头端称为栈底表头端称为栈底(bottom
2、)。当表中没有元素时。当表中没有元素时称为空栈。称为空栈。anan-1.a2a1栈底栈底栈顶栈顶入栈入栈出栈出栈栈栈S=(a1,a2,a3,.,an)a1称为栈底元素，称为栈底元素，an为栈顶元素。栈为栈顶元素。栈中元素是按中元素是按a1，a2，a3，an的次序的次序进栈的，退栈的第一个元素应为栈顶进栈的，退栈的第一个元素应为栈顶元素元素an。23.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(1)A、B、C、D四个元素四个元素依次进入一个栈，再依次依次进入一个栈，再依次出栈，得到一个输出序列出栈，得到一个输出序列DCBA。DCBAABCDDCBA 栈的特点栈的特点栈
3、的修改是按栈的修改是按后进先出后进先出的原则进行的。因此，的原则进行的。因此，栈称为后进先出表（栈称为后进先出表（LIFO）。）。33.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演：栈的运算演：(2)能否由入栈序列能否由入栈序列A、B、C、D、E得到出栈序列得到出栈序列CBDAE？ABCDE操作序列：操作序列：出栈序列：出栈序列：元素元素A入栈入栈A A 元素元素B入栈入栈B B 元素元素C入栈入栈C C43.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(2)能否由入栈序列能否由入栈序列A、B、C、D、E得到出栈序列得到出栈序列CBDAE？DE操作序列：操
4、作序列：出栈序列：出栈序列：元素元素A入栈入栈A 元素元素B入栈入栈B 元素元素C入栈入栈 元素元素C出栈出栈CC 元素元素B出栈出栈B53.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(2)能否由入栈序列能否由入栈序列A、B、C、D、E得到出栈序列得到出栈序列CBDAE？DE操作序列：操作序列：出栈序列：出栈序列：元素元素A入栈入栈A 元素元素B入栈入栈 元素元素C入栈入栈 元素元素C出栈出栈C 元素元素B出栈出栈B 元素元素D入栈入栈D D 元素元素D出栈出栈D 元素元素A出栈出栈A63.1.1 栈的定义及基本运算栈的定义及基本运算n栈的运算演示栈的运算演示(2)
5、能否由入栈序列能否由入栈序列A、B、C、D、E得到出栈序列得到出栈序列CBDAE？E操作序列：操作序列：出栈序列：出栈序列：元素元素A入栈入栈 元素元素B入栈入栈 元素元素C入栈入栈 元素元素C出栈出栈C 元素元素B出栈出栈B 元素元素D入栈入栈 元素元素D出栈出栈D 元素元素A出栈出栈A 元素元素E入栈入栈EE 元素元素E出栈出栈E7 例例3.1 设设有有4个元素个元素a、b、c、d进栈进栈,给给出它出它们们所有可能的出所有可能的出栈栈次序。次序。答答:所有可能的出所有可能的出栈栈次序如下次序如下:abcd abdc acbd acdb adcb bacd badc bcad bcda bd
6、ca cbad cbda cdba dcba8 例例3.2 设设一个一个栈栈的的输输入序列入序列为为A,B,C,D,则则借助借助一个一个栈栈所得到的所得到的输输出序列不可能是出序列不可能是 。(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均在均在栈栈中中,按照入按照入栈顺栈顺序序,在在栈栈中中顺顺序序应为应为D,C,B,A,出出栈栈的的顺顺序只能是序只能是D,C,B,A。所以本。所以本题题答案答案为为D。9 例例3.3
7、已已知知一一个个栈栈的的进进栈栈序序列列是是1,2,3,n,其其输输出出序序列是列是p1,p2,pn,若若p1=n,则则pi的的值值 。(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 例例3.4 设设n个个元元素素进进栈栈序序列列是是1,2,3,n,其其输输出出序序列是列是p1,p2,pn,若若p1=3,则则p2的的值值 。(A)一定是一定是2(B)一定是一定是1(C)不可能是不可能是1 (D)以
8、上都不以上都不对对 答答:当当p1=3时时,说说明明1,2,3先先进进栈栈,立立即即出出栈栈3,然然后后可可能能出出栈栈,即即为为2,也也可可能能4或或后后面面的的元元素素进进栈栈,再再出出栈栈。因因此此,p2可可能能是是2,也也可可能能是是4,n,但但一一定定不不能能是是1。所所以本以本题题答案答案为为C。11n栈的基本运算栈的基本运算（1）初始化栈）初始化栈 InitStack(S)（2）入栈）入栈 Push(S,e)（3）出栈）出栈 Pop(S,e)（4）获取栈顶元素）获取栈顶元素 GetTop(S,e)（5）判断栈是否为空）判断栈是否为空 StackEmpty(S)3.1.1 栈的定义
9、及基本运算栈的定义及基本运算123.1.2 栈的存储结构和实现栈的存储结构和实现anan-1.a2a1栈栈basetop 顺序栈顺序栈顺序栈顺序栈 栈的顺序存储结构简称为顺序栈栈的顺序存储结构简称为顺序栈栈的顺序存储结构简称为顺序栈栈的顺序存储结构简称为顺序栈，即利用，即利用，即利用，即利用一组地址连续的一组地址连续的一组地址连续的一组地址连续的存储单元依次存放存储单元依次存放存储单元依次存放存储单元依次存放自栈底自栈底自栈底自栈底到栈顶到栈顶到栈顶到栈顶的数据元素，同时附设栈顶指针的数据元素，同时附设栈顶指针的数据元素，同时附设栈顶指针的数据元素，同时附设栈顶指针toptop和栈底指针和栈底
10、指针和栈底指针和栈底指针basebase。可用数组来实现顺序栈。可用数组来实现顺序栈。可用数组来实现顺序栈。可用数组来实现顺序栈。l指指 针针 base始始 终终 指指 向向 栈栈 底底 的的 位位 置置，若若base=NULL，则表明栈结构不存在；，则表明栈结构不存在；l 指指针针top的的初初值值指指向向栈栈底底，当当top=base时时为空栈；为空栈；l 约约定定非非空空栈栈中中的的栈栈顶顶指指针针始始终终指指向向栈栈顶顶元元素素的的下下一一个个位位置置上上。每每当当插插入入新新的的栈栈顶顶元元素素时时，指指针针top加加1；删删除除栈栈顶顶元元素素时时，指指针针top减减1。13143
11、.1.2 栈的存储结构和实现栈的存储结构和实现n顺序栈的类型定义顺序栈的类型定义/-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base;/栈底指针，栈构造前和销毁后为空栈底指针，栈构造前和销毁后为空 SElemType *top;/栈顶指针，指向栈顶元素的下一位置栈顶指针，指向栈顶元素的下一位置 int stacksize;/当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位SqStack;15 顺序栈顺序栈顺序栈顺序栈 设设设设
12、S S是是是是SqStackSqStack类型的变量。类型的变量。类型的变量。类型的变量。basebase是栈是栈是栈是栈底指针。底指针。底指针。底指针。toptop是栈顶指针。是栈顶指针。是栈顶指针。是栈顶指针。栈不存在条件栈不存在条件栈不存在条件栈不存在条件S.base=NULLS.base=NULL 栈空条件栈空条件栈空条件栈空条件S.top=S.baseS.top=S.base 插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针插入栈顶元素，栈顶指针S.top=S.top+1S.top=S.top+1 删除栈顶元素，栈顶指针删除栈顶元素，栈顶指针删除栈顶元素，栈顶指针删
13、除栈顶元素，栈顶指针S.top=S.top-1S.top=S.top-1 栈满条件栈满条件栈满条件栈满条件S.top-S.base=S.stacksizeS.top-S.base=S.stacksize3.1.2 栈的存储结构和实现栈的存储结构和实现16 进栈/入栈示例：17出栈/退栈示例：183.1.2 栈的存储结构和实现栈的存储结构和实现n n顺序栈的顺序栈的顺序栈的顺序栈的C C语言实现语言实现语言实现语言实现(1)(1)初始化初始化初始化初始化Status InitStack(SqStack&S)Status InitStack(SqStack&S)/构造一个空栈构造一个空栈构造一个空
14、栈构造一个空栈 S.base=(SElemType*)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);if(!S.base)exit(OVERFLOW);S.top=S.base;S.top=S.base;S.stacksize=S.stacksize=STACK_INIT_SIZE;STACK_INIT_SIZE;return OK;return OK;/InitStack/InitSta
15、ck19(2)判断栈空判断栈空int StackEmpty(SqStack S)return(S.base=S.top);(3)判断栈满判断栈满int StackFull(SqStack S)return(S.top-S.base=S.stacksize);3.1.2 栈的存储结构和实现栈的存储结构和实现20(4)取栈顶元素取栈顶元素Status GetTop(SqStack S,SElemType&e)/若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回OK；否；否则返回则返回ERRORif(S.top=S.base)return ERROR;e=*(S.top-1
16、);/栈顶指针不变栈顶指针不变return OK;213.1.2 栈的存储结构和实现栈的存储结构和实现(5)5)元素入栈元素入栈元素入栈元素入栈Status Push(SqStack&S,SElemType e)if(S.top-S.base=S.stacksize)/栈满，追加存储空间栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)return(OVERFLOW);S.top=S.base+S.stacksize;/修改栈顶指针修改栈顶指
17、针 S.stacksize+=STACKINCREMENT;*S.top+=e;/*S.top=e;S.top=S.top+1;return OK;22(6)(6)出栈操作出栈操作出栈操作出栈操作Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERROR if(S.top=S.base)return ERROR;/栈空栈空 e=*-S.top;/S.top=S.top-1;e=*S.top;return OK;注意：注意：取栈顶元素与出栈不同之处在于出栈操
18、作改变栈顶取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针指针top的位置，而取栈顶元素操作不改变栈的栈顶指针。的位置，而取栈顶元素操作不改变栈的栈顶指针。233.1.2 栈的存储结构和实现栈的存储结构和实现 链栈链栈链栈链栈 栈的链式存储结构称为链栈栈的链式存储结构称为链栈栈的链式存储结构称为链栈栈的链式存储结构称为链栈，它是运算是受限的单，它是运算是受限的单，它是运算是受限的单，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。链表，插入和删除操作仅限制在表头位置上进行。链表，插入和删除操作仅限制在表头位置上进行。链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进
19、行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。单链表那样附加头结点。单链表那样附加头结点。单链表那样附加头结点。栈顶指针就是链表的头指栈顶指针就是链表的头指栈顶指针就是链表的头指栈顶指针就是链表的头指针针针针。链栈的类型说明如下：链栈的类型说明如下：链栈的类型说明如下：链栈的类型说明如下：typedef struct stacknodetypedef struct stacknode SElemType data;SElemType data;struct sta
20、cknode*next;struct stacknode*next;stacknode;stacknode;*LinkStack;243.1.2 栈的存储结构和实现栈的存储结构和实现n链栈链栈anan-1.a2a1栈栈栈底栈底栈顶栈顶S栈的链式存储栈的链式存储an an-1 a1a2 思考思考 链栈是否需要另外设置头指针？链栈是否需要另外设置头指针？建立链栈适合用哪种插入法？建立链栈适合用哪种插入法？链栈的基本操作的实现。链栈的基本操作的实现。l栈空条件：栈空条件：S=NULLl栈满条件：栈满条件：无无25（1 1）进栈操作：）进栈操作：）进栈操作：）进栈操作：Status Push_L(Li
21、nkStack&S，SElemType e)p=(LinkStack)malloc(sizeof(stacknodestacknode);if(!p)exit(Overflow);p-data=e;p-next=S;S=p;/前插法前插法 return OK;(2)(2)出栈操作出栈操作出栈操作出栈操作Status Pop_L(LinkStack&S,SElemType&e)if(!S)return ERROR;e=S-data;p=S;S=S-next;free(p);return OK;263.2 栈的应用举例栈的应用举例根据栈的根据栈的根据栈的根据栈的FILOFILOFILOFILO特性
22、，用作某些处理问题的工具。特性，用作某些处理问题的工具。特性，用作某些处理问题的工具。特性，用作某些处理问题的工具。n n1.1.数制转换数制转换数制转换数制转换例：例：例：例：（4343）10 10=（101011101011）2 2被除数被除数除数除数商商余数余数432211212101102505221221012010 输出输出27void conversion()InitStack(S);/构造空栈构造空栈scanf(“%d”,&n);while(n)Push(S,n%2);n=n/2;while(!StackEmpty(S)Pop(S,e);printf(“%d”,e);3.2 栈
23、的应用举例栈的应用举例28n2.括号匹配括号匹配设一个表达式中可以包含三种括号：设一个表达式中可以包含三种括号：“(”和和“)”、“”和和“”、“”和和“”，并且这三种括号可以按照，并且这三种括号可以按照任意的次序任意的次序嵌套嵌套使用，考查表达式中的括号是否匹配。使用，考查表达式中的括号是否匹配。例如：例如：.(.).).n例：例：a=b+(c-d)*(e-f);while(m(M-2,N-2)int i,j,di,find,k;top+;/初始方块进栈初始方块进栈 Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while(top-1)/栈
24、不空时循环栈不空时循环 i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;/读栈顶元素读栈顶元素 if(i=M-2&j=N-2)/找到了出口找到了出口,输出路径输出路径 printf(迷宫路径如下迷宫路径如下:n);for(k=0;k=top;k+)printf(t(%d,%d),Stackk.i,Stackk.j);if(k+1)%5=0)printf(n);printf(n);return;39 find=0;/未找到通道未找到通道 while(di4&find=0)/找下一个可走方块找下一个可走方块 di+;switch(di)case 0:i=Stack
25、top.i;j=Stacktop.j+1;break;case 1:i=Stacktop.i+1;j=Stacktop.j;break;case 2:i=Stacktop.i;j=Stacktop.j-1;break;case 3:i=Stacktop.i-1;j=Stacktop.j;break;if(mgij=0)find=1;40 if(find=1)/找到了下一个可走方块找到了下一个可走方块 Stacktop.di=di;/修改原栈顶元素的修改原栈顶元素的di值值 top+;/下一个可走方块进栈下一个可走方块进栈 Stacktop.i=i;Stacktop.j=j;Stacktop.d
26、i=-1;mgij=-1;/避免重复走到该方块避免重复走到该方块 else /没有路径可走没有路径可走,则退栈则退栈 top-;/出栈出栈 mgStacktop.iStacktop.j=0;/让该位置变为其他路径可走方块让该位置变为其他路径可走方块 printf(没有可走路径没有可走路径!n);41 4.表达式求值表达式求值算符优先法算符优先法 4+23-10/5 先乘除先乘除,后加减后加减;从左算到右从左算到右 先括号内先括号内,后括号外后括号外 4+23-10/5=4+6-10/5=10-10/5=10-2=8 表达式由表达式由操作数操作数(operand)、运算符运算符(operator
27、)和和界限符界限符(delimiter)组成的。组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算符、关系运算符和逻辑运算符；界限符为左右括号和标识表达式结束的结束符。将运算符和界限符统称为将运算符和界限符统称为算符算符。它们构成的集合命名为。它们构成的集合命名为OP3.2 栈的应用举例栈的应用举例42 四四则则运算法运算法则实际则实际上可以理解上可以理解为为任意两个相任意两个相继继出出现现的算符的算符c1和和c2之之间间的的优优先关系，先关系，优优先关系至多是下列三种关系之一：先关系至多是下列三种关系之一：n 1 2:1的的优优先先权权大于大于 2;用上述求表达式
28、用上述求表达式值值的方法称的方法称为为“算符算符优优先法先法”。下表下表给给出了出了+、-、*、/、（、）、和、（、）、和#的算的算术术运算符运算符间间的的优优先先级级关系。关系。+-*/（）#+-*/（#=算符间的优先关系算符间的优先关系当前待比当前待比较的字符较的字符运算符栈运算符栈栈顶字符栈顶字符 算符优先算法算符优先算法算符优先算法算符优先算法:用两个工作栈。一个称作用两个工作栈。一个称作用两个工作栈。一个称作用两个工作栈。一个称作OPTR,OPTR,用于存用于存用于存用于存放运算符放运算符放运算符放运算符;另一个称作另一个称作另一个称作另一个称作OPND,OPND,用以存放操作数或运
29、算用以存放操作数或运算用以存放操作数或运算用以存放操作数或运算结果。结果。结果。结果。首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符“#”为运算符为运算符为运算符为运算符的栈底元素；的栈底元素；的栈底元素；的栈底元素；依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进依次读入表达式中每个字符，若是操作数则进OPNDOPND栈，若是运算符，则和栈，若是运算符，则和栈，若是运算符，则和栈，若是运算符，则和OPTROPTR栈的栈顶运算符比较优
30、栈的栈顶运算符比较优栈的栈顶运算符比较优栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕先权后作相应操作，直到整个表达式求值完毕(OPTR(OPTR栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为“#”)45OperandType EvaluateExpression()InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPT
31、R)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();else /不是运算符则进栈不是运算符则进栈 switch(Precede(GetTop(OPTR),c)case:/退栈并将运算结果入栈退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/while return GetTop(OPND);/EvaluateExpression3.2 栈的应用举例栈的应用举例473.3 栈与递归的实现栈与递归的实现n栈与递归的实现栈与递归的
32、实现用栈结构实现程序设计语言中函数的嵌套调用和递归用栈结构实现程序设计语言中函数的嵌套调用和递归调用调用例：例：long f(int n)if(n1)return n*f(n-1);else return 1;void main()int n=4;printf(“%ld”,f(n);483.3 栈与递归的实现栈与递归的实现 n n阶阶阶阶HanoiHanoi塔塔塔塔 问题问题问题问题假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为假设有三个分别命名为X X、Y Y和和和和Z Z的塔座，在塔座的塔座，在塔座的塔座，在塔座的塔座，在塔座X X上插有上插有上插有上插有n n个直径大小各不
33、相同、依小到大编号个直径大小各不相同、依小到大编号个直径大小各不相同、依小到大编号个直径大小各不相同、依小到大编号为为为为1 1，2 2，,n,n的圆盘。现要求将的圆盘。现要求将的圆盘。现要求将的圆盘。现要求将X X轴上的轴上的轴上的轴上的n n个圆个圆个圆个圆盘移至塔座盘移至塔座盘移至塔座盘移至塔座Z Z上并仍按同样顺序叠排。上并仍按同样顺序叠排。上并仍按同样顺序叠排。上并仍按同样顺序叠排。每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；每次只能移动一个圆盘；圆盘可以插在圆盘可以插在圆盘可以插在圆盘可以插在X X、Y Y和和和和Z Z中的任一塔座上；中的任一塔座上；中的任一
34、塔座上；中的任一塔座上；任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。之上。之上。之上。493.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Base case:n=1 X Z503.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Base case:n=1 X Z513.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1 个盘个盘:X Y523.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1 个盘个盘:X Y533.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 最大盘最大盘:X Z543.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 最大盘最大盘:X Z553.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1个盘个盘:Y Z563.3 栈与递归的实现栈与递归的实现 n阶阶Hanoi塔问题塔问题Recursion:n 1 前前n-1个盘个盘:Y Z57