栈和队列补充.ppt

栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,栈的定义,栈顶,栈底,出栈,进栈,栈示意图,例 设有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 答:可以简单地推算,得容易得出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。,例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)。 向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。,队列的定义,队列的入队和出队操作示意图,从前图中看到,图(a)为队列的初始状态,有front=rear成立,该条件可以作为队列空的条件。 那么能不能用rear=MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。 为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。,循环队列首尾相连,当队首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 什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？ 答:在队列的顺序存储结构中,设头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入到队列时,若 rear=MaxSize(初始时rear=0)则发生队列的上溢现象,该元素不能加入队列。 特别要注意的是队列的假溢出现象:队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致。,解决队列上溢的方法有以下几种: (1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低。 (2)当出现假溢出时可采用以下几种方法: 采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)；,每当删除一个队头元素时,则依次移动队中的元素,始终使front指针指向队列中的第一个位置； 采用循环队列方式:把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循“先进先出”的原则。,