资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,(,Java版,)(第,2,版),*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,(,Java版,)(第,2,版),*,第3章 栈和队列,3.1,栈,3.2,队列,目的:,使用栈或队列求解应用问题。,要求:,掌握栈和队列抽象数据类型,以及顺 序和链式存储结构实现;理解对于怎 样的应用问题,需要使用栈或队列,以及怎样使用。,重点:,栈和队列的设计和应用。,难点:,栈或队列的使用场合,以及如何使用 栈和队列求解应用问题。,数据结构,(,Java版,)(第,2,版),第3章 栈和队列,栈(,stack,)或队(,queue),是一种特殊(对操作位置做限制)的线性表,,,其插入和删除操作只允许在线性表的一端进行。,数据结构,(,Java版,)(第,2,版),3.1 栈,3.1.1,栈抽象数据类型,3.1.2,顺序栈,3.1.3,链式栈,3.1.4,栈的应用,数据结构,(,Java版,)(第,2,版),栈:,限定仅在,表尾,进行插入或删除操作的线,性表,表尾,栈顶,,表头,栈底,,不含元素的空表称,空栈,特点:,先进后出(,FILO,),或后进先出(,LIFO,),a,n,a,1,a,2,.,栈底,栈顶,.,出栈,进栈,栈,s=(a1,a2,an),堆,3.1.1,栈抽象数据类型,栈的定义,数据结构,(,Java版,)(第,2,版),3.1.1 栈抽象数据类型,public interface SStack,boolean isEmpty();/,判断是否空栈,boolean push(E element);/,入栈,E pop();/,出栈,E get();/,取栈顶元素值,数据结构,(,Java版,)(第,2,版),3.1.2 顺序栈,public class SeqStack implements SStack,private Object value;,private int top;/,栈顶元素下标,顺序栈,数据结构,(,Java版,)(第,2,版),Top=-1,1,2,3,4,5,0,栈空,栈顶指针,top,指向实际栈顶,初值为-1,top,1,2,3,4,5,0,进栈,A,top,出栈,栈满,B,C,D,E,F,设数组大小为,M,top=,-1,栈空,此时出栈,则,下溢,(,underflow),top=,M-1,栈满,此时入栈,则,上溢,(,overflow),top,top,top,top,top,1,2,3,4,5,0,A,B,C,D,E,F,top,top,top,top,top,top,栈空,栈顶,top,的值为栈顶元素下标。,数据结构,(,Java版,)(第,2,版),例:对于一个栈,给出输入项,A、B、C,,如果输入项序列由,ABC,组成,试给出所有可能的输出序列。,A,进,A,出,B,进,B,出,C,进,C,出,ABC,A,进,A,出,B,进,C,进,C,出,B,出,ACB,A,进,B,进,B,出,A,出,C,进,C,出,BAC,A,进,B,进,B,出,C,进,C,出,A,出,BCA,A,进,B,进,C,进,C,出,B,出,A,出,CBA,不可能产生输出序列,CAB,数据结构,(,Java版,)(第,2,版),3.1.3 链式栈,public class LinkedStack,implements SStack,private Node top;,链栈,数据结构,(,Java版,)(第,2,版),3.1.4 栈的应用,栈是嵌套调用机制的实现基础,使用栈以非递归方式实现递归算法,数据结构,(,Java版,)(第,2,版),例,3.1,判断表达式中圆括号是否匹配,括号匹配,数据结构,(,Java版,)(第,2,版),例3.2 使用栈计算表达式的值,中缀表达式,1+2*(3-4)+5,数据结构,(,Java版,)(第,2,版),例如:3*(7 2),(1)要正确求值,首先了解算术四则运算的规则:,a.,从左算到右,b.,先乘除,后加减,c.,先括号内,后括号外,由此,此表达式的计算顺序为:,3*(7 2)=3*5=15,例,3.2,使用栈计算表达式的值,数据结构,(,Java版,)(第,2,版),(2)根据上述三条运算规则,在运算的每一步中,对任意相继出现的算符,1,和,2,,都要比较优先权关系。,例,3.2,使用栈计算表达式的值,数据结构,(,Java版,)(第,2,版),当前运算符,栈顶运算符,栈顶运算符,当前运算符,运算符的优先级比较,数据结构,(,Java版,)(第,2,版),(3)算法思想:,设栈:,操作符栈来保存扫描字符串所依次得到的操作符,依次读入字符:,比较栈顶元素与当前操作符优先级大小,if,操作符 栈顶元素,,操作符入栈。,例,3.2,使用栈计算表达式的值,数据结构,(,Java版,)(第,2,版),1.,将中缀表达式转换为后缀表达式,转换,数据结构,(,Java版,)(第,2,版),2.后缀表达式求值,数据结构,(,Java版,)(第,2,版),3.2 队列,3.2.1,队列抽象数据类型,3.2.2,顺序队列,3.2.3,链式队列,3.2.4,队列的应用,数据结构,(,Java版,)(第,2,版),3.2 队列,前面所讲的栈是一种后进先出的数据结构,而在实际问题中还经常使用一种“先进先出”,(,FIFO-First In First Out),的数据结构:即插入在表一端进行,而删除在表的另一端进行,我们将这种数据结构称为队或队列,把允许插入的一端叫队尾,(,rear),,,把允许删除的一端叫队头,(,front),。,显然,队列也是一种运算受限制的线性表。,数据结构,(,Java版,)(第,2,版),3.2.1 队列抽象数据类型,队列(,queue,)是一种特殊的线性表,其插入和删除操作分别在线性表的两端(相应叫做队头、队尾)进行。,public interface QQueue /,队列接口,boolean isEmpty();/,判断队列是否为空,boolean enqueue(E element);/,入队,E dequeue();/,出队,数据结构,(,Java版,)(第,2,版),3.2.2 顺序队列,顺序存储的队称为顺序队。因为队的队头和队尾都是活动的,因此,除了队列的数据区外还有队头(,front)、,队尾(,rear),两个指针。,空队时:,front=rear=-1;,即指向实际的队头和队尾。,数据结构,(,Java版,)(第,2,版),3.2.2 顺序队列,顺序队列,假溢出,数据结构,(,Java版,)(第,2,版),从图中可以看到,随着入队出队的进行,会使整个队列整体向后移动,这样就出现:队尾指针已经移到了最后,再有元素入队就会出现溢出,而事实上此时队中并未真的“满员,”,,这种现象为,“假溢出”,,这是由于“队尾入队头出”这种受限制的操作所造成。,3.2.2,顺序队列,数据结构,(,Java版,)(第,2,版),解决假溢出的方法之一是将队列的数据区(0,MAXSIZE-1),看成头尾相接的循环结构,头尾指针的关系不变,将其称为“循环队”。,2.,顺序循环队列,数据结构,(,Java版,)(第,2,版),2.顺序循环队列,front=(front+1)%length;,初始时,front=0;,rear=(rear+1)%length;,初始时,rear=0;,数据结构,(,Java版,)(第,2,版),2.顺序循环队列,但在这种设计下,队满情况下有:,front=rear,;,在队空情况下也有:,front=rear,。,就是说“队满”和“队空”的条件是相同的了。,解决方法:,方法之一,是附设一个存储队中元素个数的变量如,num,,当,num=0,时队空,当,num=length,时为队满。,另一种方法,是少用一个元素空间,情况就视为队满,此时的状态是若队尾指针加,1,就会从后面赶上队头指针,这种情况情况就视为队满,所以队满的条件是:,(,rear+1)%length=front,,,也能和空队区别开(,front=rear,)。,数据结构,(,Java版,)(第,2,版),3.顺序循环队列类,public class SeqQueue implements QQueue,private Object value;,private int front,rear;/,队列头尾下标,顺序循环队列,数据结构,(,Java版,)(第,2,版),3.2.3 链式队列,public class LinkedQueue implements QQueue /,链式队列类,private Node front,rear;,链队,数据结构,(,Java版,)(第,2,版),队列的应用-走迷宫,数据结构,(,Java版,)(第,2,版),求迷宫的最短路径:现要求设计一个算法找一条从迷宫入口到出口的最短路径。,本算法要求找一条迷宫的最短路径,算法的基本思想为:,从迷宫入口点(0,0)出发,向四周搜索,记下所有一步能到达的坐标点,;然后依次再从这些点出发,再记下所有一步能到达的坐标点,依此类推,,直到到达迷宫的出口点(,m,n),为止,然后从出口点沿搜索路径回溯直至入口,。这样就找到了一条迷宫的最短路径,否则迷宫无路径。,队列的应用-走迷宫,数据结构,(,Java版,)(第,2,版),主要问题包括:,1),有关迷宫的数据结构、,2)试探方向、,3)如何防止重复到达某点以避免发生死循环的问题、,4)如何存储搜索路径、,5)回溯。,队列的应用-走迷宫,数据结构,(,Java版,)(第,2,版),在搜索过程中必须记下每一个可到达的坐标点,由于先到达的点先向下搜索,故引进一个“先进先出”数据结构-队列来保存已到达的坐标点。到达迷宫的出口点(,m,n),后,为了能够从出口点沿搜索路径回溯直至入口,对于每一点,记下坐标点的同时,还要记下到达该点的前驱点,因此,用一个顺序队列存储走迷宫时经过的每个点,每个点有三个域:,x,y,和,z,,其中,x,y,分别为所到达的点的坐标,,z,为前驱点在队列中的坐标,是一个静态链域。此外,还有队头、队尾指针:,front,和,rear,用来指向队头和队尾元素。,队列的应用-走迷宫,数据结构,(,Java版,)(第,2,版),初始状态,队列中只有一个元素,记录的是入口点的坐标(0,0),因为该点是出发点,因此没有前驱点,,z,域为,此后搜索时都是以,front,所指点为搜索的出发点,当搜索到一个可到达点时,即将该点的坐标及,front,所指点的位置入队,不但记下了到达点的坐标,还记下了它的前驱点。,front,所指点的个方向搜索完毕后,则出队,继续对下一点搜索。搜索过程中遇到出口点则成功,搜索结束,打印出迷宫最短路径,算法结束;或者当前队空即没有搜索点了,表明没有路径算法也结束。,队列的应用-走迷宫,数据结构,(,Java版,)(第,2,版),队列的应用-走迷宫,入口 0 1 2 3 4 5 6 7,0,1,2,3,4,5,数据结构,(,Java版,)(第,2,版),队列的应用-走迷宫,运行结果:(5,7),(4,6),(3,5),(3,4),(2,3),(2,2),(1,1),(0,0),走迷宫,队列,数据结构,(,Java版,)(第,2,版),
展开阅读全文