《栈和队列补充》PPT课件.ppt

《《栈和队列补充》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《栈和队列补充》PPT课件.ppt（17页珍藏版）》请在三一办公上搜索。

1、栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,栈的定义,栈顶,栈底,出栈,进栈,栈示意图,例 设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,例2 设一个栈的输入序列为A,B,C,D,则

2、借助一个栈所得到的输出序列不可能是。(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。,例3 已知一个栈的进栈序列是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。,

3、例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,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,n,但一定不能是1。所以本题答案为C。,顺序栈进栈和出栈示意图,链栈示意图,队列简称队,它也是一种运算受限的线性表,其限制仅允许在表的一端进行插入,而在表的另一端进行删除。我们把进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成

4、为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。,队列的定义,队列的入队和出队操作示意图,从前图中看到,图(a)为队列的初始状态,有front=rear成立,该条件可以作为队列空的条件。那么能不能用rear=MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。,循环队列首尾

5、相连,当队首front指针满足 front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算()来实现:队首指针进1:front=(front+1)MaxSize 队尾指针进1:rear=(rear+1)MaxSize 循环队列的除头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按逆时针方向进1。,怎样区分这两者之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为:(q-rear+1)%MaxSize=q-front队空条件仍为:q-rear=q-front,循环队的入队和出队操作示意图,例

6、6 什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？答:在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若 rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。,解决队列上溢的方法有以下几种:(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。(2)当出现假溢出时可采用以下几种方法:采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；,每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置；采用循环队列方式:把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循“先进先出”的原则。,