### 使用链表实现链栈 链栈是一种基于链表的数据结构，它遵循后进先出（LIFO）的原则。相比于数组实现的栈，链表实现的栈具有动态扩展的优势，不会受到固定容量的限制。 以下是通过 Python 中的链表来实现链栈的具体方法： #### 1. 节点定义 为了构建链栈，首先需要定义一个 `Node` 类表示链表中的节点。每个节点包含两个部分：一个是存储数据的字段 `data`，另一个是指向下一个节点的指针 `next`。 ```python class Node(object): def __init__(self, data=None): self.data = data self.next = None ``` #### 2. 链栈类定义 接下来定义一个 `LinkedStack` 类用于管理链表形式的栈操作。该类的主要功能包括初始化、压入（Push）、弹出（Pop）、获取栈顶元素以及判断栈是否为空等。 ```python class LinkedStack(object): def __init__(self): """ 初始化链栈 """ self.top = None # 栈顶指针初始为None def push(self, value): """ 压入新元素到栈顶 """ new_node = Node(value) # 创建新的节点 new_node.next = self.top # 新节点的 next 指向当前栈顶 self.top = new_node # 更新栈顶指针 return f"成功压入 {value} 到栈顶" def pop(self): """ 弹出栈顶元素并返回其值 """ if self.is_empty(): raise Exception("栈已空，无法执行 Pop 操作") # 如果栈为空，则抛出异常 popped_value = self.top.data # 获取栈顶元素的值 self.top = self.top.next # 将栈顶指针移动到下一个节点 return popped_value def peek(self): """ 查看栈顶元素而不移除 """ if self.is_empty(): raise Exception("栈已空，无法执行 Peek 操作") return self.top.data def is_empty(self): """ 判断栈是否为空 """ return self.top is None def size(self): """ 返回栈中元素的数量 """ count = 0 current = self.top while current: count += 1 current = current.next return count ``` #### 3. 测试代码 下面是一个简单的测试案例，展示如何使用上述链栈类进行基本的操作。 ```python if __name__ == "__main__": stack = LinkedStack() print(stack.push(1)) # 成功压入 1 到栈顶 print(stack.push(2)) # 成功压入 2 到栈顶 print(f"栈顶元素: {stack.peek()}") # 栈顶元素应为 2 print(f"弹出元素: {stack.pop()}") # 弹出元素应为 2 print(f"栈是否为空: {stack.is_empty()}") # 应为 False print(f"栈的大小: {stack.size()}") # 大小应为 1 ``` --- ### 关键特性说明 - **时间复杂度** - Push 和 Pop 的时间复杂度均为 O(1)，因为它们仅涉及修改头结点及其指针[^4]。 - **空间复杂度** - 动态分配内存给每个节点，因此空间复杂度取决于实际存储的元素数量。 --- ### 问题