### 链栈的 Python 实现 链栈是一种基于链表实现的栈数据结构，其操作遵循“先进后出”的原则。以下是链栈的具体实现方法： #### 定义节点类 为了构建链栈，首先需要定义一个节点类 `Node`，该类用于存储每个节点的数据以及指向下一个节点的引用。 ```python class Node: def __init__(self, data=None): self.data = data # 节点数据 self.next = None # 下一节点引用 ``` #### 创建链栈类 链栈的核心功能包括初始化、入栈、出栈、获取栈顶元素、判断栈是否为空等。以下是完整的链栈实现： ```python class LinkStack: def __init__(self): """ 初始化链栈 """ self.top_node = None # 栈顶指针初始为None def is_empty(self): """ 判断链栈是否为空 """ return self.top_node is None # 如果top_node为None，则栈为空 def push(self, item): """ 入栈操作 """ new_node = Node(item) # 新建节点 new_node.next = self.top_node # 将新节点next指向当前栈顶 self.top_node = new_node # 更新栈顶指针到新节点 def pop(self): """ 出栈操作 """ if self.is_empty(): raise Exception("Stack Underflow") # 若栈为空则抛出异常 popped_item = self.top_node.data # 获取栈顶元素 self.top_node = self.top_node.next # 移动栈顶指针至下一节点 return popped_item # 返回弹出的元素 def get_top(self): """ 获取栈顶元素 """ if self.is_empty(): raise Exception("Stack is empty") # 若栈为空则抛出异常 return self.top_node.data # 返回栈顶元素 def traverse(self): """ 遍历链栈 (仅用于调试目的) """ current = self.top_node elements = [] while current: elements.append(current.data) current = current.next return elements[::-1] # 反转列表以显示从栈底到栈顶的顺序 ``` #### 测试代码 以下是一个简单的测试案例，展示如何使用上述链栈类完成基本操作： ```python if __name__ == "__main__": stack = LinkStack() # 入栈操作 stack.push(10) stack.push(20) stack.push(30) # 打印链栈内容 print("链栈内容:", stack.traverse()) # 获取栈顶元素 print("栈顶元素:", stack.get_top()) # 出栈操作 print("出栈元素:", stack.pop()) print("出栈后的链栈内容:", stack.traverse()) # 检查栈是否为空 print("链栈是否为空:", stack.is_empty()) ``` --- ### 输出示例 运行以上代码后，可能得到如下输出： ``` 链栈内容: [30, 20, 10] 栈顶元素: 30 出栈元素: 30 出栈后的链栈内容: [20, 10] 链栈是否为空: False ``` --- ### 关键点说明 1. **节点设计** 使用单向链表中的节点即可满足需求，无需像双链表那样维护前后两个方向的指针[^2]。 2. **时间复杂度分析** - 入栈 (`push`) 和出栈 (`pop`) 的时间复杂度均为 \(O(1)\)，因为它们只涉及修改头结点及其相邻关系。 - 遍历整个链栈的时间复杂度为 \(O(n)\)[^1]。 3. **边界条件处理** 当尝试对空栈执行出栈或获取栈顶元素的操作时，应显式抛出异常以提示错误状态[^3]。 ---