游牧学院

2.3 栈的应用与实现
2.5 哈希表的原理与实现

基础数据结构 2.4 队列及其变种（循环队列、优先队列）

1. 队列概述

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。它的基本操作包括入队（enqueue）和出队（dequeue）。在队列中，元素的插入总是在队尾进行，而元素的删除总是在队头进行。队列广泛应用于计算机科学中，例如在任务调度、数据缓冲、广度优先搜索等场景中。

1.1 队列的基本操作

  • 入队（Enqueue）：将一个元素添加到队列的尾部。
  • 出队（Dequeue）：从队列的头部移除一个元素并返回该元素。
  • 查看队头元素（Front/Peek）：返回队头元素但不移除它。
  • 检查队列是否为空（IsEmpty）：判断队列是否为空。
  • 获取队列的大小（Size）：返回队列中元素的数量。

1.2 队列的实现

队列可以通过数组或链表来实现。下面分别展示这两种实现方式。

1.2.1 数组实现队列

class ArrayQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.front]
        self.queue[self.front] = None  # Optional: Clear the reference
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue[self.front]

    def get_size(self):
        return self.size

1.2.2 链表实现队列

class Node:
    def __init__(self, value):
        self.value = value
        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, item):
        new_node = Node(item)
        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 Exception("Queue is empty")
        item = self.front.value
        self.front = self.front.next
        if self.front is None:  # If the queue is now empty
            self.rear = None
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.front.value

    def get_size(self):
        return self.size

1.3 队列的优缺点

优点

  • 简单易用：队列的操作简单，易于理解和实现。
  • 高效：在大多数情况下，队列的入队和出队操作时间复杂度为 O(1)。

缺点

  • 固定大小：使用数组实现的队列在容量上是固定的，可能导致空间浪费或溢出。
  • 内存开销：链表实现的队列在每个节点上都有额外的内存开销。

2. 循环队列

循环队列（Circular Queue）是对线性队列的一种改进，解决了线性队列在出队后可能造成的空间浪费问题。循环队列通过将队列的尾部与头部连接起来，使得队列的使用更加高效。

2.1 循环队列的实现

循环队列的实现与线性队列类似，但在入队和出队时需要使用模运算来处理索引的循环。

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

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.front]
        self.queue[self.front] = None  # Optional: Clear the reference
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue[self.front]

    def get_size(self):
        return self.size

2.2 循环队列的优缺点

优点

  • 空间利用率高：循环队列有效利用了数组的空间，避免了线性队列中的空间浪费。
  • 操作简单：与线性队列相比，循环队列的操作逻辑相似，易于实现。

缺点

  • 固定大小：与线性队列一样，循环队列的大小在创建时固定，可能导致空间不足。
  • 复杂性增加：实现时需要处理索引的循环，增加了实现的复杂性。

3. 优先队列

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个优先级。出队时，优先级高的元素会优先被移除。优先队列通常使用堆（Heap）来实现。

3.1 优先队列的实现

优先队列可以使用最小堆或最大堆来实现。以下是一个使用最小堆实现的优先队列示例。

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def is_empty(self):
        return len(self.heap) == 0

    def enqueue(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return heapq.heappop(self.heap)[1]

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.heap[0][1]

    def get_size(self):
        return len(self.heap)

3.2 优先队列的优缺点

优点

  • 灵活性：优先队列允许根据优先级处理元素，适用于许多应用场景，如任务调度、图算法等。
  • 高效性：使用堆实现的优先队列，入队和出队操作的时间复杂度为 O(log n)。

缺点

  • 实现复杂：优先队列的实现相对复杂，尤其是在处理优先级时。
  • 内存开销：使用堆结构可能会导致额外的内存开销。

4. 总结

队列及其变种（循环队列、优先队列）是计算机科学中非常重要的数据结构。它们各自有不同的实现方式和应用场景。选择合适的队列实现方式可以提高程序的效率和可读性。在实际应用中，开发者需要根据具体需求来选择合适的队列类型，并注意其优缺点。希望本教程能帮助你更深入地理解队列及其变种。

2.3 栈的应用与实现
2.5 哈希表的原理与实现