什么是队列？

队列是一种先进先出（FIFO）的线性数据结构，更先进入的元素更先被移除。可以把它想象成超市收银台前的队伍：先到的人先结账，后来的人排在队尾。

队列的核心特征

• 队头（Front）： 只允许删除元素的一端。
• 队尾（Rear）： 只允许插入元素的一端。
• 入队（Enqueue）： 把新元素放到队尾。
• 出队（Dequeue）： 把队头元素移除并返回。

队列有哪些常见实现方式？

1. 顺序队列（数组实现）

用一段连续内存存储元素，维护两个指针 front 与 rear。缺点是可能出现“假溢出”，需要循环队列解决。

2. 链式队列（链表实现）

通过指针链接节点，动态扩容，无容量上限，但每个节点需额外空间存储指针。

3. 循环队列

把数组视为首尾相接的环，利用取模运算高效利用空间，避免假溢出。

队列有哪些应用场景？

1. 操作系统任务调度

CPU 采用时间片轮转策略时，将就绪进程排成队列，依次分配时间片。

2. 消息队列（MQ）

Kafka、RabbitMQ 等中间件用队列削峰填谷，解耦生产者和消费者，提高系统吞吐量。

3. 打印任务管理

打印机缓冲区就是队列，先到先打印，避免任务丢失。

4. 广度优先搜索（BFS）

在图或树中，BFS 用队列逐层扩展节点，保证最短路径优先。

5. 异步日志收集

日志系统把日志事件入队，后台线程批量刷盘，降低 I/O 阻塞。

队列与栈有什么区别？

如何实现一个线程安全的队列？

多线程环境下，普通队列会出现竞态条件。常用方案：

1. 加锁： 使用互斥锁保护入队、出队操作，简单但可能阻塞。
2. 无锁队列： 基于 CAS（Compare-And-Swap）原子指令，避免锁开销，如 Disruptor。
3. 分段锁： 把队列拆成多段，每段独立加锁，提高并发度，如 Java ConcurrentLinkedQueue。

队列的复杂度分析

• 顺序队列： 入队、出队平均 O(1)，扩容时最坏 O(n)。
• 链式队列： 入队、出队均 O(1)，额外空间 O(n) 存储指针。
• 循环队列： 所有操作 O(1)，空间利用率接近 100%。

实战：用 Python 写一个循环队列

class CircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.max_size = k
        self.front = 0
        self.rear = 0
        self.size = 0

    def enqueue(self, value):
        if self.size == self.max_size:
            raise OverflowError("Queue full")
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.max_size
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("Queue empty")
        val = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.max_size
        self.size -= 1
        return val

常见面试问题快问快答

Q：为什么循环队列要浪费一个存储单元？
A：为了区分空与满，当 (rear+1)%capacity==front 时判满，避免与空队列条件 rear==front 冲突。

Q：优先队列是队列吗？
A：不是严格意义上的 FIFO 队列，它按优先级出队，底层通常用堆实现。

Q：队列能用来实现栈吗？
A：可以，用两个队列来回倒腾，入栈 O(n)、出栈 O(1)，或用单个队列配合循环移位。

队列在微服务中的更佳实践

在分布式系统里，消息队列常作为事件总线：

• 使用死信队列处理消费失败的消息，避免数据丢失。
• 开启幂等生产与消费，防止重复消息导致业务错误。
• 设置合理的 TTL，让过期消息自动进入死信队列，减轻存储压力。

未来趋势：持久化队列与流式队列

传统内存队列断电即失，新一代持久化队列如 Kafka 把消息顺序写入磁盘，支持TB 级数据回溯。流式队列（Pulsar）更进一步，提供多租户隔离与分层存储，让队列兼具消息系统与实时数据湖的能力。