如何使用数组实现一个队列？

推荐答案

// www.javascriptcn.com code example
class Queue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [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("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.front]
        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]

本题详细解读

1. 队列的基本概念

队列是一种先进先出（FIFO）的数据结构，类似于现实生活中的排队。队列有两个主要操作：

• 入队（Enqueue）：将元素添加到队列的末尾。
• 出队（Dequeue）：移除队列的第一个元素。

2. 使用数组实现队列的挑战

数组是一种线性数据结构，具有固定的大小。使用数组实现队列时，主要挑战是如何高效地管理队列的头部和尾部，以避免频繁地移动元素。

3. 实现细节

• 初始化：在初始化时，我们创建一个固定大小的数组，并初始化front、rear和size变量。front指向队列的第一个元素，rear指向队列的最后一个元素，size表示队列中当前元素的数量。

• 入队操作：当向队列中添加元素时，我们首先检查队列是否已满。如果队列未满，则将rear指针移动到下一个位置（使用模运算实现循环），并将元素放入该位置。最后，增加size。

• 出队操作：当从队列中移除元素时，我们首先检查队列是否为空。如果队列不为空，则返回front指针指向的元素，并将front指针移动到下一个位置（同样使用模运算实现循环）。最后，减少size。

• 查看队首元素：peek操作返回front指针指向的元素，但不移除它。

4. 循环数组的优势

使用循环数组可以避免在出队操作时频繁移动元素，从而提高效率。通过模运算，front和rear指针可以在数组的末尾和开头之间循环移动，充分利用数组的空间。

5. 边界条件处理

• 队列满：当size等于capacity时，队列已满，无法再添加元素。
• 队列空：当size等于0时，队列为空，无法移除元素。

通过这些操作和边界条件的处理，我们可以使用数组高效地实现一个队列。