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

一、什么是链式队列？

链式队列是基于单向链表构建的队列。它包含两个关键指针：

• front：指向队列的第一个元素（出队端）
• rear：指向队列的最后一个元素（入队端）

每次入队操作都在 rear 端添加新节点，出队操作则从 front 端移除节点。这种设计使得插入和删除的时间复杂度均为 O(1)。

二、实现步骤

我们将分三步实现链式队列：

1. 定义节点类（Node）
2. 定义链式队列类（LinkedQueue）
3. 实现核心方法：入队（enqueue）、出队（dequeue）、判空（is_empty）等

三、完整代码实现

下面是一个完整的 Python链式队列 实现：

class Node:    def __init__(self, data):        self.data = data        self.next = Noneclass LinkedQueue:    def __init__(self):        # 初始化时 front 和 rear 都为 None        self.front = None        self.rear = None    def enqueue(self, data):        # 入队：在 rear 端添加新节点        new_node = Node(data)        if self.rear is None:            # 如果队列为空，front 和 rear 都指向新节点            self.front = self.rear = new_node        else:            self.rear.next = new_node            self.rear = new_node    def dequeue(self):        # 出队：从 front 端移除节点        if self.is_empty():            raise IndexError("队列为空，无法出队！")                temp = self.front        self.front = temp.next                if self.front is None:            # 如果出队后队列变空，更新 rear            self.rear = None                return temp.data    def is_empty(self):        return self.front is None    def peek(self):        # 查看队首元素但不移除        if self.is_empty():            raise IndexError("队列为空！")        return self.front.data    def display(self):        # 打印整个队列（用于调试）        current = self.front        elements = []        while current:            elements.append(str(current.data))            current = current.next        print(" <-> ".join(elements) if elements else "队列为空")  

四、使用示例

现在我们来测试一下这个 链式队列实现 是否正常工作：

# 创建队列实例q = LinkedQueue()# 入队操作q.enqueue(10)q.enqueue(20)q.enqueue(30)# 显示当前队列q.display()  # 输出: 10 <-> 20 <-> 30# 查看队首元素print("队首元素:", q.peek())  # 输出: 队首元素: 10# 出队操作print("出队元素:", q.dequeue())  # 输出: 出队元素: 10q.display()  # 输出: 20 <-> 30# 判断是否为空print("队列是否为空:", q.is_empty())  # 输出: 队列是否为空: False  

五、为什么选择链式队列？

相比数组实现的顺序队列，Python数据结构中的链式队列有以下优势：

• 动态内存分配，无需预先指定大小
• 入队/出队操作效率高（O(1)）
• 不会出现“假溢出”问题

六、总结

通过本教程，你已经掌握了如何用 Python 实现一个功能完整的链式队列。无论是学习队列操作教程，还是深入理解Python链式队列的工作原理，这个实现都为你打下了坚实基础。建议你动手敲一遍代码，并尝试添加更多功能（如获取队列长度、清空队列等），以加深理解。

掌握数据结构是成为优秀程序员的关键一步，继续加油！