《栈和队列补充》PPT课件

《《栈和队列补充》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。栈的定义栈顶栈底出栈进栈栈示意图例设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba例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,所以本题答

3、案为C。例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->fr

6、ont队空条件仍为:q->rear==q->front循环队的入队和出队操作示意图例6什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？答:在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。解决队列上溢的方法有以下几种:(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。

7、(2)当出现假溢出时可采用以下几种方法:①采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；②每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置；③采用循环队列方式:把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循“先进先出”的原则。