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题：经典题目，背的滚瓜烂熟，自己看看就行。