如何使用链表实现一个栈？

推荐答案

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            raise IndexError("pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        return value

    def peek(self):
        if self.top is None:
            raise IndexError("peek from empty stack")
        return self.top.value

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

本题详细解读

1. 链表节点的定义

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

2. 栈的实现

• Stack 类用于实现栈数据结构。栈是一种后进先出（LIFO）的数据结构，支持以下操作：
  • push(value)：将元素压入栈顶。
  • pop()：移除并返回栈顶元素。
  • peek()：返回栈顶元素但不移除它。
  • is_empty()：检查栈是否为空。

3. push 方法

• push 方法用于将元素压入栈顶。具体步骤如下：
  1. 创建一个新的 Node 对象，并将 value 赋值给它的 value 属性。
  2. 将新节点的 next 指针指向当前的栈顶节点。
  3. 将栈顶指针 top 更新为新节点。

4. pop 方法

• pop 方法用于移除并返回栈顶元素。具体步骤如下：
  1. 检查栈是否为空。如果为空，抛出 IndexError 异常。
  2. 获取栈顶节点的 value。
  3. 将栈顶指针 top 更新为下一个节点。
  4. 返回栈顶节点的 value。

5. peek 方法

• peek 方法用于返回栈顶元素但不移除它。具体步骤如下：
  1. 检查栈是否为空。如果为空，抛出 IndexError 异常。
  2. 返回栈顶节点的 value。

6. is_empty 方法

• is_empty 方法用于检查栈是否为空。如果栈顶指针 top 为 None，则栈为空，返回 True；否则返回 False。

7. 复杂度分析

• push、pop 和 peek 操作的时间复杂度均为 O(1)，因为它们只涉及对栈顶节点的操作。
• 空间复杂度为 O(n)，其中 n 是栈中元素的数量。