设计顺序栈,并实现基本运算
时间: 2024-05-02 07:21:02 浏览: 19
顺序栈是一种线性数据结构,它的特点是后进先出(LIFO)。
设计顺序栈需要定义以下几个元素:
1. 栈的最大容量(max_size)
2. 栈顶指针(top)
3. 存储栈元素的数组(data)
栈的基本运算包括:
1. 初始化栈(initStack)
2. 入栈(push)
3. 出栈(pop)
4. 获取栈顶元素(getTop)
5. 判断栈是否为空(isEmpty)
6. 判断栈是否已满(isFull)
下面是具体的实现代码:
```python
class SeqStack:
def __init__(self, max_size):
self.max_size = max_size
self.top = -1
self.data = [None] * max_size
def push(self, elem):
if self.isFull():
raise Exception("stack is full")
self.top += 1
self.data[self.top] = elem
def pop(self):
if self.isEmpty():
raise Exception("stack is empty")
elem = self.data[self.top]
self.top -= 1
return elem
def getTop(self):
if self.isEmpty():
raise Exception("stack is empty")
return self.data[self.top]
def isEmpty(self):
return self.top == -1
def isFull(self):
return self.top == self.max_size - 1
```
使用示例:
```python
# 初始化栈
stack = SeqStack(5)
# 入栈
stack.push(1)
stack.push(2)
stack.push(3)
# 获取栈顶元素
print(stack.getTop()) # 3
# 出栈
print(stack.pop()) # 3
print(stack.pop()) # 2
# 判断栈是否为空
print(stack.isEmpty()) # False
# 判断栈是否已满
print(stack.isFull()) # False
# 入栈
stack.push(4)
stack.push(5)
# 判断栈是否已满
print(stack.isFull()) # True
# 入栈,此时会抛出异常
stack.push(6)
```