队列（Queue）

算法原理

队列是先进先出（FIFO, First In First Out）的线性结构：队尾（tail）入队（enqueue），队首（head）出队（dequeue）——和排队买票一样，先来的先走。把"栈"的开口从一端换成两端各司其职，公平性就出来了：元素的出场顺序与到场顺序完全一致。队列是广度优先搜索的引擎、"生产者-消费者"的缓冲带、操作系统任务调度的骨架。

本动画在容量 8 的环形队列（ring buffer）上演完整序列，一操作一拍：

enqueue 4 1 7 9 5 2 8 3   （8 次入队填满全列，tail 走到 8 后环回 0）
dequeue × 3               （出 4、出 1、出 7——先来的先走，head 逐格右移）

关键看点在环回：tail 走到末尾后下一拍回到下标 0 继续入队——环形存储让出队腾出的空间能被复用，数组实现的队列因此不搬元素、不开新数组。

动画怎么看

• 单行 8 格：队列本体，从左到右是下标 0–7 的环形存储摊平的样子；
• head / tail 圆徽章：队首读出位置、队尾写入位置，随操作逐格滑动；同槽并排时 head 左 tail 右错开（队空/队满都在此形态）；
• enqueue 拍：新卡在 tail 槽淡入，徽章右移一格；tail 到 8 环回 0 时状态行标 环回；
• dequeue 拍：head 槽的卡向下滑动淡出，徽章右移一格；
• 大✓：8 进 3 出，队长 5——剩下的 9 5 2 8 3 从 head=3 一路排到 tail=3（环回后在此会合），状态行 ✓ 完成 ｜ 队长 5 · 8 进 3 出。

复杂度分析

C++ 参考代码

#include <iostream>
using namespace std;

class Queue {
    int a[8];
    int head = 0, tail = 0, cnt = 0;   // cnt 区分队空/队满
public:
    bool empty() const { return cnt == 0; }
    bool full()  const { return cnt == 8; }
    void enqueue(int v) {
        if (full()) { cout << "队满\n"; return; }
        a[tail] = v;
        tail = (tail + 1) % 8;          // 环回：到末尾回 0
        cnt++;
    }
    int dequeue() {
        if (empty()) { cout << "队空\n"; return -1; }
        int v = a[head];
        head = (head + 1) % 8;
        cnt--;
        return v;
    }
};

int main() {
    Queue q;
    int plan[] = {4, 1, 7, 9, 5, 2, 8, 3};
    for (int v : plan) q.enqueue(v);    // 填满，tail 环回 0
    for (int i = 0; i < 3; i++)
        cout << q.dequeue() << endl;    // 4 1 7 —— 先来的先走
    return 0;
}

什么时候用队列

凡是"先到先服务"的公平语义，都是队列的主场：广度优先搜索（层层扩散靠它维持次序）、任务调度与消息队列（先提交先处理）、缓冲区（键盘输入、网络包、打印队列）。双端的需求（两头都能进出）升级为 deque；带优先级的调度（急诊插队）则换优先队列。实现上数组环形队列要盯紧判满判空与取模环回两件事——本动画 tail 走满 8 格回到 0 的那一拍，正是环形结构最值得看的一眼。