队列(Queue)

定义

队列是一种遵循先进先出（FIFO，First In First Out）原则的线性数据结构。元素从队尾入队（enqueue），从队头出队（dequeue），类似排队买票。

工作方式

队列可用数组或链表实现。简单数组实现会因出队产生空洞而浪费空间，因此常用循环队列，用首尾两个指针在固定数组上回绕。还有双端队列（deque）允许两端增删，优先队列按优先级而非顺序出队（通常用堆实现）。

复杂度

• 入队 enqueue：O(1)
• 出队 dequeue：O(1)
• 查看队头：O(1)
• 空间复杂度：O(n)

应用场景

• 广度优先搜索的层次遍历
• 任务调度、消息队列、缓冲区
• 操作系统进程与 IO 请求排队
• 生产者消费者模型