首页 > 编程学习 > 第三章:栈/队列 重点题

第三章:栈/队列 重点题

发布时间:2022/11/10 9:04:04

1. 栈(Stack)是一种操作受限(只允许在一边进行插入或者删除操作)的线性表,遵循先进后出(也称后进先出)原则 Last In First Out ;

(1) 若一个栈的输入序列是1,2,3…, n , 输出序列的第一个元素是n ,则第i 个输出的元素是:n-i+1

分析:第一个输出的元素如果是n,证明1~n-1顺序入栈且还在栈中,此时按照栈的特性,后进先出,依次出栈的顺序是:
第二个:n-1
第三个:n-2
第四个:n-3

第n个:1
所以第i个输出的元素的按照规律就是:n-i+1

(2) 若一个栈的输入序列是1,2,3…, n , 输出序列的第一个元素是i ,则第j 个输出的元素是:不确定

该题跟第一题类似,但是因为第一个输出的元素i不确定,自然没法推断第j个输出的元素

(3)若一个栈的输入序列是P1,P2,P3…Pn ,输出序列是1,2,3…n, 若P3 = 1;P1的值不可能是:2

假设P1进,P2进,P3进,P3出(输出1),
按照题目的输出序列,第二个输出的必须是2,此时P3和P1中间隔着P2,所以必须P2出完,P1才能出栈,所以,P1绝对不可能是2,但是从P4~Pn都有可能是2,设 i 属于4~n范围内且Pi=2,则Pi进,Pi出,马上可以得到1,2的输出序列

(4)已知一个栈的入栈序列是1,2,3,4,出栈序列P1,P2,P3,P4,则P2,P4 不可能是:C
A:2,4 B:2,1 C:4,3 D:3,4

A选项,1进1出(P1),2进2出(P2),3进3出(P3),4进4出(P4)即可得P2=2,P4=4
B选项,1进,2进,3进3出(P1),2出(P2),4进4出(P3),1出(P4),即可得P2=2,P4=1
C选项,1进1出(P1),2进,3进,4进4出(P2),此时,只能要出栈只能3出(P3),最后2出(P4),P4不可能是3
D选项,1进1出(P1),2进,3进3出(P2),2出(P3),4进4出(P4),即可得P2=3,P4=4

(5)设有一个顺序共享栈Share[0:n-1] ,其中第一个栈顶指针top1初始值为-1,第二个栈顶指针top2初始值为n,则判断栈满条件是:A
A:top2-top11 B:top1-top21 C:top1==top2 D:以上都不对

分析:
共享栈,迎面增长的方式,top1入栈一个元素,则栈顶指针top1为0,入栈第二个,则栈顶指针top1为1,以此类推
top2入栈一个栈顶指针top2为n-1,入栈第二个为n-2…
当. top2 - 1 == top1 的时候,即第二个栈还想放元素,但是已经碰到第一个栈的栈顶指针了,即下一个位置已经是别人的栈顶,也就是共享栈已经满了,不能再放了,所以,当 : top2 - top1 = 1时,栈满。A正确
B选项top1比top2还大,这已经是顶过头了,把第一个栈的元素装到第二个栈范围里面去了,记住top1永远比top2指针小才对
C选项top1=top2,这表示两个栈顶挤在同一个下标,这样错得离谱了,根本搞不清楚当前下标的数组位置装的是哪个栈的元素。所以❌

(6)【2013】一个栈的入栈序列1,2,3,… n ;出栈序列是 P1,P2,P3…Pn ,若P2=3, P3 可能取值的个数是:n-1

因为P2=3
1进,2进2出(P1),3进3出(P2),1出(P3),P3可以等于1
1进1出(P1)2进,3进3出(P2),2出(P3),P3可以等于2
1进2进任意一个出(P1),3进3出(P2),4~n进,任意一个出(P3)
由此很清晰看出,P3 可以是:1,2,4,5…n
所以P3取值个数是 n-1
本题最主要是逐个判断通过出入栈组合,列举出P3的可能取值。

2. 队列(Queue)一种操作受限(仅能从一边进,另外一边出)的线性表,先入先出原则 First In First Out ,插入元素叫入队,删除元素叫出队。很好理解,就是我们日常生活中的排队。

队列需要经常操作队头和队尾元素,所以采用的数据结构一定要能方便操作队头和队尾!
在我们使用数组顺序存储队列时,会出现所谓的“假溢出”,也就是队列只有一个元素,但是也判断说队列已满,例如:

假设队尾指针是rear,队头指针front,初始化时候front=rear=0 (队空)
有一个元素进队,rear往后挪一位,即rear=rear+1(想像成队伍越排越长,很好理解), 直到rear = MaxSize最大值,此时如果没有元素出队,那么确实队满没错。
有一个元素出队,front指针往后挪一位,不断出队,不断的front+1;直到front=MaxSize=rear;即所有元素都出队完了,此时是队空。
这个时候,有个新元素A想进来,判断条件如果是if(rear==MaxSize)则队满,此时新元素A就无法进队,但是明明队空,却还无法进栈,这就很不合理!但是我们能想象出来,最主要原因是出完队之后,旧的下标位置没能循环利用。

此时就要使用 循环队列。

所谓循环队列,仅仅是逻辑上看做一个首尾相连环状队列,实际物理存储还是一个顺序队列,同时,进队出队和判断队满条件有如下逻辑:

入队:rear = (rear+1) % MaxSize
出队:front =(front+1)% MaxSize
队列长度:(rear - front + MaxSize) % MaxSize

例如:
假设MaxSize = 10 ; rear = 0, front = 0
(记住rear指的是下一个元素进来存放的下标。front指的是下一个要出队的元素的下标)
A入队,A放到0号位 ,队尾指针 rear = (0+1)%10 = 1
B入队,B放到1号位,队尾指针 rear = (1+1)%10 = 2

J入队,J放到9号位,队尾指针 rear = (9+1)%10 = 0 (此时队尾指针又指回0,就意味着可以循环入队元素了)

此时由于没有元素出队,front=0=rear,此时可看到,front=0=rear 既是初始化时候的队空,又是队满,无法通过front=0=rear判断是队空还是队满,所以最最直观的方法,就是《牺牲一个存储单元做标志》:

if ( (rear + 1 ) % MaxSize == front ) 就是队满

所以按照上面的例子,J无法入队,因为 (9+1)%10 = 0 , 队满!
当A出队,front = (front + 1) % MaxSize = (0+1)%10 = 1;
此时J要入队,rear= (9+1)%10 = 0
rear != front ,允许入队!
此时队列长度:(0-1+10)%10 = 9
这样就解决了队列的顺序存储问题~

公式记忆:

初始化时,队空头等于尾 rear=front
同一个公式:XX =(XX+1)%MaxSize
入队XX就是rear,出队XX就是front
(rear-front+MaxSize)%MaxSize 求队列长度

(1)循环队列存储在A[0…n] 中,入队时候的操作是:rear = (rear+1) % (n+1)

还是一样套用公式,但是要找准这里的最大长度MaxSize是从0~n,即n+1长度

(2)已知循环队列的存储空间为数组A[21],front指向队头元素的前一个位置,rear指向队尾元素,假设当前front和rear的值分别为8和3,该队列的长度是:

在上面例子中,我们假设的是front指向队头元素(也就是下一个要出队的位置),rear指向队尾下一个位置(即下一个元素进来可以直接存放的位置),该题目把front和rear整体前移了1,不影响套公式:
最大长度是: (rear-front+MaxSize)%MaxSize = (3-8+21)%21 = 16

(3)已知循环队列的存储空间为数组A[0…6],front指向队头元素的前一个位置,rear指向队尾后一个元素,假设当前front和rear的值分别为1和6,该队列的长度是:

分析:
MaxSize = 7
因为front指向队头元素前一位置,所以套用公式中front = front + 1 = 2
rear指向队尾后一个元素,所以rear不用改变
最大长度是: (rear-front+MaxSize)%MaxSize = (6-2+7)%7 = 4,
即队列中有四个元素。(可画图验证)

(4)若用数组A[0…5]来实现循环队列,且当前rear和front值分别是1和5,当从队中删除一个元素,再加入两个元素后,rear和front的值分别是:rear = 3 front=5

MaxSize = 6
套用公式:
出队一个:(front + 1 )%MaxSize = (5+1)% 6 = 0
入队一个:(rear + 1 )%MaxSize = (1+1) % 6 = 2
再入队一个:(rear + 1 )%MaxSize = (2+1) % 6 = 3
即可得:rear = 3 front=5

(5)已知循环队列存储在一维数组A[0…n-1]中,且队列非空时,front和rear分别指向队头元素和队尾元素,若初始队列为空,且要求第一个进入队列的元素存储在A[0]处,则初始时front和rear的值分别是:

公式:
MaxSize = n
入队一个:(rear+1)% n = 0 ;
求得原始的rear = n-1
又因为入队一个后,队列非空,front和rear分别指向队头和队尾,即都是指向同一个那个元素, 而入队操作不改变front的值
得:
front = 0
所以原始的rear = n-1 ; front = 0

(6) 循环队列放在一维数组A[0…M-1]中,end1指向头元素,end2指向队尾元素后一个位置,假设队列两端均可以进行出队入队操作,队列中最多容纳M-1个元素,初始时为空
则判断队空的条件是:end1 = = end2

因为题目的循环队列最多容纳M-1个元素,所以它预留了一个做为队满的标志,这种队列队空的判断就是front = rear

判断队满的条件是:(end2 + 1) % M = end1

队满只会发生在入队时判断,不会发生在出队(从没听说过队满不能出队的),所以肯定是尾指针+1做入队,从0~M-1. MaxSize = M
同时尾指针指向队尾元素的再后一个位置,那么当队尾指针的再下一个就是头,则是队满了,也可以理解为这时候队尾指针起着队满标志的作用。

(7)假设循环单链表表示的队列长度为n,队头固定在链表尾,若只设头指针,则进队操作的时间复杂度为:

分析:这个题目出得比较绕,很难理解,而且很容易误解,这里要区分链表尾和队尾,链表头和队头,还有头指针。这几者的区别和在这道题中各自扮演的角色。其中最重要的是理解在新结点入队后,为什么时间复杂度是O(n) ,主要是因为维护循环单链表特性,只能从头指针循环一遍,找到链表尾,把链表尾(队头)的next链接到新的链表头(队尾),看下面示意图:
在这里插入图片描述

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式