数据结构：队列-平芜编程栈

数据结构：队列（Queue）
—— 后端开发中最常用、最容易被忽略的“先进先出”神器

队列是数据结构中最简单却又极其重要的线性结构之一，它的核心特性只有一句话：

先进先出（FIFO - First In First Out）

就像排队买奶茶：先来的先拿到，先排队的人先走。

1. 队列的核心操作（必须掌握的 5 个）

操作	英文名称	时间复杂度	说明
入队	enqueue / offer	O(1)	从队尾添加元素
出队	dequeue / poll	O(1)	从队首移除并返回元素
查看队首	peek / front	O(1)	只看队首元素，不移除
判断空	isEmpty	O(1)	判断队列是否为空
获取长度	size	O(1)	返回当前队列中的元素个数

注意：好的队列实现中，上面所有操作都应该是 O(1) 的。

2. 队列的几种常见实现方式对比（2025-2026面试最常问）

实现方式	底层结构	入队复杂度	出队复杂度	特点与适用场景	推荐指数
顺序队列（数组）	固定大小数组	O(1)	O(n)	简单，但出队效率低（需前移元素）	★★☆☆☆
循环队列（数组）	固定/动态数组+头尾指针	O(1)	O(1)	最高效，空间利用率高（最推荐）	★★★★★
链表队列	单向链表	O(1)	O(1)	空间动态扩展，无上限，内存不连续	★★★★☆
双端队列（Deque）	双向链表/数组	O(1)	O(1)	头尾都可进出（Java LinkedList/ArrayDeque）	★★★★☆
优先队列（PriorityQueue）	堆（二叉堆）	O(log n)	O(log n)	不是严格的FIFO，按优先级出队	★★★☆☆

结论：
日常开发中 90% 的队列需求，用循环队列（数组实现）或链表队列就够了。
性能要求极高或需要动态扩容 → 优先用循环队列（带动态扩容）。

3. 最经典的循环队列实现（Java版，面试常考）

publicclassCircularQueue{privateint[]data;privateintfront;// 指向队首元素privateintrear;// 指向队尾下一个空位privateintsize;// 当前元素个数privateintcapacity;publicCircularQueue(intk){capacity=k;data=newint[k];front=0;rear=0;size=0;}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;}data[rear]=value;rear=(rear+1)%capacity;size++;returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;}front=(front+1)%capacity;size--;returntrue;}publicintFront(){if(isEmpty())return-1;returndata[front];}publicintRear(){if(isEmpty())return-1;returndata[(rear-1+capacity)%capacity];}publicbooleanisEmpty(){returnsize==0;}publicbooleanisFull(){returnsize==capacity;}}

关键点记忆口诀：
“rear 永远指向下一个空位”
“满的判断：size == capacity”
“空的判断：size == 0”
“取尾元素：(rear-1 + capacity) % capacity”

4. 队列的经典应用场景（后端最常遇到）

场景	队列作用	典型技术选型
消息队列	异步解耦、削峰填谷	RabbitMQ / Kafka / Redis List
任务队列	定时任务、延时任务、异步处理	DelayQueue / Redis ZSET
BFS（广度优先搜索）	层序遍历、求最短路径	LinkedList 作为队列
滑动窗口最大值	维护窗口内最大值	双端队列（Deque）
生产者-消费者模型	线程间通信	BlockingQueue（ArrayBlockingQueue）
请求缓冲池	高并发场景限流、缓冲请求	LinkedBlockingQueue
打印机任务队列	先来先服务	顺序队列