队列
知识总结
队列的定义
队列（Queue）是一种先进先出（FIFO, First In First Out）的线性数据结构。
从队尾插入，从队头删除。
基本操作
| 操作 | 说明 | 时间复杂度 |
|---|---|---|
push(x) | 入队 | O(1) |
pop() | 出队 | O(1) |
front() | 查看队头 | O(1) |
back() | 查看队尾 | O(1) |
empty() | 是否为空 | O(1) |
C++ STL 队列
1#include <queue>
2queue<int> q;
3q.push(1);
4q.push(2);
5q.push(3);
6cout << q.front(); // 1
7q.pop();
8cout << q.front(); // 2队列的变种
- 双端队列（deque）：两端都可以插入和删除
- 优先队列（priority_queue）：按优先级出队，本质是堆
- 循环队列：用数组实现，首尾相连避免假溢出
队列的应用
- BFS（广度优先搜索）：核心数据结构
- 任务调度：先来先服务
- 缓冲区：打印队列等