### Python 实现顺序栈和链栈的基本操作 #### 1. **顺序栈** 顺序栈是一种基于数组的数据结构，其存储空间是连续的。以下是顺序栈的基本操作代码示例： ```python class SeqStack: def __init__(self, max_size=10): self.stack = [] # 使用列表模拟栈 self.max_size = max_size def push(self, item): if len(self.stack) >= self.max_size: # 判断栈是否已满 raise Exception("Stack Overflow") self.stack.append(item) def pop(self): if not self.stack: # 判断栈是否为空 raise Exception("Stack Underflow") return self.stack.pop() def peek(self): if not self.stack: raise Exception("Stack is empty") return self.stack[-1] def is_empty(self): return len(self.stack) == 0 def size(self): return len(self.stack) # 测试顺序栈功能 if __name__ == "__main__": seq_stack = SeqStack() seq_stack.push(10) seq_stack.push(20) print(f"Top element: {seq_stack.peek()}") # 输出栈顶元素[^1] print(f"Size of stack: {seq_stack.size()}") # 获取栈大小[^1] print(seq_stack.pop()) # 弹出栈顶元素[^1] print(f"Is the stack empty? {seq_stack.is_empty()}") # 判断栈是否为空 ``` --- #### 2. **链栈** 链栈是一种基于链表的数据结构，其节点通过指针连接在一起。以下是链栈的基本操作代码示例： ```python class Node: def __init__(self, data=None): self.data = data self.next = None class LinkStack: def __init__(self): self.top = None def push(self, item): new_node = Node(item) new_node.next = self.top # 新节点指向当前栈顶 self.top = new_node # 更新栈顶为新节点 def pop(self): if self.top is None: # 如果栈为空，则抛出异常 raise Exception("Stack Underflow") popped_data = self.top.data self.top = self.top.next # 移动栈顶到下一个节点 return popped_data def peek(self): if self.top is None: # 如果栈为空，则抛出异常 raise Exception("Stack is empty") return self.top.data def is_empty(self): return self.top is None # 测试链栈功能 if __name__ == "__main__": link_stack = LinkStack() link_stack.push(30) link_stack.push(40) print(f"Top element: {link_stack.peek()}") # 输出栈顶元素[^1] print(link_stack.pop()) # 弹出栈顶元素[^1] print(f"Is the stack empty? {link_stack.is_empty()}") # 判断栈是否为空 ``` --- ### 总结 以上分别展示了如何使用Python实现顺序栈和链栈的基本操作。顺序栈依赖于固定大小的数组来管理数据，而链栈则通过动态分配内存的方式构建节点并链接起来。