Queue

Jessica Gracewell2023-09-282023-10-12

Queue

队列是一种先入先出 (First In, First Out, FIFO) 的线性数据结构。在实际应用中，队列被广泛用于各种场景，比如 BFS (宽度优先搜索)、处理请求等。在这篇博客中，我们将探索队列的基本概念、操作和应用。

基本概念

以下是队列的常用操作及其时间复杂度：

push(): 元素入队，即将元素添加至队尾。
pop(): 队首元素出队。

peek(): 访问队首元素，但不移除。

在 Python 中，可以使用 collections.deque 作为队列。虽然 Python 还提供了一个 queue.Queue() 类，但它主要用于多线程编程，所以在这里我们使用 collections.deque。

队列基础和基于链表的实现

队列是一种遵循先入先出原则的数据结构，我们可以用链表来实现它。我们将链表的一端作为队首，另一端作为队尾。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点值
        self.next = next  # 指向下一个节点的指针

class LinkedListQueue:
    def __init__(self):
        self.front = None  # 队首指针
        self.rear = None  # 队尾指针
        self.size = 0  # 队列中的元素数量
    
    # 入队操作
    def push(self, x):
        node = ListNode(x)  # 创建新的节点
        if not self.rear:
            # 如果队列为空，队首和队尾都指向新的节点
            self.front = self.rear = node
        else:
            # 否则，将新节点加到队尾，然后更新队尾指针
            self.rear.next = node
            self.rear = node
        self.size += 1  # 更新队列大小
    
    # 出队操作
    def pop(self):
        if not self.front:
            return None  # 如果队列为空，返回 None
        val = self.front.val  # 获取队首元素的值
        self.front = self.front.next  # 更新队首指针
        if not self.front:
            self.rear = None  # 如果队列为空，重置队尾指针
        self.size -= 1  # 更新队列大小
        return val  # 返回队首元素的值
    
    # 获取队首元素
    def peek(self):
        return self.front.val if self.front else None  # 如果队列非空，返回队首元素的值
    
    # 判断队列是否为空
    def is_empty(self):
        return self.size == 0  # 如果队列大小为 0，返回 True

基于数组的实现

虽然链表是实现队列的一种方式，但我们也可以用数组来实现。使用数组时，需要处理数组的开始和结束位置，避免空间的浪费。

class ArrayQueue:
    def __init__(self, capacity):
        self.data = [None] * capacity  # 初始化固定大小的数组
        self.front = 0  # 队首索引
        self.size = 0  # 队列中的元素数量
    
    # 入队操作
    def push(self, x):
        if self.size == len(self.data):
            raise ValueError("Queue is full")  # 如果队列已满，抛出异常
        # 计算队尾索引并将元素添加到队尾
        rear = (self.front + self.size) % len(self.data)
        self.data[rear] = x
        self.size += 1  # 更新队列大小
    
    # 出队操作
    def pop(self):
        if self.size == 0:
            raise ValueError("Queue is empty")  # 如果队列为空，抛出异常
        val = self.data[self.front]  # 获取队首元素的值
        self.data[self.front] = None  # 清空队首元素
        self.front = (self.front + 1) % len(self.data)  # 更新队首索引
        self.size -= 1  # 更新队列大小
        return val  # 返回队首元素的值
    
    # 获取队首元素
    def peek(self):
        if self.size == 0:
            raise ValueError("Queue is empty")  # 如果队列为空，抛出异常
        return self.data[self.front]  # 返回队首元素的值
    
    # 判断队列是否为空
    def is_empty(self):
        return self.size == 0  # 如果队列大小为 0，返回 True

使用栈实现队列

由于栈是一种后入先出 (Last In, First Out, LIFO) 的数据结构，我们可以使用两个栈来模拟队列的行为。一个栈用于入队，另一个栈用于出队。

class MyQueue:
    def __init__(self):
        self.in_stack = []  # 输入栈，用于入队操作
        self.out_stack = []  # 输出栈，用于出队操作
    
    # 入队操作
    def push(self, x):
        self.in_stack.append(x)  # 元素入输入栈
    
    # 出队操作
    def pop(self):
        self._move()
        return self.out_stack.pop()  # 元素从输出栈出栈
    
    # 获取队首元素
    def peek(self):
        self._move()
        return self.out_stack[-1]  # 查看输出栈的栈顶元素
    
    # 将输入栈的元素移动到输出栈
    def _move(self):
        if not self.out_stack:  # 如果输出栈为空
            while self.in_stack:  # 当输入栈不为空时
                self.out_stack.append(self.in_stack.pop())  # 输入栈的元素出栈并入输出栈
    
    # 判断队列是否为空
    def is_empty(self):
        return not self.in_stack and not self.out_stack  # 如果两个栈都为空，返回 True

队列的应用 - BFS 和层次遍历

在 BFS（宽度优先搜索）中，队列用于按层次顺序遍历图或树的节点。当访问一个节点时，将其邻居节点添加到队列的尾部。之后，我们从队列的头部移除并处理节点。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # 节点的值
        self.left = left  # 左子节点
        self.right = right  # 右子节点

def level_order(root):
    if not root:
        return []  # 如果根节点为空，返回空列表
    result = []
    queue = [root]  # 初始化队列，根节点入队
    while queue:  # 当队列不为空时
        level = []
        for i in range(len(queue)):
            node = queue.pop(0)  # 队首节点出队
            level.append(node.val)  # 将队首节点的值添加到当前层的列表中
            if node.left:
                queue.append(node.left)  # 左子节点入队
            if node.right:
                queue.append(node.right)  # 右子节点入队
        result.append(level)  # 将当前层的列表添加到结果中
    return result  # 返回层次遍历的结果

队列在矩阵中的应用

在一个由 0 和 1 组成的矩阵中，我们可以使用 BFS 来计算每个元素到最近的 0 的距离。我们从每个 0 的位置开始，以层次遍历的方式，计算每个元素到 0 的最短距离。

def update_matrix(matrix):
    rows, cols = len(matrix), len(matrix[0])  # 获取矩阵的行数和列数
    queue = []  # 初始化队列
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 定义四个方向
    
    # 找到所有的 0，并将它们入队
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                queue.append((i, j))
            else:
                matrix[i][j] = float('inf')  # 初始化所有的 1 为无穷大
    
    # BFS
    while queue:
        i, j = queue.pop(0)  # 队首元素出队
        for dx, dy in directions:
            ni, nj = i + dx, j + dy  # 计算邻居节点的位置
            if 0 <= ni < rows and 0 <= nj < cols and matrix[ni][nj] > matrix[i][j] + 1:
                # 如果邻居节点在矩阵范围内且距离可以被优化，则更新距离并将邻居节点入队
                matrix[ni][nj] = matrix[i][j] + 1
                queue.append((ni, nj))
    
    return matrix  # 返回更新后的矩阵