Python顺序队列详解（从零开始掌握队列的实现与应用）

什么是顺序队列？

顺序队列是使用连续的内存空间（如数组或Python中的列表）来存储元素的队列。它有两个关键指针：

• 队头（front）：指向队列的第一个元素，用于出队操作。
• 队尾（rear）：指向队列最后一个元素的下一个位置，用于入队操作。

实现步骤

我们将使用Python类来封装队列的操作，包括初始化、入队、出队、查看队头、判断是否为空等。

1. 定义队列类

首先，我们创建一个名为 SequentialQueue 的类，并在初始化方法中设置最大容量、队列列表、队头和队尾指针。

class SequentialQueue:    def __init__(self, max_size=10):        self.max_size = max_size          # 队列最大容量        self.queue = [None] * max_size    # 初始化固定大小的列表        self.front = 0                    # 队头指针        self.rear = 0                     # 队尾指针

2. 判断队列是否为空或满

这两个辅助方法能帮助我们安全地进行入队和出队操作。

    def is_empty(self):        """判断队列是否为空"""        return self.front == self.rear    def is_full(self):        """判断队列是否已满（考虑循环队列情况）"""        return (self.rear + 1) % self.max_size == self.front

3. 入队操作（enqueue）

将元素添加到队尾，并更新队尾指针。

    def enqueue(self, item):        """入队操作"""        if self.is_full():            raise Exception("队列已满，无法入队！")        self.queue[self.rear] = item        self.rear = (self.rear + 1) % self.max_size  # 循环移动

4. 出队操作（dequeue）

移除并返回队头元素，同时更新队头指针。

    def dequeue(self):        """出队操作"""        if self.is_empty():            raise Exception("队列为空，无法出队！")        item = self.queue[self.front]        self.queue[self.front] = None  # 可选：清除引用        self.front = (self.front + 1) % self.max_size        return item

5. 查看队头元素与当前长度

    def peek(self):        """查看队头元素但不移除"""        if self.is_empty():            raise Exception("队列为空！")        return self.queue[self.front]    def size(self):        """返回当前队列中元素个数"""        return (self.rear - self.front + self.max_size) % self.max_size

完整代码示例

将上述所有方法整合，形成完整的Python顺序队列实现：

class SequentialQueue:    def __init__(self, max_size=10):        self.max_size = max_size        self.queue = [None] * max_size        self.front = 0        self.rear = 0    def is_empty(self):        return self.front == self.rear    def is_full(self):        return (self.rear + 1) % self.max_size == self.front    def enqueue(self, item):        if self.is_full():            raise Exception("队列已满，无法入队！")        self.queue[self.rear] = item        self.rear = (self.rear + 1) % self.max_size    def dequeue(self):        if self.is_empty():            raise Exception("队列为空，无法出队！")        item = self.queue[self.front]        self.queue[self.front] = None        self.front = (self.front + 1) % self.max_size        return item    def peek(self):        if self.is_empty():            raise Exception("队列为空！")        return self.queue[self.front]    def size(self):        return (self.rear - self.front + self.max_size) % self.max_size# 使用示例if __name__ == "__main__":    q = SequentialQueue(5)    q.enqueue("A")    q.enqueue("B")    q.enqueue("C")    print("队列大小：", q.size())      # 输出：3    print("队头元素：", q.peek())     # 输出：A    print("出队：", q.dequeue())       # 输出：A    print("出队：", q.dequeue())       # 输出：B

为什么使用循环队列？

在上面的实现中，我们使用了 % self.max_size 来实现循环队列。这是因为普通顺序队列在多次出队后，队头前面的空间会被浪费。通过循环利用数组空间，可以提高内存效率。

总结

通过本篇数据结构教程，你已经掌握了如何用Python实现一个功能完整的顺序队列。这种实现方式不仅有助于理解队列的工作原理，也为后续学习更复杂的Python编程入门内容打下坚实基础。记住，队列的核心是“先进先出”，而循环设计则能有效避免空间浪费。

关键词回顾：Python顺序队列、队列实现、数据结构教程、Python编程入门