2025-4-2-链式队列

1. 什么是链式队列？

链式队列是用 链表（Linked List） 实现的队列，符合 先进先出（FIFO） 的规则。就像现实中的排队：

• 入队（Enqueue）：新人排到队尾。
• 出队（Dequeue）：队头的人先离开。

链式队列 vs 数组队列

| 对比项 | 链式队列 | 数组队列 | | ———— | ———————- | ————— | | 存储方式 | 动态分配（不连续内存） | 连续内存 | | 扩容 | 灵活（无容量限制） | 需手动扩容/缩容 | | 适用场景 | 频繁增删 | 随机访问 |

2. 链式队列的实现步骤

我们用py代码实现

先定义节点

1
2
3
4
5

class Node:
    def __init__(self):
        self.front = None
        self.rear = None
        

再定义队列

1
2
3
4
5
6
7
8

def enqueue(self,data):
    new_node = Node(data)
    if self.rear is None:
        self.front = self.rear = new_node
    else:
        self.rear.next = new_node
        self.rear = new_code
        

出队的实现

1
2
3
4
5
6
7
8

def dequeue(self):
    if self.front is None:
        return None
    temp = self.front
    self.front = temp.next
    if self.front is None:
        self.rear = None
    return temp.data

检查队头是不是空的

1
2

def is_empty(self):
    return self.front is None

4. 时间复杂度分析

| 操作 | 时间复杂度 | 说明 | | ———– | ———- | ——————— | | Enqueue | O(1) | 直接修改队尾指针 | | Dequeue | O(1) | 直接修改队头指针 | | IsEmpty | O(1) | 检查 front 是否为空 |

5. 常见问题

Q1: 链式队列会溢出吗？

不会！因为链表动态分配内存，除非系统内存耗尽。

Q2: 如何遍历链式队列？

从 front 开始，沿着 next 指针逐个访问：

1

current = queue.frontwhile current:    print(current.data)    current = current.next