7 线性数据结构之队列

在上一篇中，我们讨论了线性数据结构中的栈，了解了如何使用栈进行数据的存取操作。这一次，我们将探索另一种重要的线性数据结构——队列。队列在计算机科学中扮演着重要的角色，特别是在需要按照特定顺序处理数据的场景中。

什么是队列？

队列是一个先进先出（FIFO，First In First Out）的线性数据结构。在队列中，数据的插入和删除操作分别在不同的端口进行：数据从队列的一端（称为“队头”）删除，而从另一端（称为“队尾”）插入。这样，最先入队的数据将最先出队，形成一种顺序处理的机制。

队列的基本操作

队列的基本操作包括：

1. 入队（Enqueue）：插入一个新元素到队列的队尾。
2. 出队（Dequeue）：删除队列队头的元素，并返回该元素。
3. 查看队头（Peek/Front）：返回队头的元素，但不删除它。
4. 检查队列是否为空（IsEmpty）：判断队列是否还包含元素。

队列的实现

队列可以用数组或链表来实现。下面我们以数组为基础来介绍简单的队列实现。

数组实现队列

假设我们有一个数组来存储队列元素，同时使用两个指针 front 和 rear 来管理队头和队尾的位置。

class Queue:
    def __init__(self, capacity):
        self.capacity = capacity  # 队列的最大容量
        self.items = [None] * capacity  # 创建一个空队列
        self.front = 0  # 队头指针
        self.rear = -1  # 队尾指针
        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("队列已满")
        self.rear = (self.rear + 1) % self.capacity  # 环形队列处理
        self.items[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("队列为空")
        item = self.items[self.front]
        self.front = (self.front + 1) % self.capacity  # 环形队列处理
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("队列为空")
        return self.items[self.front]

示例应用

队列在许多场景中都有广泛应用。以下是一个具体的案例：一个简单的任务调度器。

假设我们有一个任务调度器，它需要处理一系列任务，每个任务按照它的到达顺序依次执行。我们可以使用队列来存储待处理的任务。

def task_scheduler(tasks):
    queue = Queue(len(tasks))
    for task in tasks:
        queue.enqueue(task)

    while not queue.is_empty():
        current_task = queue.dequeue()
        print(f"正在执行任务: {current_task}")

# 测试函数
tasks = ['任务1', '任务2', '任务3', '任务4']
task_scheduler(tasks)

在这个例子中，我们将任务依次加入队列，然后依次从队列中出队并执行，这样就确保了任务的顺序。

小结

队列是一种重要的线性数据结构，适合于需要遵循先进先出规则的场景。通过上述示例和代码实现，我们认识了队列的基本操作以及在实际应用中的价值。

在接下来的部分，我们将转向非线性数据结构的另一重要类别——树。我们将讨论树的基本概念以及不同类型的树如何组织和处理数据，继续深入探讨数据结构的世界。