🧮 队列 (Queue)

难度 / Difficulty: 简单 (Easy)
分类 / Category: 数据结构 (Data Structure)
操作复杂度 / Operations: 全部 O(1)
空间复杂度 / Space Complexity: O(n)

📖 算法简介 / Introduction

队列是一种先进先出（First In First Out, FIFO）的数据结构。就像排队买东西，先来的人先服务。

A queue is a First In First Out (FIFO) data structure. Like a line at a store — people who arrive first are served first.

核心操作：Enqueue（入队） 和 Dequeue（出队）

💡 算法原理 / Principle

核心特性

• FIFO：最先进入队列的元素最先出来
• 一端进，另一端出：队尾入队，队头出队
• 操作受限：不支持随机访问中间元素

基本操作

📝 代码实现 / Implementation

基础队列

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()
    
    def enqueue(self, x):
        self.queue.append(x)
    
    def dequeue(self):
        if self.queue:
            return self.queue.popleft()
        return None
    
    def front(self):
        if self.queue:
            return self.queue[0]
        return None
    
    def empty(self):
        return len(self.queue) == 0
    
    def size(self):
        return len(self.queue)

✨ 示例 / Example

操作序列：
enqueue(1)  →  [1]
enqueue(2)  →  [1, 2]
enqueue(3)  →  [1, 2, 3]
dequeue()   →  返回 1，队列变为 [2, 3]
dequeue()   →  返回 2，队列变为 [3]
front()     →  返回 3，队列仍为 [3]

🎯 适用场景 / Scenarios

• 任务调度 — 操作系统任务队列、打印队列
• 层次遍历（BFS） — 用队列实现广度优先搜索
• 消息队列 — 异步通信、任务解耦
• 资源池 — 连接池、线程池管理
• 流量控制 — 限流、缓冲

Task scheduling (OS, printers), BFS implementation, Message queues (async communication), Resource pools (connection pools), Traffic control (rate limiting).

🔄 与栈对比 / Comparison with Stack

🔄 优先队列 / Priority Queue

普通队列按 FIFO 顺序出队，优先队列按优先级出队，优先级最高的先出队。

实现方式：通常用堆（Heap）实现，O(log n) 入队和出队。

import heapq

pq = []
heapq.heappush(pq, (priority, item))
heapq.heappop(pq)  # 优先级最高的先出