GESP 六级 · GESP 202506 C++ 六级 第 18 题

为了实现一个队列，使其出队操作（pop）的时间复杂度为 $O(1)$ 并且避免数组删除首元素的 $O(n)$ 问题，一种常见且有效的方法是使用环形数组，通过调整队首和队尾指针来实现。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】队列实现｜环形数组｜时间复杂度 O(1)

环形数组的核心是模运算：队首指针 front 右移时，新位置为 (front + 1) % 数组长度。这样队首元素被逻辑跳过，无需移动后续元素，pop 操作直接 O(1)。队列满时 rear 不追上 front，需预留空位或判满条件，但 pop 本身不受影响。

错误选项往往混淆"逻辑删除"与"物理移动"。命题人利用考生对"删除"二字的惯性认知：看到 pop 就想到"移除元素"，下意识判断需要移动后续元素 → 误判为 O(n)。其实环形数组中 front 指针右移（模运算）即完成逻辑删除，元素本身留在原地，时间复杂度恒为 O(1)。

命题人若改问"入队操作时间复杂度"，答案仍为 O(1)（rear 指针右移即可）；若换用链表实现队列，pop 同样 O(1) 但空间开销 O(n)。这题本质考的是"环形数组是否解决了前端删除的线性移动问题"，而非队列抽象本身。