定义链栈以及使用各种链栈的操作函数
时间: 2024-09-22 14:05:58 浏览: 34
链栈_链栈的基本操作_链栈的清空_清空链栈_
5星 · 资源好评率100%
链栈是一种数据结构,它类似于数组构成的栈,但是内部元素通过链表的方式组织。在链栈中,数据项(节点)的添加和删除操作通常发生在栈顶,因为新元素总是添加到顶部,而移除时也是从顶部开始。
链栈的基本操作包括:
1. **初始化(Create Stack)**:创建一个新的空链栈,没有存储任何元素。
```python
def create_stack():
return None # 创建一个空链表表示空栈
```
2. **压入元素(Push)**:将新的元素添加到栈顶。
```python
def push(stack, item):
new_node = Node(item) # 创建新节点
new_node.next = stack # 新节点的next指向前一个元素
stack = new_node # 更新栈顶为新节点
return stack
```
3. **弹出元素(Pop)**:移除并返回栈顶元素,如果栈为空则抛出异常。
```python
def pop(stack):
if stack is None or stack.next is None:
raise Exception("Stack is empty")
top_item = stack.item # 保存栈顶元素
stack = stack.next # 移除栈顶节点
return top_item
```
4. **查看栈顶元素(Peek)**:返回栈顶元素,但不改变栈的状态(不会触发pop操作)。
```python
def peek(stack):
if stack is None:
raise Exception("Stack is empty")
return stack.item
```
5. **判断栈是否为空(IsEmpty)**:检查链栈是否包含元素。
```python
def is_empty(stack):
return stack is None or stack.next is None
```
阅读全文