第三章 栈和队列10.17(1).ppt

数据结构数据结构3栈和队列栈和队列13 栈和队列开始学习本章前要掌握：开始学习本章前要掌握：u从数据结构角度看，栈和队列仍属于线性从数据结构角度看，栈和队列仍属于线性结构，具有线性结构的共同特征；结构，具有线性结构的共同特征；u学习本章时，要注意到栈和队列所具有的学习本章时，要注意到栈和队列所具有的线性结构的共性，更要掌握其个性；线性结构的共性，更要掌握其个性；u栈和队列是操作受限的线性结构栈和队列是操作受限的线性结构；23 栈和队列33 栈和队列主要内容主要内容栈的类型定义栈的类型定义栈的表示栈的表示顺序表示顺序表示链表表示链表表示栈的应用栈的应用进制转换进制转换括号匹配括号匹配地图四染色问题地图四染色问题走迷宫走迷宫表达式计算表达式计算栈和递归栈和递归队列的类型定义队列的类型定义队列的表示队列的表示链表表示链表表示顺序表示：循环队列顺序表示：循环队列队列的应用队列的应用杨辉三角杨辉三角划分子集问题划分子集问题农夫过河农夫过河43 栈和队列栈的类型定义栈的类型定义定义定义只允许在同一端删除、同一端插入的线性表只允许在同一端删除、同一端插入的线性表允许插入、删除的一端叫做栈顶允许插入、删除的一端叫做栈顶(top)，另一端，另一端叫做栈底叫做栈底(bottom)bottomtop特性特性先进后出先进后出(FILO,First In Last Out)举例：餐馆的盘子举例：餐馆的盘子53 栈和队列通常通常栈底栈底固定固定，栈顶栈顶移动移动。栈的类型定义栈的类型定义63 栈和队列栈的基本操作栈的基本操作1.插入插入（进栈、入栈）（进栈、入栈）2.删除删除（出栈、退栈）（出栈、退栈）3.测试栈是否为空测试栈是否为空4.测试栈是否已满测试栈是否已满5.检索当前栈顶元素检索当前栈顶元素73 栈和队列(a)栈空。栈顶元素所对应的下标值栈空。栈顶元素所对应的下标值 top=-1。顺序栈的几种状态顺序栈的几种状态(最大长度最大长度maxsize为为4)(b)表示在表示在(a)基础上执行基础上执行Push(S,A)后后的状态。的状态。(c)元素元素B、C、D先后入栈，栈顶元素的下标值先后入栈，栈顶元素的下标值top=3。栈满。栈满。(d)表示在表示在(c)状态下，执行一次状态下，执行一次Pop(S,x)运算得到。运算得到。(e)表示在表示在(d)状态下，执行三次状态下，执行三次Pop(S,x)运算得到。此时栈顶下运算得到。此时栈顶下标值标值 top=-1，又变成栈空状态。又变成栈空状态。top-10123(a)topA0123(b)topBCDA0123(c)topABC0123(d)top-10123(e)83 栈和队列栈的表示：顺序存储结构栈的表示：顺序存储结构一、构造原理一、构造原理 描述栈的顺序存储结构最简单的方法是利用描述栈的顺序存储结构最简单的方法是利用一维数组一维数组datamaxsize来表示，同时定义一个来表示，同时定义一个整型变量整型变量(不妨取名为不妨取名为top)给出栈顶元素的位置。给出栈顶元素的位置。maxsize-193 栈和队列typedef struct datatype datamaxsize;int top;/栈顶指针栈顶指针栈顶指针栈顶指针 SeqStack;初始时，初始时，top=-1103 栈和队列初始化：初始化：栈内没有元素栈内没有元素void SETNULL(SeqStack*s)s-top =-1;int EMPTY(SeqStack*S)if(s-top=-1)return TRUE;else return FALSE;判空栈操作：判空栈操作：01234s-top空栈空栈二、栈的基本操作及算法二、栈的基本操作及算法113 栈和队列SeqStack*PUSH(SeqStack*s,datatype x)/*上溢的情况上溢的情况*/if(s-top=maxsize-1)printf(“overflow”);return NULL;else s-data+s-top=x;return s;进栈操作：进栈操作：栈满栈满s-top856074559001234123 栈和队列 datatype POP(SeqStack*s)/*下溢的情况下溢的情况*/if(EMPTY(s)printf(“underflow”);return NULL;else return s-datas-top-;出栈操作：出栈操作：s-top8560745501234133 栈和队列datatype TOP(SeqStack*s)/*栈空的情况栈空的情况*/if(EMPTY(s)printf(“stack is empty”);return NULL;else return(s-datas-top);取栈顶元素取栈顶元素返回返回“55”s-top8560745501234143 栈和队列(1)如果进站的车厢序列为如果进站的车厢序列为123，则出站车厢序列是什，则出站车厢序列是什么？么？【例例】火车站列车调度示意图如下，假设调度站两侧火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。的轨道为单向行驶轨道。出站出站进站进站123,132,213,231,321(2)如果进站的车厢序列为如果进站的车厢序列为123456，问能否得到，问能否得到135426和和435612的出站序列。的出站序列。153 栈和队列三、多栈共享连续空间的问题三、多栈共享连续空间的问题（以两个栈共享一个数组为例）（以两个栈共享一个数组为例）STACKmaxsizetop0、top1分别为第分别为第1个与第个与第2个栈的栈顶元素指针。个栈的栈顶元素指针。插插入入当当i=1时，将时，将item插入第插入第1个栈，个栈，当当i=2时，将时，将item插入第插入第2个栈。个栈。第第1个栈个栈可用空间可用空间第第2个栈个栈0 1 2 maxsize-1top0top1163 栈和队列maxsize-1第第1个栈个栈可用空间可用空间第第2个栈个栈0 1 2 maxsize-1top0top1173 栈和队列删删除除当当i=1时，删除第时，删除第1个栈的栈顶元素，个栈的栈顶元素，当当i=2时，删除第时，删除第2个栈的栈顶元素。个栈的栈顶元素。top0=-1第第1栈栈空的条件栈栈空的条件top1=maxsize第第2栈栈空的条件栈栈空的条件栈栈空空可用空间可用空间0 1 2 maxsize-1第第1个栈个栈可用空间可用空间第第2个栈个栈0 1 2 maxsize-1top0top1183 栈和队列两个栈的共享存储单元可用两个栈的共享存储单元可用C语言描述如下：语言描述如下：#define maxsize typedef struct datatype datamaxsize;/共享数组的大小共享数组的大小 int top2;/两个栈顶指针两个栈顶指针SeqSTACK;193 栈和队列 栈的链式实现是以链表作为栈的存储结构，并实栈的链式实现是以链表作为栈的存储结构，并实现栈的基本运算。栈的链式实现称为链栈。（现栈的基本运算。栈的链式实现称为链栈。（DCBA四个元素进栈演示）四个元素进栈演示）栈的表示：链式存储栈的表示：链式存储typedef struct node datatype data;struct node*next;LinkSTACK;LinkSTACK*top;B C A栈顶栈顶 栈底栈底topNULLD有没有必要像单链表有没有必要像单链表那样附加头结点那样附加头结点?203 栈和队列栈的表示：链式表示栈的表示：链式表示链式表示链式表示使用链表来实现使用链表来实现栈不就是线性表栈不就是线性表+LIFO限制么？限制么？参照线性表的链式表示参照线性表的链式表示213 栈和队列void Init_LS(LinkSTACK*top)top=NULL;栈初始化栈初始化判栈空判栈空int Empty_LS(LinkSTACK*top)if(top=NULL)return TURE;else return FALSE;223 栈和队列LinkSTACK*Push_LS(LinkSTACK*top,datatype x)LinkSTACK*p;p=(LinkSTACK*)malloc(sizeof(LinkSTACK);p-data=x;/*将将x送到新结点数据域送到新结点数据域*/p-next=top;/*将新结点插在链表最前面将新结点插在链表最前面*/top=p;/*修改栈顶指针的指向修改栈顶指针的指向*/return top;入栈入栈:等效于在链表最前面插入一个新结点等效于在链表最前面插入一个新结点时间复杂度时间复杂度O(1)不必判断栈不必判断栈满满233 栈和队列int*Pop_LS(LinkSTACK*top,datatype x)LinkSTACK*p;if(Empty_LS(top)printf(“Stack underflow.”);/*下溢下溢*/return OVERFLOW;else p=top;/*暂时保存栈顶结点的地址暂时保存栈顶结点的地址*/x=top-data;/*保存被删栈顶的数据信息保存被删栈顶的数据信息*/top=top-next;/*删除栈顶结点删除栈顶结点*/free(p);/*释放被删除结点释放被删除结点*/return OK;出栈出栈:时间复杂度时间复杂度O(1)仍然要判断栈空仍然要判断栈空243 栈和队列int GetTop(LinkSTACK*top,datatype y)if(Empty_LS(top)printf(“Stack underflow.”);/*下溢下溢*/return OVERFLOW;else y=top-data;return OK;取栈顶元素取栈顶元素topdata next A B C253 栈和队列栈的应用栈的应用栈的应用栈的应用颠倒元素顺序颠倒元素顺序直接应用栈先进后出的特性直接应用栈先进后出的特性数制转换数制转换记录记录“历史信息历史信息”括号匹配的检验括号匹配的检验地图四染色问题地图四染色问题走迷宫走迷宫表达式计算表达式计算263 栈和队列栈的应用栈的应用:数制转换数制转换把十进制数转换为八进制数。把十进制数转换为八进制数。例如例如:(1348)10=(2504)8 1348/8=168,1348%8=4最低位最低位 168/8=21,168%8=0 21/8=2,21%8=5 2/8=0,2%8=2最高位最高位(1348)10=1*103+3*102+4*101+8*100;(2504)8=2*83+5*82+0*81+4*80;273 栈和队列数制转换的非递归算法数制转换的非递归算法void conversion(int N)/*把十进制转换为八进制把十进制转换为八进制*/top=-1;/*存放余数的栈清空存放余数的栈清空*/进栈进栈退栈退栈while(N)STACK+top=N%8;/*余数进栈余数进栈*/N=N/8;while(top=0)printf(“%d”,STACKtop-);顺序存储结构的堆顺序存储结构的堆栈栈283 栈和队列数制转换的递归算法数制转换的递归算法void Convert(int n)/*把十进制把十进制n转换为八进制转换为八进制*/if(n!=0)Convert(n/8);printf(“%d”,n%8);293 栈和队列 链式存储结构的堆栈如何实现十进链式存储结构的堆栈如何实现十进制制数数转换成十六进制数？转换成十六进制数？void conversion(int N)LinkSTACK*p,*top=NULL;while(N)p=(LinkSTACK*)malloc(sizeof(LinkSTACK);p-data=N%16;p-next=top;top=p;N=N/16;while(top!=NULL)printf(“%d”,top-data);p=top;top=top-next;free(p);进栈进栈退栈退栈switch(top-data)case 10:printf(“A”);break;case 11:printf(“B”);break;case 12:printf(“C”);break;case 13:printf(“D”);break;case 14:printf(“E”);break;case 15:printf(“F”);break;default:printf(“%d”,top-data);303 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测问题问题括号、引号等符号是成对出现的，必须相互匹配括号、引号等符号是成对出现的，必须相互匹配设计一个算法，自动检测输入的字符串中的括号设计一个算法，自动检测输入的字符串中的括号是否匹配是否匹配比如：比如：()匹配匹配()，()都不匹配都不匹配313 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测括号的匹配规则括号的匹配规则从里向外开始从里向外开始左括号应当和最近的右括号匹配左括号应当和最近的右括号匹配()323 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测思考思考从左向右扫描字符串从左向右扫描字符串()当前是当前是，期待一个，期待一个333 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测思考思考从左向右扫描字符串从左向右扫描字符串()当前是当前是(，和刚才的，和刚才的不匹配，说明相匹配不匹配，说明相匹配的符号还在右边，继续扫描的符号还在右边，继续扫描343 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测思考思考从左向右扫描字符串从左向右扫描字符串()当前是当前是，和刚才的，和刚才的(不匹配，说明相匹配不匹配，说明相匹配的符号还在右边，继续扫描的符号还在右边，继续扫描353 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测思考思考从左向右扫描字符串从左向右扫描字符串()当前是当前是，和刚才的，和刚才的正好一对，可以从字正好一对，可以从字符串中符串中“删去删去”不考虑了不考虑了363 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测思考思考从左向右扫描字符串从左向右扫描字符串()当前是当前是，目前最近的一个是，目前最近的一个是(，不匹配，不匹配，继续扫描继续扫描373 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测发现规律发现规律当扫描到当前字符的时候，需要知道已经扫描当扫描到当前字符的时候，需要知道已经扫描过的字符中，哪一个离它最近过的字符中，哪一个离它最近()因此希望有一个工具，能够记录扫描的历史，因此希望有一个工具，能够记录扫描的历史，这样可以方便的得到最近的上一次访问的字符这样可以方便的得到最近的上一次访问的字符383 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测栈栈“记录历史记录历史”的特性的特性人的记忆：人的记忆：越早发生的事情越难回忆越早发生的事情越难回忆越迟发生的事情越容易回忆越迟发生的事情越容易回忆栈的先进后出栈的先进后出越早压入的元素越晚弹出越早压入的元素越晚弹出越迟压入的元素越早弹出越迟压入的元素越早弹出因此很自然的想到利用栈来模拟记忆因此很自然的想到利用栈来模拟记忆393 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测算法思想算法思想从左向后扫描每一个字符从左向后扫描每一个字符准备一个栈，用于存放扫描过的字符准备一个栈，用于存放扫描过的字符如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较当所有字符都扫描完毕，栈应当为空当所有字符都扫描完毕，栈应当为空若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描403 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈为空，栈为空，当前字符直接入栈当前字符直接入栈如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描413 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符不匹配，栈顶字符和当前字符不匹配，当前字符入栈当前字符入栈(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描423 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符不匹配，栈顶字符和当前字符不匹配，当前字符入栈当前字符入栈(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描433 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符匹配，栈顶字符和当前字符匹配，弹出栈顶字符弹出栈顶字符(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描443 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符不匹配，栈顶字符和当前字符不匹配，当前字符入栈当前字符入栈(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描453 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符匹配，栈顶字符和当前字符匹配，弹出栈顶字符弹出栈顶字符(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描463 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符匹配，栈顶字符和当前字符匹配，弹出栈顶字符弹出栈顶字符(如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描473 栈和队列栈的应用：括号匹配检测栈的应用：括号匹配检测()栈顶字符和当前字符匹配，栈顶字符和当前字符匹配，弹出栈顶字符弹出栈顶字符如果栈为空，直接把当前字符入栈如果栈为空，直接把当前字符入栈否则，把栈顶字符和当前字符比较否则，把栈顶字符和当前字符比较若若匹配匹配，则弹出栈顶字符，继续向前扫描，则弹出栈顶字符，继续向前扫描不匹配不匹配，则当前字符入栈，继续向前扫描，则当前字符入栈，继续向前扫描483 栈和队列栈在回溯法中的应用栈在回溯法中的应用 在某些问题的求解过程中常常采用试在某些问题的求解过程中常常采用试探方法，当某一路径受阻时，需要逆序退探方法，当某一路径受阻时，需要逆序退回，重新选择新路径，这样必须回，重新选择新路径，这样必须用栈记录用栈记录曾经到达的每一状态，栈顶状态即是回退曾经到达的每一状态，栈顶状态即是回退的第一站的第一站。493 栈和队列地图四染色问题地图四染色问题“四染色四染色”定理：定理：用不多于四色对地图着色，使相邻的地用不多于四色对地图着色，使相邻的地区不重色。区不重色。算法思想算法思想 ：“回溯回溯”法法从第一号地区开始逐一染色，每一个地区逐次用色数从第一号地区开始逐一染色，每一个地区逐次用色数1、2、3、4进行试探进行试探；若当前所取的色数与周围已染色的地区不重色，则用栈记下若当前所取的色数与周围已染色的地区不重色，则用栈记下该地区的色数，否则依次用下一色数进行试探；该地区的色数，否则依次用下一色数进行试探；若出现用若出现用1.4色均与相邻地区发生重色，则需退栈回溯，色均与相邻地区发生重色，则需退栈回溯，修改当前栈顶的色数。修改当前栈顶的色数。503 栈和队列地图四染色问题算法实现地图四染色问题算法实现数据结构：数据结构：rnn：nn的关系矩阵，的关系矩阵，rij=0 表示表示i与与j不相邻不相邻,rij=1 表示表示i与与j相邻。相邻。Sn：栈的顺序存储。栈的顺序存储。Si表示表示i号地区所使用的号地区所使用的染色号数。染色号数。(1)(2)(4)(5)(6)(7)(3)1#紫色紫色 2#黄色黄色3#红色红色 4#绿色绿色513 栈和队列(1)(2)(4)(5)(6)(7)(3)r771 2 3 4 5 6 71 2 3 4 5 6 71 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01#紫色紫色 2#黄色黄色3#红色红色4#绿色绿色地图四染色算法地图四染色算法123456712243 4332431523 栈和队列