python中的队列

在 Python 中，队列（Queue）是一种常见的数据结构，特别是在刷算法题时经常被用到。以下是队列相关的基础语法及其在算法题中的应用总结。

1. 队列的基本定义

队列遵循 FIFO（先进先出） 原则，可以通过以下方式实现：

1) collections.deque

deque 是双端队列，支持快速的两端插入和删除操作。

from collections import deque

# 初始化队列
queue = deque()

# 入队
queue.append(1)  # 队尾插入
queue.append(2)

# 出队
x = queue.popleft()  # 队首弹出

# 检查队列是否为空
if not queue:
    print("Queue is empty")

2) queue.Queue

标准库中的线程安全队列，适合多线程场景。

from queue import Queue

# 初始化队列
queue = Queue()

# 入队
queue.put(1)
queue.put(2)

# 出队
x = queue.get()

# 检查队列是否为空
if queue.empty():
    print("Queue is empty")

2. 队列常见操作

1) 初始化队列

从列表初始化队列：

data = [1, 2, 3, 4]
queue = deque(data)

2) 队列长度

获取队列长度：

length = len(queue)

3) 清空队列

清空队列内容：

queue.clear()

4) 双端操作

deque 支持双端队列操作：

# 队首插入
queue.appendleft(0)

# 队尾弹出
x = queue.pop()

3. 算法题中队列的常用场景

1) 广度优先搜索（BFS）

队列是实现 BFS 的核心数据结构，常用于图遍历、最短路径等问题。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)  # 访问节点

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

2) 滑动窗口问题

在滑动窗口中，队列常用来维护窗口中的元素或其索引。

from collections import deque

def max_sliding_window(nums, k):
    deque_window = deque()
    result = []

    for i, num in enumerate(nums):
        # 移除窗口外的元素
        if deque_window and deque_window[0] == i - k:
            deque_window.popleft()

        # 保持队列单调递减，移除比当前元素小的
        while deque_window and nums[deque_window[-1]] < num:
            deque_window.pop()

        deque_window.append(i)

        # 记录窗口的最大值
        if i >= k - 1:
            result.append(nums[deque_window[0]])

    return result

3) 拓扑排序

利用队列维护入度为 0 的节点，用于有向图的拓扑排序。

from collections import deque

def topological_sort(graph, indegree):
    queue = deque([node for node in graph if indegree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else []

4) 多源 BFS

处理多个起点同时进行的 BFS 问题，比如火焰蔓延、病毒扩散等问题。

from collections import deque

def multi_source_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque()

    # 将所有起点加入队列
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:  # 起点条件
                queue.append((r, c))

    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:
                grid[nx][ny] = grid[x][y] + 1
                queue.append((nx, ny))

4. 优先队列

在需要按照优先级弹出元素的场景中，可以使用 heapq 实现最小堆（优先队列）。

import heapq

def process_priority_queue(data):
    pq = []
    for item in data:
        heapq.heappush(pq, item)  # 入堆

    while pq:
        print(heapq.heappop(pq))  # 出堆

若需要最大堆，可以将元素取反：

pq = []
heapq.heappush(pq, -1 * value)  # 插入负值
max_val = -1 * heapq.heappop(pq)  # 弹出负值并取反

5. 队列技巧总结

1. 广度优先搜索（BFS）：核心应用场景，用于图论、最短路径、层序遍历等。
2. 双端队列：滑动窗口、单调队列等问题的利器，支持高效的两端操作。
3. 优先队列：解决需要动态维护最大值或最小值的场景，如 Huffman 编码、Dijkstra 算法等。
4. 队列与递归结合：部分问题可以用队列替代递归，避免栈溢出。
5. 灵活初始化：从数组、起点集合快速构建队列，加速算法实现。

通过这些队列操作，刷算法题中涉及队列的数据结构问题会更加顺畅！