队列

队列（Queue）是一种先进先出的线性表，一端进、另一端出。
和栈正好相反：栈是"后进先出"，队列是"先进先出"。

一、队列概念

1.1 什么是队列

队列：一种限定性的线性表——只能在一端（队尾）插入，另一端（队首）删除。

就像排队买票：新来的人排在队尾，先来的人在队首先被服务。

1.2 核心规则：先进先出（FIFO）

FIFO（First In First Out）：先进入的，先出去。

队尾（入队）          队首（出队）  
 ← 3 2 1 加入 1 2 3 →  
 后进的后出           先进的先出  

按 1 → 2 → 3 的顺序入队，出队顺序仍然是 1 → 2 → 3（和入队顺序一样）。

💡 口诀：队列是"先进先出"，先排队的先出去——和栈的"后进先出"正好相反。

1.3 名词介绍

1.4 应用场景

💡 一句话判断"该不该用队列"：如果处理顺序是"先进先出"（先来的先处理），就用队列。

二、数组模拟队列

2.1 结构：q[]、front、rear

用一个数组 q[] 存元素，两个变量 front、rear 标记队首和队尾。

const int N = 100005;  
int q[N];  
int front = 0, rear = 0;   // front 队首，rear 队尾的下一个空位  

入队 1、2、3 之后：  
 q[0]  q[1]  q[2]  q[3]  q[4]
┌───┬───┬───┬───┬───┐  
│ 1 │ 2 │ 3 │   │   │  
└───┴───┴───┴───┴───┘  
 ↑           
 ↑front = 0   rear = 3（指向队尾的下一个空位）  

约定：front 指向队首元素，rear 指向队尾的下一个空位。所以：

• 元素数量 = rear - front
• 空队列 = front == rear

2.2 基本操作

q[rear++] = x;    // 入队：放到队尾，rear 后移  
  
q[front];         // 队首元素  
  
front++;          // 出队：front 后移，原队首就被"跳过"了  
  
rear - front;     // 元素数量  
  
front == rear;    // 空队列  

💡 记住这几句：

• 入队 q[rear++] = x（放到队尾，rear 后移）
• 队首 q[front]
• 出队 front++
• 元素数量 rear - front
• 空队列 front == rear

2.3 假溢出问题

普通数组队列，入队、出队多次后，front 和 rear 都一直往后移，数组前面的空间浪费了：

入队 5 个、出队 2 个之后：  
 q[0]  q[1]  q[2]  q[3]  q[4]
┌───┬───┬───┬───┬───┐  
│   │   │ 3 │ 4 │ 5 │  
└───┴───┴───┴───┴───┘  
 ↑           ↑ 
 front=2    rear=5（到末尾了）  

⚠️ 虽然 q[0]、q[1] 空着，但 rear 已经到数组末尾，再入队就越界了——这叫假溢出。
解决：把数组首尾连起来，让 rear 到末尾后回到 0，就是循环队列。

三、循环队列

3.1 为什么需要循环队列

把数组首尾相接，rear 走到末尾后回到开头，空出的位置就能重新利用，避免假溢出。

把数组想象成一个环：  
  
 q[0]  q[1]  q[2]  q[3]  q[4] 
 ┌─────┬─────┬─────┬─────┬─────┐ 
 │     │  3  │  4  │  5  │     │ 
 └─────┴─────┴─────┴─────┴─────┘ 
 ↑               ↑ 
 rear 回到这 front  （再入队放 q[0]）  

3.2 模运算实现循环

用取模 % 让 front、rear 循环移动：

const int N = 100005;  
int q[N];  
int front = 0, rear = 0;  

// 入队  
q[rear] = x;  
rear = (rear + 1) % N;      // rear 到末尾后回到 0  
// 出队  
front = (front + 1) % N;    // front 到末尾后回到 0  

3.3 基本操作

q[rear] = x;                   // ① 入队：放进队尾  
rear = (rear + 1) % N;         // ② rear 后移（循环）  
  
q[front];                      // 队首元素  
  
front = (front + 1) % N;       // 出队：front 后移（循环）  
  
(rear - front + N) % N;        // 元素数量  
  
front == rear;                 // 空队列  

💡 核心就一句话：移动指针时用 (指针 + 1) % N，让它绕回来。

3.4 空队列和满队列的判断

循环队列里，front == rear 有两种情况（空、满），要区分：

💡 满队列用"牺牲一个位置"的方法：始终让队尾后面空一个位置，当 rear 再往后一格就撞上 front 时，说明满了。所以循环队列最多存 N - 1 个元素。

满队列（假设 N = 5，最多存 4 个）：  
 q[0]  q[1]  q[2]  q[3]  q[4]
┌───┬───┬───┬───┬───┐  
│   │ 2 │ 3 │ 4 │ 5 │  
└───┴───┴───┴───┴───┘  
 ↑               ↑
 rear=0         front=1  
此时 (rear+1) % 5 == 0 == front，满了  

另一种做法是用一个计数器 size 记录元素个数：size == 0 空，size == N 满，能存满 N 个，但多一个变量。