根据栈的抽象数据类型的定义,实现一个链栈。程序实现数据的插入、遍历、删除等操作。
时间: 2024-03-22 09:39:42 浏览: 16
好的,下面是一个基于链表实现的栈的示例代码:
```python
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkedStack:
def __init__(self):
self.top = None
def is_empty(self):
return self.top is None
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.is_empty():
raise Exception("Stack is empty!")
data = self.top.data
self.top = self.top.next
return data
def peek(self):
if self.is_empty():
raise Exception("Stack is empty!")
return self.top.data
def __len__(self):
count = 0
p = self.top
while p:
count += 1
p = p.next
return count
def traverse(self):
p = self.top
while p:
print(p.data, end=" ")
p = p.next
print()
```
在这个示例代码中,我们首先定义了一个`Node`类来表示栈中的每个元素,包括数据`data`和指向下一个节点的指针`next`。然后定义了`LinkedStack`类来表示整个链栈,其中`top`表示栈顶节点。
接下来,我们依次实现了链栈的基本操作:
- `is_empty()`:判断栈是否为空;
- `push(data)`:向栈中插入一个元素;
- `pop()`:从栈中删除一个元素并返回其值;
- `peek()`:返回栈顶元素的值,但不删除它;
- `__len__()`:返回栈的长度;
- `traverse()`:遍历整个栈并打印出每个元素的值。
如果你想要使用这个链栈,可以按照以下步骤:
```python
stack = LinkedStack() # 创建一个空栈
stack.push(1) # 向栈中插入元素
stack.push(2)
stack.push(3)
print(len(stack)) # 打印栈的长度
stack.traverse() # 遍历栈并打印出每个元素的值
print(stack.pop()) # 从栈中删除一个元素并返回其值
print(stack.peek()) # 返回栈顶元素的值,但不删除它
```
输出结果应该为:
```
3
3 2 1
3
2
```