Allureluoli 二月FEBRUARY

2025-4-2-链式队列

2 min read 1.0k 字
#Python #数据结构

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

Q3: 链式队列 vs 循环队列？

  • 链式队列：无容量限制，但每次操作需动态分配内存。
  • 循环队列：固定容量，适合已知最大长度的场景（如操作系统任务调度）。

6. 实际应用场景

  1. 消息队列：RabbitMQ、Kafka 的底层实现之一。
  2. CPU 任务调度：操作系统中的就绪队列。
  3. 广度优先搜索（BFS）：图的遍历算法。

总结

  • 链式队列 = 链表 + 队头队尾指针。
  • 核心操作：enqueue（队尾插入）、dequeue（队头删除）。
  • 优点：动态扩容、无需处理固定容量问题。

本文作者 Allureluoli

文字版权归作者所有，转载请注明出处；商业用途请先联系二月。

CC BY-NC-ND 4.0 原文链接 ↗

评论COMMENTS