2024王道数据结构---队列
1-5题
第一题:逻辑结构包含线性结构和非线性结构,明显栈和队列是线性结构,这是特有属性,无法改变,存储结构可以有顺序结构和链式结构。栈和队列的存储结构即可以是顺序结构和链式结构。 第二题:先进先出是队列的特有属性,删除总是队头,插入总是队尾。 第三题:队列不能进行排序操作,不能在中间插入元素。队列除了队首可以进行删除和队尾进行插入,以及查询对首元素,查询队列长度,没有其他操作。 第四题:队列只能先进先出,所以只能1 2 3 4进队,1 2 3 4出队。 第五题:是一道比较容易出错的题目,从0到n一共有n+1个位置,入队就是rear+1,由于是循环队列,避免假溢出,对maxsize进行取余。 6-10题
第6题:循环队列进行判断队列有效长度,先找到队列的最大容量maxsize=21,再进行判断,如果r>f则r-f,否则r-f+maxsize即可。 第7题:入队rear++ 然后对maxsize取余,出队front++,对maxsize取余即可。 第8题:参照第7题,则(队尾+1)%maxsize==队首,则表明队列已经满了。再插入一个元素,两个指针即将重合,即可能误解为队列。 第9题:最适合做链队的是带首尾指针的非循环单链表。因为方便入队出队,并且单链表维护方便,非循环的链表首尾不同,操作简单。 第10题:最不适合的是只带头指针,不方便维护队尾,双链表,插入删除麻烦。 11-15题
第11题:在单链表中,队头在链表头,队尾在链表尾,方便操作,O(1)解决插入删除。 第12题:可以在链表队列首尾进行插入删除,如果在队首删除,需要改变头指针,如果队列中只有一个元素,在队首删除,也需要改变尾指针rear=front。 第13题:将元素x插入队尾,rear->next=x,x->next=NULL,rear=x并且更新尾指针。 第14题:由于队首在链表尾部,只有头指针,则进队操作的时间复杂度,进队是在队尾进队,即在链表头部进行入队。 第15题:判断队列为空即两个指针位置重合,为满即假设循环队列的插入一个元素(rear+1)%maxsize,如果位置和队首指针重合,则说明队列真溢出,说明队列已经满了。 16-20题
第16题:自定义队列,支持双端插入,一端删除,则依次进队然后再全部出队,说明出队顺序应该是队列顺序或者整体反转,说明输入顺序相邻的字母在队列中的整体应该相邻,选项C中b字母和a字母并不相邻,在插入过程中并不能实现,所以出队序列中不可能有这样的情况。 第17题:入队操作中队列首指针不变化,尾指针进行自增然后对maxsize取余。由于题目说明front指向队列第一个元素,rear指向队列最后一个元素,在队列只插入一个元素,存储在A[0]的位置,说明front原本就是在0的位置,rear应该在n-1的位置,然后rear+1再对n取余得到0。 第18题:经典题目,背的滚瓜烂熟,自己看看就行。