题目

请设计一个队列，要求满足：

① 初始时队列为空；

② 入队时，允许增加队列占用空间；

③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；

④ 入队操作和出队操作的时间复杂度始终保持为 O(1)。

请回答下列问题：

(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？

(2) 画出队列的初始状态，并给出判断队空和队满的条件。

(3) 画出第一个元素入队后的队列状态。

(4) 给出入队操作和出队操作的基本过程。

解析

(1) 选择哪种存储结构？

答案：链式存储（具体地，循环单链表 + front 和 rear 两个指针）。

为什么不选顺序存储？

要求 ④"入队/出队始终 O(1)"是关键约束：

• 顺序存储（数组）+ 扩容：当数组用满需要扩容（malloc 新数组 + 拷贝 + free 旧数组），单次入队最坏 O(n)——虽然均摊 O(1)，但题面要求"始终保持 O(1)"，不允许某次入队是 O(n)；
• 链式存储：入队就在 rear 后挂一个新结点（或复用空闲结点），O(1)；出队就移动 front，O(1)。每一次操作都是常数时间，满足要求。

要求 ③"出队元素的空间可重用"——单纯的链队列出队会 free 掉结点，下次入队又要 malloc，没有"复用"。循环单链表（rear->next 指回 front 一带）让出队后的结点暂时留下，下次入队优先重用，这才符合③ 的"只增不减"。

(2) 初始状态、队空与队满判断

初始状态：循环单链表只有一个哨兵结点（不存储队列元素，只起占位作用），front 和 rear 都指向这个哨兵，哨兵->next 指回自身（形成"自环"）。

       ┌──────┐
       │ 哨兵  │ ←── front, rear
       │(无值) │
       └──┬───┘
          │
          └─→ 自身（next 指向自己）

队空判断条件：front == rear。

队满判断条件：rear->next == front（rear 之后下一个就是 front，意味着所有非哨兵结点全部填满数据，没有空闲槽给入队）。

(3) 第一个元素入队后的状态

第一个元素入队时，初始状态满足 rear->next == front（队满，因为只有 1 个哨兵结点不能放数据），需先新建 1 个结点插入 rear 与 front 之间，然后 rear 后移、写入数据：

       ┌──────┐         ┌──────┐
       │ 哨兵  │   ─→   │  x   │ ←── rear
front ─→(无值) │         │      │
       └──┬───┘         └──┬───┘
          ↑                │
          └────────────────┘
                  next

此时 front 指向哨兵，rear 指向新结点（值 = x），新结点的 next 回指 front。

(4) 入队 / 出队的基本过程

入队 enqueue(x)：

1. 检查 Q->rear->next == Q->front：若是（队满，没空闲结点可复用），则 malloc 一个新结点 p，把 p 插入 rear 与 front 之间（p->next = rear->next; rear->next = p）；若否（rear 后面就是空闲结点），跳过此步直接复用；
2. Q->rear = Q->rear->next（rear 前进一格，落到那个待写入的结点上）；
3. Q->rear->data = x（写入数据）。

出队 dequeue()：

1. 检查 Q->front == Q->rear：若是（队空），返回错误；
2. Q->front = Q->front->next（front 前进一格，跳过哨兵或上一个数据结点，新位置就是当前队头）；
3. 返回 Q->front->data（即原队头元素）。注意不释放结点，让它留在链表里，下次 rear 转一圈回来时复用。

编者注（生僻术语）：本题的设计实质是带哨兵的循环空闲链表。front 之前到 rear 这一段是"已用区"（存数据），rear 之后到 front 这一段是"空闲区"（结点保留供下次复用）；入队从空闲区头部"借一个"，出队把已用区头部"释放回去"。如果题目允许动态收缩（违反 ③），可以再加"延迟释放"逻辑；本题不需要。