《刘勇3栈和队列》由会员分享，可在线阅读，更多相关《刘勇3栈和队列（27页珍藏版）》请在金锄头文库上搜索。
1、刘勇3栈和队列Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望定义定义定义定义 只允许在一端插入和删除的线性表；只允许在一端插入和删除的线性表；只允许在一端插入和删除的线性表；只允许在一端插入和删除的线性表； 允许插入和删除的一端称为允许插入和删除的一端称为允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶栈顶栈顶(top)(top)，另一另一另一另一端称为端称为端称为端称为栈底栈底栈底栈底(bottom)(bottom)。特点特点特点特点 后进先出后进先出后进先出后进先出 (
2、LIFO) (LIFO)栈栈 ( Stack )退栈进栈a0an-1an-2topbottom7/20/20242北京化工大学信息学院 数据结构ADT Stack /对象对象:由数据类型为由数据类型为StackData的元素构成的元素构成 void push (StackData x);/进栈进栈 void pop (); /出栈出栈 StackData top (); /取栈顶取栈顶 bool isEmpty (); /判栈空否判栈空否 bool isFull (); /判栈满否判栈满否(顺序栈顺序栈)栈的主要操作栈的主要操作7/20/20243北京化工大学信息学院 数据结构 top空栈to
3、ptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈c7/20/20244北京化工大学信息学院 数据结构topc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop7/20/20245北京化工大学信息学院 数据结构栈的链接表示栈的链接表示 链式栈链式栈链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头链式栈的栈顶在链头链式栈
4、的栈顶在链头适合于多栈操作适合于多栈操作适合于多栈操作适合于多栈操作top7/20/20246北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 1 八进制数八进制数7/20/20247北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 2 括号匹配括号匹配()()()() 匹配)( 不匹配() 不匹配后后出现的左括号出现的左括号先先匹配匹配 栈栈7/20/20248北京化工大学信息学院 数据结构7/20/20249北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 3 行编辑程序行编辑程序# 退格符 退行符switch(ch) case #: s.pop(); break; ca
5、se : s.clear(); break; default: s.push(ch); break;7/20/202410北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 4 迷宫迷宫到了一个位置，先往东东走，走不通再顺时针换方向往南，西，北7/20/202411北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 4 迷宫迷宫求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：1、起点、起点S入栈入栈2、反复执行以下步骤，直到栈为空，或者找到终点、反复执行以下步骤，直到栈为空，或者找到终点E（1）取栈顶）取栈顶m，标记，标记m已被访问，根据已被访问，根据m的方向找到下一个位置的方
6、向找到下一个位置next；（2）如果）如果next不是墙壁，也没有被访问过，将不是墙壁，也没有被访问过，将next入栈入栈（3）否则换方向继续找下一个位置）否则换方向继续找下一个位置（4）4个方向都不能通过，出栈，回到第（个方向都不能通过，出栈，回到第（1）步）步3、找到终点、找到终点E，迷宫走出，迷宫走出 在找到终点在找到终点E之前，栈空了，说明迷宫没有出去的路径之前，栈空了，说明迷宫没有出去的路径7/20/202412北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表达式运算7/20/202413北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表
7、达式运算7/20/202414北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表达式运算操作数栈D，运算符栈O1、操作数入栈D2、遇到运算符OP1，和O栈顶运算符OP2比较：（1）如果OP2优先级高，则将两个栈的元素出栈，做运算，将运算结果入栈D；（2）如果OP1优先级高，OP1入栈O7/20/202415北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 6 出栈合法性出栈合法性算法：1、辅助数组 bool isPushedN+1 = false,1入栈S， isPushed1=true2、遍历出栈序列，对每个数字n，执行以下操作：（1）取S栈顶t，将t,t+1,t
8、+2.n的所有不曾入栈的数字入栈，并在辅助数组中标记对应下标为true（2）取S栈顶t，若s=n，S出栈；若s!=n，则出栈序列非法。已知自然数1，2，.，N（1=N=100）依次入栈，请问序列C1，C2，.，CN是否为合法的出栈序列。如3 4 2 1 5是合法的而3 5 1 4 2不是合法的7/20/202416北京化工大学信息学院 数据结构定义定义定义定义队列是只允许在一端删除，在另一端插入的线性表队列是只允许在一端删除，在另一端插入的线性表队列是只允许在一端删除，在另一端插入的线性表队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做允许删除的一端叫做允许删除的一端叫做允许删除
9、的一端叫做队头队头队头队头(front)(front)，允许插入的一端叫，允许插入的一端叫，允许插入的一端叫，允许插入的一端叫做做做做队尾队尾队尾队尾(rear)(rear)。特性特性特性特性先进先出先进先出先进先出先进先出(FIFO, First In First Out)(FIFO, First In First Out)a0 a1 a2 an-1frontrear队列队列 ( Queue )7/20/202417北京化工大学信息学院 数据结构ADT Queue /对象对象:由数据类型为由数据类型为QueueData的元素构成的元素构成 void push (QueueData x); /
10、进队进队 void pop();/出队出队并取队头并取队头 QueueData front ();/取队头取队头 bool isEmpty (); /判队空否判队空否 bool isFull (); /判队满否判队满否(顺序队列顺序队列)队列的主要操作队列的主要操作7/20/202418北京化工大学信息学院 数据结构队列的进队和出队队列的进队和出队 front rear空队列front rearA进队Afront rearB进队A Bfront rearC, D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进队C D E F
11、 GC D E F Gfront rearH进队,溢出7/20/202419北京化工大学信息学院 数据结构队列的进队和出队原则队列的进队和出队原则n 进队时队尾指针先进一进队时队尾指针先进一进队时队尾指针先进一进队时队尾指针先进一 rear = rear + 1rear = rear + 1，再将新，再将新，再将新，再将新元素按元素按元素按元素按 rear rear 指示位置加入。指示位置加入。指示位置加入。指示位置加入。n n 出队时队头指针先进一出队时队头指针先进一出队时队头指针先进一出队时队头指针先进一 front = front + 1front = front + 1，再将，再将，再
12、将，再将下标为下标为下标为下标为 front front 的元素取出。的元素取出。的元素取出。的元素取出。n 队满时再进队将队满时再进队将队满时再进队将队满时再进队将溢出出错溢出出错溢出出错溢出出错；n n 队空时再出队将队空时再出队将队空时再出队将队空时再出队将队空处理队空处理队空处理队空处理。n n 解决办法之一：将队列元素存放数组首尾相接，解决办法之一：将队列元素存放数组首尾相接，解决办法之一：将队列元素存放数组首尾相接，解决办法之一：将队列元素存放数组首尾相接，形成形成形成形成循环循环循环循环( (环形环形环形环形) )队列队列队列队列。 7/20/202420北京化工大学信息学院 数
13、据结构队列存放数组被当作首尾相接的表处理。队列存放数组被当作首尾相接的表处理。队列存放数组被当作首尾相接的表处理。队列存放数组被当作首尾相接的表处理。队头、队尾指针加队头、队尾指针加队头、队尾指针加队头、队尾指针加1 1时从时从时从时从QueueSize -1QueueSize -1直接进到直接进到直接进到直接进到0 0，可，可，可，可用语言的取模用语言的取模用语言的取模用语言的取模( (余数余数余数余数) )运算实现。运算实现。运算实现。运算实现。队头指针进队头指针进队头指针进队头指针进1:1: front = (front+1) % QueueSize front = (front+1)
14、% QueueSize; ;队尾指针进队尾指针进队尾指针进队尾指针进1: 1: rear = (rear+1) % QueueSizerear = (rear+1) % QueueSize; ;队列初始化：队列初始化：队列初始化：队列初始化：frontfront = = rearrear = 0; = 0;队空条件：队空条件：队空条件：队空条件：frontfront = rearrear; ;队满条件：队满条件：队满条件：队满条件：(rear+1) % QueueSize (rear+1) % QueueSize = front front 循环队列循环队列 (Circular Queue)7
15、/20/202421北京化工大学信息学院 数据结构01234567front01234567front01234567frontrearAABCrearrear空空队列列A进队队B, C进队队0123456701234567A退退队队B退退队队01234567D,E,F,G,H, I进队队frontBCrearAfrontBCrearfrontCrearDEF GHI7/20/202422北京化工大学信息学院 数据结构队列的链接表示队列的链接表示 链式队列链式队列队头在链头，队尾在链尾。队头在链头，队尾在链尾。链式队列在进队时无队满问题，但链式队列在进队时无队满问题，但有队空问题。有队空问题。
16、队空条件为队空条件为 front = NULLfrontrear7/20/202423北京化工大学信息学院 数据结构队列的应用举例队列的应用举例 逐行打印二项展开式逐行打印二项展开式 (a + b)i 的系数的系数杨辉三角形杨辉三角形 (Pascals triangle)7/20/202424北京化工大学信息学院 数据结构分析第分析第 i 行元素与第行元素与第 i+1行元素的关系行元素的关系从前一行的数据可以计算下一行的数据从前一行的数据可以计算下一行的数据0 1 1 0ts+ti = 40 1 3 3 1 0si = 51 4 6 4 1i = 30 1 2 1 07/20/202425北京
17、化工大学信息学院 数据结构从第从第 i 行数据计算并存放第行数据计算并存放第 i+1 行数据行数据1 2 1 0 1 3 3 1 0 1 4 6s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1s+t s=t s=t s=t s=t s=t s=t s=t s=ts+t s+t s+t s+t s+t s+t s+t s+t7/20/202426北京化工大学信息学院 数据结构求第求第n层算法：层算法：（1）初始化队列为）初始化队列为0 1 0，将第将第2、3步循环步循环n-1次次（2）将队列的前两个元素）将队列的前两个元素s,t求和，结果入队，删除求和，结果入队，删除队首队首s，直到，直到t为为0为止为止（3）0入队入队7/20/202427北京化工大学信息学院 数据结构
