深入理解链式栈（Python链式栈实现详解：从零开始构建栈的链式存储结构）

什么是链式栈？

链式栈是使用链表作为底层存储结构的栈。与顺序栈不同，链式栈不需要预先分配固定大小的内存空间，它可以动态地申请和释放内存，因此更加灵活。

在链式栈中，我们通常将链表的头部作为栈顶（top），这样插入（push）和删除（pop）操作的时间复杂度都是 O(1)，效率非常高。

实现步骤

我们将分三步实现一个完整的链式栈：

1. 定义链表节点（Node）类
2. 定义链式栈（LinkedStack）类
3. 实现核心方法：push、pop、peek、is_empty、size

第1步：定义节点类

每个节点包含两个部分：数据（data）和指向下一个节点的指针（next）。

class Node:    def __init__(self, data):        self.data = data      # 存储数据        self.next = None      # 指向下一个节点

第2步：定义链式栈类

初始化时，栈顶（top）为 None，表示空栈。

class LinkedStack:    def __init__(self):        self.top = None   # 栈顶指针，初始为空        self._size = 0    # 记录栈中元素个数

第3步：实现核心方法

下面我们逐一实现栈的基本操作：

• push(item)：入栈，将新元素添加到栈顶
• pop()：出栈，移除并返回栈顶元素
• peek()：查看栈顶元素但不移除
• is_empty()：判断栈是否为空
• size()：返回栈中元素个数

完整代码如下：

class Node:    def __init__(self, data):        self.data = data        self.next = Noneclass LinkedStack:    def __init__(self):        self.top = None        self._size = 0    def push(self, item):        """入栈操作"""        new_node = Node(item)        new_node.next = self.top   # 新节点指向当前栈顶        self.top = new_node        # 更新栈顶为新节点        self._size += 1    def pop(self):        """出栈操作"""        if self.is_empty():            raise IndexError("栈为空，无法执行 pop 操作")        data = self.top.data        self.top = self.top.next   # 栈顶下移        self._size -= 1        return data    def peek(self):        """查看栈顶元素"""        if self.is_empty():            raise IndexError("栈为空")        return self.top.data    def is_empty(self):        """判断栈是否为空"""        return self.top is None    def size(self):        """返回栈的大小"""        return self._size    def __str__(self):        """方便打印栈内容（从栈顶到栈底）"""        result = []        current = self.top        while current:            result.append(str(current.data))            current = current.next        return " -> ".join(result) if result else "(空栈)"

测试你的链式栈

现在，让我们写一段测试代码，验证我们的Python链式栈是否正常工作：

# 创建栈实例stack = LinkedStack()# 入栈stack.push(10)stack.push(20)stack.push(30)print("当前栈内容:", stack)          # 输出: 30 -> 20 -> 10print("栈大小:", stack.size())       # 输出: 3print("栈顶元素:", stack.peek())     # 输出: 30# 出栈print("出栈元素:", stack.pop())      # 输出: 30print("出栈后栈内容:", stack)        # 输出: 20 -> 10# 判断是否为空print("栈是否为空:", stack.is_empty())  # 输出: False

为什么选择链式栈？

相比顺序栈（基于列表），链式栈实现有以下优势：

• 内存动态分配，无需预设容量
• 避免了顺序栈扩容时的性能开销
• 插入和删除操作始终为 O(1) 时间复杂度

当然，它也有缺点，比如每个节点需要额外的空间存储指针，且不能像数组那样随机访问元素。但在大多数应用场景中，链式栈是非常实用的选择。

总结

通过本教程，你已经掌握了如何用 Python 实现一个完整的链式栈。这不仅加深了你对栈的链式存储的理解，也为后续学习更复杂的数据结构（如队列、树等）打下了坚实基础。

记住：动手实践是最好的学习方式！试着修改代码，添加清空栈（clear）或遍历栈的方法，进一步巩固所学知识。

关键词回顾：Python链式栈、链式栈实现、Python数据结构、栈的链式存储。