考研笔记

队列与循环队列

循环队列的题目每次都换一种指针约定。 教材【命题追踪】列了「特定条件下循环队列队头/队尾指针的初值」（2011）和「队空/队满的判断条件」（2014）；链式队列一侧是「根据需求分析队列适合的存储结构」（2019 综合题）。三种判空判满方案的完整对照在 速查：栈与队列的判空判满，本页讲怎么应对换了约定的题目。

机制

3.2.1 队列的基本概念

队列（Queue）也是一种操作受限的线性表，只允许在表的一端进行插入，在另一端进行删除。操作特性是先进先出（First In First Out，FIFO）。

  • 队头（Front）：允许删除的一端，也称队首。
  • 队尾（Rear）：允许插入的一端。

基本操作：InitQueue、QueueEmpty、EnQueue、DeQueue、GetHead。栈和队列都是操作受限的线性表，不是任何对线性表的操作都可以作为它们的操作，比如不能随便读取栈或队列中间的某个数据。

3.2.2 顺序队列与假溢出

分配一块连续的存储单元，附设两个指针：教材默认 front 指向队首元素，rear 指向队尾元素的下一个位置。

  • 初始：Q.front==Q.rear==0，可以作为队空条件。
  • 入队：队不满时，先送值到队尾元素，再将队尾指针加 1。
  • 出队：队不空时，先取队首元素值，再将队首指针加 1。

Q.rear==MaxSize 不能作为队满条件。 出队几次后，队列中可能只有一个元素，rear 却已经到了 MaxSize，入队出现「上溢出」，但数组中依然存在可以存放元素的空位置——这是假溢出。

3.2.2 循环队列

把存储队列元素的表从逻辑上视为一个环。front 到 MaxSize-1 后再前进一个位置就自动到 0，用取模运算实现：

队首指针进：队尾指针进：队列长度：

出入队时指针都按顺时针方向进 1。队空是 Q.front==Q.rear；入队快于出队时，队尾指针会追上队首指针，队满时也有 Q.front==Q.rear，所以要额外区分。三种处理方式：

方式队空队满
① 牺牲一个单元（较为普遍）Q.front==Q.rear(Q.rear+1)%MaxSize==Q.front
② 增设 sizeQ.size==0Q.size==MaxSize
③ 增设 tag（删除置 0，插入置 1）front==rear 且 tag==0front==rear 且 tag==1

②、③ 两种方式下，队空和队满时都有 Q.front==Q.rear。方式 ① 的队列最多只能存 MaxSize-1 个元素。

边界辨析：

教材注意框：「循环队列是指顺序存储的队列，而不是指逻辑上的循环」，循环单链表表示的队列不能称为循环队列。front 和 rear 的初值并不是固定的。

3.2.3 链式队列

实质是一个同时有队首指针和队尾指针的单链表：队首指针指向队头结点，队尾指针指向队尾结点（单链表的最后一个结点）。

不带头结点带头结点（通常采用）
队空Q.front==NULL && Q.rear==NULLQ.front==Q.rear
入队原队列为空时，front 也要指向新结点Q.rear->next=s; Q.rear=s;
出队删的是最后一个结点时，front 和 rear 都置 NULL删的是最后一个结点时，Q.rear=Q.front

不带头结点的链式队列在操作上往往比较麻烦，所以通常设计成带头结点的单链表，插入和删除操作就统一了。

链式队列特别适合数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。程序中要使用多个队列时，与多个栈的情形一样，最好使用链式队列。

手算模板

约定换了，就先画一个空队列，再入队一个元素，看指针怎么动。 教材注意框：「对于这类具体问题，举一些特例判断往往比直接思考问题能更快得到答案。」

  1. 读约定：front 指向队首元素，还是队首元素的前一个位置？rear 指向队尾元素，还是队尾元素的后一个位置？
  2. 读容量：A[0…n] 有 个单元，取模用 ；A[n] 的下标是 。
  3. 放一个元素：题目通常指定第一个元素存在哪里（如 A[0]）。按约定写出此时的 front、rear，再倒推入队之前的初值。
  4. 求长度：不论哪种约定，只要 front、rear 的「偏移」一致（一个指向元素、另一个指向元素外侧），长度都是 (rear-front+MaxSize)%MaxSize。
题约定结论
2011A[0…n-1]，front 指向队首元素，rear 指向队尾元素，第一个元素存 A[0]入队后 front=rear=0；入队只改 rear，且先加 1 再存，所以初值 front=0，rear=n-1
2014A[0…M-1]，end1 指向队首元素，end2 指向队尾元素的后一个位置，最多存 个队空 end1==end2；队满 end1==(end2+1) mod M（牺牲一个单元）
3.2.5 第 6 题A[21]，front 指向队首元素的前一个位置，rear 指向队尾元素，front=8、rear=3长度
3.2.5 第 7 题A[0…5]，rear=1、front=5，删除一个再加入两个模 6：front=0，rear=3
3.2.5 第 8 题front 指向队首元素的前一个位置，rear 指向队尾元素只有一个元素时 front 在它前一位、rear 指向它；队空是 Q.rear==Q.front

边界

说法判断说明
「栈和队列的主要区别是逻辑结构不同」❌逻辑结构都是线性结构，存储结构也都可顺序可链式。本质区别是插入、删除操作的限定不同
「先进先出指同时插入删除时插入优先」❌指最后插入的元素最后被删除、每次删除的总是最早插入的元素
「取出最近入队的元素是队列的操作」❌队列只能删除队首元素；取最近入队的元素是栈的行为
「Q.rear==MaxSize 可作为顺序队列的队满条件」❌会出现假溢出
「循环队列就是用循环链表实现的队列」❌循环队列指顺序存储的队列
「A[0…n] 的循环队列入队用 mod n」❌有 个单元，用 mod (n+1)
「牺牲一个单元时能存 MaxSize 个元素」❌最多 MaxSize-1 个
「链式队列的长度不受限制」❌也受内存空间限制，不能无限增长
「链式队列入队出队比顺序队列快」❌两者都是
「链式队列不能顺序访问」❌能。它的缺点是不能用队首、队尾指针直接算出长度
「链式队列出队只修改头指针」❌只剩一个元素时，删除后尾指针也要修改
「链式队列入队执行 rear->next=x; rear=x; 即可」⚠️不严密。队尾的 x->next 必须置空
「用单链表实现队列，队头设在链尾」❌队头设在链头，便于删除

选链表做队列：最适合的是带队首指针和队尾指针的非循环单链表；做成循环的对队列来说是多余的。最不适合的是只带队首指针的非循环双链表：入队要改队尾结点的指针域，找队尾需要 。循环单链表只设头指针、队头固定在链表尾时，入队是 （3.2.5 第 17 题）。

错题复盘：2019 设计一个空间只增不减、出入队都是 的队列

要求：初始为空；入队时允许增加占用空间；出队元素的空间可重复使用，整个队列占用的空间只增不减；入队、出队都是 。

  1. 选链式存储：顺序存储无法随入队而增加空间。
  2. 做成首尾相接的循环单链表，出队的结点不释放，留给后面入队复用。仿照循环队列牺牲一个空闲结点区分空与满：初始只有一个空结点，front 和 rear 都指向它。队空 front==rear；队满 front==rear->next。
  3. 第一个元素入队后：元素存在原空结点中，rear 后移，此时要另开辟一个空闲结点。
  4. 入队：若 front==rear->next（满），先在 rear 后插入一个新的空闲结点；再把元素存到 rear 所指结点，rear=rear->next。出队：若 front==rear（空）则失败；否则取 front 所指结点的元素，front=front->next。

这道题把「循环队列牺牲一个单元」的思路搬到了链表上。rear 始终指向一个空闲结点，相当于顺序循环队列里「rear 指向队尾元素的下一个位置」。

考点

  • FIFO；队头删、队尾插；栈与队列的本质区别是操作的限定。
  • 假溢出的成因；循环队列的三条取模公式。
  • 三种判空判满方案，尤其是牺牲一个单元时的队满条件。
  • 换约定的题：2011 求初值、2014 求判空判满，一律先画空队列、再入队一个元素。
  • 链式队列：带头结点判空 front==rear；删最后一个元素时改 rear；2019 设计题。

链接

反向链接