先进先出

队列（queue）像排队买东西：新来的排到队尾，服务从队头开始。先来的先被服务，这条规矩叫先进先出（FIFO，First In First Out）。

它和栈正好相反：栈只在一头进出（后进先出），队列则一头进、另一头出。依次来 1、2、3，服务顺序就是 1、2、3，和进来顺序一致；换成栈则是 3、2、1。

// 手写队列的核心：两个指针
int q[100], head = 0, tail = 0;
q[tail++] = 1;      // 入队（排到队尾）
q[tail++] = 2;
int x = q[head++];  // 出队（从队头拿），x = 1

入队、出队都是 $O(1)$，判空是 head == tail。

队列是广度优先搜索（BFS）的核心容器：一圈圈往外扩、先进先处理，正好靠 FIFO 保证按层顺序。坑：手写队列 head 只往后走不回头，空间会一直消耗，数据量大时要用循环队列或直接用库里的 queue。