队列与双端队列：先进先出

银行里的队伍

队列就是一条井然有序的队伍。新来的人从队尾加入；柜员从队首叫号。最先来的人最先离开——先进先出，即 FIFO。只要关乎公平或到达顺序，它就是自然的选择。

两个核心操作各有名字：enqueue（入队）从队尾加入，dequeue（出队）从队首移除。两者都是 O(1)——在一端加、在另一端删，从不需要移动任何人。

dequeue <- [ 1 | 2 | 3 ] <- enqueue
          front        back

enqueue 4:  [ 1 | 2 | 3 | 4 ]
dequeue  :  returns 1 ->  [ 2 | 3 | 4 ]

队尾加，队首删。两端相对——这正是 FIFO 的由来。

C++ 里的 std::queue

标准库提供 `std::queue`。它的术语和栈略有不同：在队尾 `push`（入队），用 `front()` 读队首，从队首 `pop()`。

#include <queue>
#include <iostream>

std::queue<int> q;
q.push(1);              // enqueue
q.push(2);
q.push(3);
std::cout << q.front(); // 1 (the FIRST one in)
q.pop();                // dequeue -> removes 1
std::cout << q.front(); // 2

std::queue：push 在队尾加，front() 读队首，pop() 移除队首。

环形缓冲区的思路

用普通数组实现队列会遇到个麻烦：如果每次从队首删除都把后面整体左移，那么每次出队都要 O(n)。聪明的办法是环形缓冲区——维护两个下标 `head` 和 `tail`，让它们到达固定数组末端后绕回开头。这样从不需要移动元素。

capacity 5, head=front, tail=next free slot:

  index:  0   1   2   3   4
        [ . | 2 | 3 | 4 | . ]
              ^head       ^tail

enqueue 5 -> tail goes to 4; enqueue 6 -> tail WRAPS to 0
        [ 6 | 2 | 3 | 4 | 5 ]
          ^tail ^head

(use tail = (tail + 1) % capacity to wrap)

环形缓冲区用取模让下标绕回，从而复用前端空出的格子。

关键技巧是取模：`index = (index + 1) % capacity` 让下标从最后一格跳回第 0 格。有了它，入队和出队都保持 O(1)，且没有任何元素被移动。

双端队列，以及队列的用武之地

deque（双端队列，读作 "deck"）允许你在两端都进行加和删——队首和队尾皆可。它是栈和队列的超集。在 C++ 里，`std::deque` 提供 `push_front`、`push_back`、`pop_front`、`pop_back`，全是 O(1)。

#include <deque>

std::deque<int> d;
d.push_back(2);    // [2]
d.push_front(1);   // [1, 2]
d.push_back(3);    // [1, 2, 3]
d.pop_front();     // [2, 3]   removed 1
d.pop_back();      // [2]      removed 3

std::deque：两端都能 O(1) 地伸缩。

为什么要在意它？任务队列按到达顺序处理作业。操作系统从一个队列里调度程序。而广度优先搜索——逐层探索图，你将在"树与图"那一阶见到它——完全建立在队列之上：你把邻居入队，再按发现顺序出队。队列正是"按到达顺序处理事情"的引擎。