2019·42 设计可复用空间的队列：约束反推数据结构

本文属于「从暴力解到最优解」专题的第二组。这道题连「算法」都算不上——它是一道数据结构设计题，没有暴力解可以优化。它考的是另一种能力：给你几条约束，反推出唯一合适的数据结构。这种题的分不在跑得多快，在设计判断准不准。

题目

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

① 初始时队列为空； ② 入队时，允许增加队列占用空间； ③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； ④ 入队操作和出队操作的时间复杂度始终保持为 O(1)。

请回答：(1) 该队列应选链式存储还是顺序存储？(2) 画出初始状态，并给出队空、队满的条件；(3) 画出第一个元素入队后的状态；(4) 给出入队和出队操作的基本过程。总分 10 分。

这道题没有「尽可能高效」——因为它压根不比复杂度。四条要求本身就是答案的设计蓝图，你要做的是读懂它们，反推出结构。

关键在读懂两条硬约束

大多数队列题目直接给你数组或链表，这道题反过来：先给约束，让你选结构。四条要求里，真正卡死选型的是 ③ 和 ④：

• 要求 ④「入队/出队始终 O(1)」 里的「始终」两个字最关键。顺序存储（数组）用满时要扩容——申请新数组、拷贝旧元素、释放旧数组，这一次入队是 $O(n)$。虽然均摊下来是 $O(1)$，但题面要求的是每一次都 $O(1)$，不允许某一次突然变慢。这一条直接排除数组。
• 要求 ③「空间只增不减、可复用」 排除了普通链队列。普通链队列出队时 free 掉结点，下次入队再 malloc——这是「减了又增」，不符合「只增不减、复用」。

两条约束一夹，答案唯一：链式存储，而且是循环单链表 + 哨兵结点 + 空闲结点池。这就是设计题的解题方式：顺着约束去找那个能同时满足全部要求的结构。

结构设计与三个状态

存储选择（第 1 问）：循环单链表，配 front 和 rear 两个指针。理由就是上面两条：数组扩容违反「始终 O(1)」，普通链队列 free 结点违反「空间可复用」。这两条理由必须都说到，只说一条会丢分。

初始状态与队空/队满（第 2 问）：链表里只有一个哨兵结点（不存数据），front 和 rear 都指向它，哨兵的 next 指回自己形成自环。

• 队空条件：front == rear；
• 队满条件：rear->next == front（rear 的下一个就是 front，说明中间没有空闲结点可用了）。

这两个条件的位置不能反——写成 front->next == rear 是错的。

第一个元素入队后（第 3 问）：初始状态下 rear->next == front 恰好满足「队满」（只有哨兵、没有存数据的结点），所以要先 malloc 一个新结点插到 rear 与 front 之间，再把 rear 移过去、写入数据。此时 front 仍指哨兵，rear 指新结点，新结点 next 回指 front。

核心机制：front 之前到 rear 之间是「已用区」（存数据），rear 之后到 front 之间是「空闲区」（结点留着复用）。入队从空闲区借一个，出队把结点还回空闲区——空间只增不减，全靠这个「环 + 空闲池」。

入队与出队（第 4 问）

入队 enqueue(x)：

1. 检查 rear->next == front：若是（队满、无空闲结点），malloc 新结点 p 插入 rear 与 front 之间；若否，直接复用 rear 后面那个空闲结点；
2. rear = rear->next（rear 前进到待写入的结点）；
3. rear->data = x。

出队 dequeue()：

1. 检查 front == rear：若是（队空），报错返回；
2. front = front->next（front 前进一格，新位置就是原队头）；
3. 返回 front->data，但不 free 这个结点——让它留在环里，等 rear 转一圈回来复用。

那句「不 free」是这道题最高频的失分点。第一反应总是「出队就该释放内存」，但这里一 free 就违反了要求 ③「空间可复用」。设计题的细节分，往往就藏在这种「反直觉但题面要求如此」的地方。

队列的入队出队，看一遍

下面的交互演示可以走一遍入队、出队，直观感受队头队尾指针的移动和结点的循环复用：

加载可视化中...

常见错点清单

• 选了顺序存储：无论理由多漂亮，「始终 O(1)」这条已经把数组判出局。
• 漏掉哨兵设计 / 把 front、rear 初始化成 NULL：没有哨兵，空队列的边界处理会变得很别扭。
• 队满条件写成 rear->next == NULL：那是普通链表的思路，循环单链表里 next 永远不为 NULL。
• 出队 free 结点：直接违反要求 ③，是本题标志性错误。
• 入队漏判队满、直接复用：初始状态没有空闲结点，不先 malloc 会写到 front（哨兵）上出错。

这些错点没有一个和「算法效率」有关，全是设计是否自洽。这正是第二组设计题的特点：把结构想清楚、把边界画准，分就到手了。

下一步

• 回到题库看这道题的完整解析与状态图：真题库 · 数据结构
• 同属「数据结构设计题」的邻题：2020·42 前缀编码译码（用二叉树保存前缀码），专题后续更新
• 想练循环链表本身的指针操作，可看循环链表