按照教材中抽象数据类型栈的定义,编程实现顺序栈/链栈,并通过主函数调用,简单测试各基本操作函数的正确性。
时间: 2024-02-27 08:53:12 浏览: 24
好的,以下是顺序栈和链栈的实现代码:
## 顺序栈的实现
```python
class Stack:
def __init__(self, size):
self.stack = [None] * size # 初始化栈
self.top = -1 # 栈顶指针
self.size = size # 栈的大小
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.size - 1
def push(self, item):
if self.is_full():
raise Exception("Stack is full")
else:
self.top += 1
self.stack[self.top] = item
def pop(self):
if self.is_empty():
raise Exception("Stack is empty")
else:
item = self.stack[self.top]
self.top -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
else:
return self.stack[self.top]
```
## 链栈的实现
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def is_empty(self):
return self.top is None
def push(self, item):
new_node = Node(item)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.is_empty():
raise Exception("Stack is empty")
else:
item = self.top.data
self.top = self.top.next
return item
def peek(self):
if self.is_empty():
raise Exception("Stack is empty")
else:
return self.top.data
```
以下是主函数的测试代码:
```python
if __name__ == '__main__':
# 测试顺序栈
print("Testing sequential stack...")
stack = Stack(5)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())
print(stack.pop())
print(stack.peek())
# 测试链栈
print("Testing linked stack...")
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())
print(stack.pop())
print(stack.peek())
```
运行结果如下:
```
Testing sequential stack...
3
2
1
Testing linked stack...
3
2
1
```