跳到主要内容

队列

队列是计算机科学中一种基本的线性数据结构，它遵循先进先出 (FIFO) 的原则。就像现实世界中的队列（例如，人们在售票处排队）一样，第一个添加到队列中的元素将是第一个被移除的。

队列的特点​

  • FIFO 顺序： 元素按照它们被添加的顺序进行处理。第一个入队的元素是第一个出队的。
  • 线性结构： 元素以顺序方式排列。
  • 两个主要操作：
    • enqueue(item): 将一个元素添加到队列的尾部（末端）。
    • dequeue(): 移除并返回队列头部的元素（开始）。
  • 额外操作（可能因实现而异）：
    • peek(): 返回队列头部的元素，但不移除它。
    • isEmpty(): 检查队列是否为空。
    • isFull(): 检查队列是否已满（适用于固定大小的队列）。
  • 术语：
    • 队头 (Front/Head)： 队列中元素被移除的一端。
    • 队尾 (Rear/Tail)： 队列中元素被添加的一端。

常见操作​

操作描述时间复杂度
enqueue向队列尾部添加一个元素。如果队列已满（固定大小），可能会导致溢出。O(1)O(1)
dequeue移除并返回队列头部的元素。如果队列为空，可能会导致下溢。O(1)O(1)
peek返回队列头部的元素，但不移除它。O(1)O(1)
isEmpty检查队列是否没有元素。O(1)O(1)
isFull检查队列是否无法容纳更多元素（适用于固定大小的队列）。O(1)O(1)

队列的实现​

使用内置数据结构​

大多数高级编程语言都提供内置数据结构或库来实现队列。例如，在 Python 中，你可以使用 collections 模块中的 deque 类来实现高效的队列。

from collections import deque

# 初始化队列
queue = deque()

# 入队元素
queue.append(1)
queue.append(2)
queue.append(3)

# 出队一个元素
first_element = queue.popleft()

# 查看队头元素，但不移除它
front_element = queue[0]

# 检查队列是否为空
is_empty = len(queue) == 0

实现队列​

使用链表实现队列​

链表是实现队列的自然选择，尤其是在大小不固定的情况下。在这里，队列的 front 对应于链表的头部，而 rear 对应于尾部。

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class LinkedListQueue:
    """使用单链表实现的队列。"""

    def __init__(self):
        self._front = None  # 指向队头节点的引用
        self._rear = None   # 指向队尾节点的引用
        self._size = 0

    def is_empty(self):
        """检查队列是否为空。"""
        return self._size == 0

    def enqueue(self, val):
        """向队列尾部添加一个元素。"""
        new_node = ListNode(val)
        if self.is_empty():
            self._front = self._rear = new_node
        else:
            self._rear.next = new_node
            self._rear = new_node
        self._size += 1

    def dequeue(self):
        """移除并返回队列的队头元素。"""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        removed_value = self._front.val
        self._front = self._front.next
        self._size -= 1
        if self.is_empty():
            self._rear = None
        return removed_value

    def peek(self):
        """返回队头元素，但不移除它。"""
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self._front.val

    def size(self):
        """返回队列中的元素数量。"""
        return self._size

    def to_list(self):
        """将队列元素转换为列表。"""
        elements = []
        current = self._front
        while current:
            elements.append(current.val)
            current = current.next
        return elements

使用循环数组实现队列​

使用循环数组是实现固定大小队列的一种高效方法。其思想是将数组视为环绕，从而可以利用所有可用空间。

class ArrayQueue:
    """使用循环数组实现的队列。"""

    def __init__(self, capacity):
        self._array = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._size = 0

    def is_empty(self):
        """检查队列是否为空。"""
        return self._size == 0

    def is_full(self):
        """检查队列是否已满。"""
        return self._size == self._capacity

    def enqueue(self, val):
        """向队列尾部添加一个元素。"""
        if self.is_full():
            raise IndexError("Enqueue to full queue")
        rear = (self._front + self._size) % self._capacity
        self._array[rear] = val
        self._size += 1

    def dequeue(self):
        """移除并返回队列的队头元素。"""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        val = self._array[self._front]
        self._array[self._front] = None  # 可选：帮助垃圾回收
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return val

    def peek(self):
        """返回队头元素，但不移除它。"""
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self._array[self._front]

    def size(self):
        """返回队列中的元素数量。"""
        return self._size

    def to_list(self):
        """将队列元素转换为列表。"""
        elements = []
        for i in range(self._size):
            index = (self._front + i) % self._capacity
            elements.append(self._array[index])
        return elements

队列的应用​

队列广泛应用于各种计算场景，尤其是在需要保留顺序的情况下。

  1. 广度优先搜索 (BFS)： 用于图遍历算法，逐层探索节点。
  2. 资源调度：
    • CPU 调度： 在操作系统中管理进程和线程。
    • 磁盘调度： 排序磁盘 I/O 操作以优化性能。
  3. 异步数据处理：
    • IO 缓冲区： 设备之间传输数据的临时存储。
    • 打印假脱机 (Print Spooling)： 管理发送到打印机的打印作业。
  4. 任务管理系统：
    • Web 服务器中的作业队列： 处理 Web 应用程序中的传入请求。
    • 消息队列： 通过存储消息进行异步处理来解耦系统。
  5. 订单处理系统：
    • 电子商务平台（例如，亚马逊订单）： 订单按照收到的顺序处理。
  6. 现实世界队列的模拟：
    • 客户服务热线： 模拟和分析服务系统中的队列。
    • 呼叫中心： 按照收到的顺序管理来电。
  7. 待办事项列表和任务调度：
    • 操作系统中的任务队列： 管理等待执行的任务。
    • GUI 应用程序中的事件队列： 处理用户输入事件。

总结​

队列是基本的数据结构，它提供了一种按顺序处理数据、同时保留插入顺序的方式。理解队列、它们的实现和应用对于解决计算机科学和软件工程中的许多问题至关重要。

在实现队列时，根据需求选择正确的数据结构很重要：

  • 链表： 适用于元素频繁添加和移除的动态大小队列。
  • 循环数组： 对于固定大小的队列，开销最小且效率高，适用于已知最大容量的系统。

队列在进程调度、数据缓冲和实时系统等领域无处不在，使其成为一个必须掌握的关键概念。