如何使用链表实现一个队列？

推荐答案

// www.javascriptcn.com code example
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

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

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

    def enqueue(self, value):
        new_node = Node(value)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

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

    def peek(self):
        if self.is_empty():
            return None
        return self.front.value

本题详细解读

1. 链表节点定义

• Node 类用于表示链表中的节点。每个节点包含两个属性：
  • value：存储节点的值。
  • next：指向下一个节点的指针。

2. 队列类定义

• Queue 类用于实现队列。队列有两个指针：
  • front：指向队列的第一个元素。
  • rear：指向队列的最后一个元素。

3. 队列的基本操作

• is_empty()：检查队列是否为空。如果 front 为 None，则队列为空。
• enqueue(value)：将元素添加到队列的末尾。如果队列为空，则 front 和 rear 都指向新节点。否则，将新节点添加到 rear 的后面，并更新 rear。
• dequeue()：移除并返回队列的第一个元素。如果队列为空，返回 None。否则，将 front 指向下一个节点，并返回原 front 的值。如果 front 变为 None，则 rear 也设置为 None。
• peek()：返回队列的第一个元素但不移除它。如果队列为空，返回 None。

4. 时间复杂度分析

• enqueue(value)：O(1)，因为只需要在链表末尾添加一个节点。
• dequeue()：O(1)，因为只需要移除链表头部的节点。
• peek()：O(1)，因为只需要访问链表头部的节点。

5. 空间复杂度分析

• 空间复杂度为 O(n)，其中 n 是队列中元素的数量。每个元素都需要一个节点来存储。