《栈和队列补充》由会员分享，可在线阅读，更多相关《栈和队列补充（17页珍藏版）》请在金锄头文库上搜索。
1、 栈是一种只能在一端进行插入或删除操作的线栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为性表。表中允许进行插入、删除操作的一端称为栈顶栈顶。 栈栈顶顶的的当当前前位位置置是是动动态态的的,栈栈顶顶的的当当前前位位置置由由一一个个称称为为栈栈顶顶指指针针的的位位置置指指示示器器指指示示。表表的的另另一一端端称为栈底。称为栈底。 当栈中没有数据元素时当栈中没有数据元素时,称为称为空栈空栈。 栈栈的的插插入入操操作作通通常常称称为为进进栈栈或或入入栈栈,栈栈的的删删除除操操作通常称为作通常称为退栈退栈或或出栈出栈。栈的定义栈的定义 栈顶栈顶栈底栈底出栈出栈进栈进栈
2、栈示意图栈示意图 例例 设设有有4个个元元素素a、b、c、d进进栈栈,给给出出它它们们所有可能的出栈次序。所有可能的出栈次序。 答答:所有可能的出栈次序如下所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 例例2 设设一一个个栈栈的的输输入入序序列列为为A,B,C,D,则则借借助助一一个栈所得到的输出序列不可能是个栈所得到的输出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答答:可可以以简简单单地地推推算算,得得容容易
3、易得得出出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, , p
4、n=1推断出推断出pi=n-i+1,所以本题答案为所以本题答案为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。
5、顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图链栈示意图链栈示意图 队列简称队队列简称队,它也是一种运算受限的线性表它也是一种运算受限的线性表,其限其限制仅允许在表的一端进行插入制仅允许在表的一端进行插入,而在表的另一端进行删而在表的另一端进行删除。除。 我们把进行插入的一端称做我们把进行插入的一端称做队尾队尾(rear),进行删除进行删除的一端称做的一端称做队首队首(front)。 向队列中插入新元素称为向队列中插入新元素称为进队进队或或入队入队,新元素进队新元素进队后就成为新的队尾元素；从队列中删除元素称为后就成为新的队尾元素；从队列中删除元素称为出队出队或或离队离队,元素出队后元素出队后,
6、其后继元素就成为队首元素。其后继元素就成为队首元素。 队列的定义队列的定义 队列的入队和出队操作示意图队列的入队和出队操作示意图 从从 前前 图图 中中 看看 到到 ,图图 (a)为为 队队 列列 的的 初初 始始 状状 态态 ,有有front=rear成立成立,该条件可以作为队列空的条件。该条件可以作为队列空的条件。 那那么么能能不不能能用用rear=MaxSize-1作作为为队队满满的的条条件件呢呢？显显然然不不能能,在在图图(d)中中,队队列列为为空空,但但仍仍满满足足该该条条件件。这这时时入入队队时时出出现现“上上溢溢出出”,这这种种溢溢出出并并不不是是真真正正的的溢溢出出,在在ele
7、m数数组组中中存存在在可可以以存存放放元元素素的的空空位位置置,所所以以这这是是一一种假溢出。种假溢出。 为为了了能能够够充充分分地地使使用用数数组组中中的的存存储储空空间间,把把数数组组的的前前端端和和后后端端连连接接起起来来,形形成成一一个个环环形形的的顺顺序序表表,即即把把存存储储队列元素的表从逻辑上看成一个环队列元素的表从逻辑上看成一个环,称为循环队列。称为循环队列。 循环队列首尾相连循环队列首尾相连,当队首当队首front指针满足指针满足 front=MaxSize-1后后,再前进一个位置就自动到再前进一个位置就自动到0,这可这可以利用除法取余的运算以利用除法取余的运算()来实现来实
8、现: 队首指针进队首指针进1:front=(front+1)MaxSize 队尾指针进队尾指针进1:rear=(rear+1)MaxSize 循循环环队队列列的的除除头头指指针针和和队队尾尾指指针针初初始始化化时时都都置置0:front=rear=0。在在入入队队元元素素和和出出队队元元素素时时,指指针针都都按按逆时针方向进逆时针方向进1。 怎样区分这两者之间的差别呢怎样区分这两者之间的差别呢?在入队时少用一个在入队时少用一个数据元素空间数据元素空间,以队尾指针加以队尾指针加1等于队首指针判断队满等于队首指针判断队满,即队满条件为即队满条件为: (q-rear+1) % MaxSize=q-f
9、ront队空条件仍为队空条件仍为: q-rear=q-front循环队的入队和出队操作示意图循环队的入队和出队操作示意图 例例6 什什么么是是队队列列的的上上溢溢现现象象和和假假溢溢出出现现象象？解解决决它它们有哪些方法？们有哪些方法？ 答答:在在队队列列的的顺顺序序存存储储结结构构中中,设设头头指指针针为为front,队队尾尾指指针针rear,队队的的容容量量(存存储储空空间间的的大大小小)为为MaxSize。当当有有元元素素加加入入到到队队列列时时,若若 rear=MaxSize(初初始始时时rear=0)则则发生队列的上溢现象发生队列的上溢现象,该元素不能加入队列。该元素不能加入队列。
10、特特别别要要注注意意的的是是队队列列的的假假溢溢出出现现象象:队队列列中中还还有有剩剩余余空空间间但但元元素素却却不不能能进进入入队队列列,造造成成这这种种现现象象的的原原因因是是由于队列的操作方法所致。由于队列的操作方法所致。 解决队列上溢的方法有以下几种解决队列上溢的方法有以下几种: (1)建建立立一一个个足足够够大大的的存存储储空空间间,但但这这样样做做会会造造成成空空间间的使用效率降低。的使用效率降低。 (2)当出现假溢出时可采用以下几种方法当出现假溢出时可采用以下几种方法: 采采用用平平移移元元素素的的方方法法:每每当当队队列列中中加加入入一一个个元元素素时时,队队列列中中已已有有的的元元素素向向队队头头移移动动一一个个位位置置(当当然然要要有有空空闲闲的空间可供移动的空间可供移动)； 每每当当删删除除一一个个队队头头元元素素时时,则则依依次次移移动动队队中中的的元素元素,始终使始终使front指针指向队列中的第一个位置；指针指向队列中的第一个位置； 采采用用循循环环队队列列方方式式:把把队队列列看看成成一一个个首首尾尾相相接接的的循循环环队队列列,在在循循环环队队列列上上进进行行插插入入或或删删除除运运算算时时仍仍然遵循然遵循“先进先出先进先出”的原则的原则。
