实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作
时间: 2024-10-17 15:09:57 浏览: 61
实现一个特殊的栈,即带有一个额外功能可以返回栈中的最小元素,通常称为“最小堆栈”或“带有最小值的栈”。这种数据结构结合了栈的特性(后进先出LIFO)以及堆(最小/最大元素优先)的特点。我们可以使用两个栈来实现这个功能:
1. 主栈:用于存储常规的栈元素,遵循栈的插入和删除操作。
2. 辅助栈(也称为辅助队列):用于保存每次弹出主栈顶部元素时的最小值。
当向主栈添加新元素时:
- 如果这是第一个元素,直接压入主栈和辅助栈。
- 否则,比较新元素与辅助栈顶元素,如果新元素较小,则将辅助栈顶元素弹出并压回主栈,然后将新元素压入辅助栈。
当需要获取主栈的最小元素时:
- 只需访问辅助栈的栈顶元素即可,因为辅助栈始终包含当前已知的最小值。
从主栈中删除元素时:
- 弹出主栈顶部元素的同时,更新辅助栈的栈顶元素,如果新的栈顶元素比辅助栈的新顶小,就更新辅助栈。
以下是伪代码示例:
```python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
# 插入元素
def push(self, x):
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
# 删除元素
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
return None if not self.stack else self.stack[-1]
# 返回栈顶最小值
def top(self):
return self.min_stack[-1] if self.min_stack else None
# 判定栈是否为空
def empty(self):
return len(self.stack) == 0
```
阅读全文