04、队列
排队买饭、等待处理的任务、按层访问的树节点，都有一个共同要求：先来的先处理。队列把这个规则变成一个受约束的接口：队尾加入，队首取出，先进先出（FIFO）。
队列限制了哪些操作
队列不是只能用数组实现，也不是“删除任意元素”的容器。它约定 push 在尾部加入、pop 从头部取出、front 查看当前最早的元素。
例如依次加入 10、20、30，第一次取出的一定是 10。队列元素的逻辑先后关系比物理地址是否连续更重要。
从普通数组队列想到循环队列
最直接的数组实现会在删除队头后移动其他元素，这次删除要 O(n)。也可以不移动元素，只推进队首下标；但如果队尾一直向右走，前面空出来的位置就可能无法复用。
循环队列把下标更新改成 (index + 1) % slot_count。走到数组最后一个位置后，下一次回到下标 0，物理上不连续的元素仍然可以构成逻辑连续的队列。
本文约定：front 指向第一个有效元素，rear 指向下一次写入的位置。预留一个槽位后：
- 空：
front == rear。 - 满：
(rear + 1) % slot_count == front。 - 有效容量为
slot_count - 1，不是数组槽位总数。
下标绕回，不需要移动元素
假设有四个槽位，最多存三个元素。当前 front = 3、rear = 1，下标 3 存 10、下标 0 存 20，逻辑顺序就是 10 → 20。
取出 10 后，front 从 3 绕回 0，rear 仍为 1。下标 3 从此不再属于有效队列。图中把它标成空位，只表示逻辑失效，不要求代码把原来的整数擦成 0。
这里的“预留一个槽位”是判满规则，不是永久禁止使用某个固定下标。另一种常见方案是额外维护元素计数，能够使用全部槽位；两种约定不要混用。
C++17 实现
#include <cstddef>
#include <limits>
#include <optional>
#include <stdexcept>
#include <vector>
class CircularQueue {
public:
explicit CircularQueue(std::size_t capacity) {
if (capacity == std::numeric_limits<std::size_t>::max()) {
throw std::length_error("queue capacity is too large");
}
data_.resize(capacity + 1);
}
bool empty() const { return front_ == rear_; }
bool full() const { return advance(rear_) == front_; }
bool push(int value) {
if (full()) return false;
data_[rear_] = value;
rear_ = advance(rear_);
return true;
}
std::optional<int> pop() {
if (empty()) return std::nullopt;
const int value = data_[front_];
front_ = advance(front_);
return value;
}
std::optional<int> front() const {
if (empty()) return std::nullopt;
return data_[front_];
}
private:
std::size_t advance(std::size_t index) const {
return (index + 1) % data_.size();
}
std::vector<int> data_;
std::size_t front_ = 0;
std::size_t rear_ = 0;
};
复杂度、选型与边界
构造预分配数组需要 O(C) 时间和空间；之后每次入队、出队和查看都是 O(1)，不包含扩容，因为本实现不会自动扩容。容量为 0 时始终不能入队，空队列通过 optional 表示“没有元素”，不把 -1 这种合法数据当作错误标记。
链表队列也能在保留头尾指针时做到入队、出队 O(1)，但有节点分配与指针空间成本。普通 C++ 业务代码通常优先使用 std::queue，需要两端操作时考虑 std::deque；本文实现用于理解循环下标与容量约定。
常见误区
不要在没有计数或额外标记的情况下，同时让 front == rear 表示空与满。也不要直接把单线程循环队列当作无锁并发队列：线程间的同步与可见性是另一个问题。