经典应用
广度优先搜索（BFS）
图的广度优先搜索使用队列来保存待访问的顶点，保证按照距离起点的层次顺序依次访问。
void BFS(Graph G, int v) {
InitQueue(Q);
visited[v] = true;
EnQueue(Q, v);
while (!QueueEmpty(Q)) {
DeQueue(Q, v);
visit(v); // 访问顶点v
for (每个邻接点w of v) {
if (!visited[w]) {
visited[w] = true;
EnQueue(Q, w);
}
}
}
}其他应用
- 缓冲区管理：如键盘输入缓冲区、打印机任务队列
- 操作系统任务调度：就绪队列、等待队列
- 网络数据包传输：路由器的数据包排队
- 层次遍历：二叉树的层序遍历
- 滑动窗口：用双端队列实现滑动窗口最大值问题
趣味事实
队列的生活类比：队列最形象的例子就是排队买奶茶。先来的人排在前面，先买到奶茶先走（先进先出）；后来的人排在队尾，等待前面的人都买完才能轮到自己。如果有人插队，就破坏了队列的”先进先出”原则——这在数据结构中就相当于使用了优先级队列，插队的人优先级更高。
银行叫号系统：银行的叫号系统就是一个典型的队列应用。顾客取号后进入等待队列，叫号时按照取号顺序依次叫号（先进先出）。但银行的VIP客户可以优先办理业务，这就引入了优先级队列的概念——VIP客户的优先级更高，可以插队到普通客户前面。