7-1 最小栈设计并实现一个MinStack类 C++
时间: 2024-09-12 07:09:59 浏览: 16
设计一个最小栈MinStack类,需要实现的功能是能够在O(1)时间内得到栈内的最小元素。这通常可以通过维护一个辅助栈来实现,这个辅助栈用于存储每个元素对应的最小值。
以下是MinStack类的基本实现方法:
```cpp
#include <stack>
using namespace std;
class MinStack {
private:
stack<int> dataStack; // 主栈,存放所有元素
stack<int> minStack; // 辅助栈,存放当前最小元素
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
dataStack.push(x);
// 当辅助栈为空或者新元素小于等于辅助栈栈顶元素时,将新元素压入辅助栈
if (minStack.empty() || x <= minStack.top()) {
minStack.push(x);
}
}
void pop() {
if (dataStack.empty()) {
return;
}
int top = dataStack.top();
dataStack.pop();
// 如果弹出的元素是当前最小元素,则辅助栈也弹出该元素
if (top == minStack.top()) {
minStack.pop();
}
}
int top() {
if (dataStack.empty()) {
throw out_of_range("Stack is empty");
}
return dataStack.top();
}
int getMin() {
if (minStack.empty()) {
throw out_of_range("Stack is empty");
}
return minStack.top();
}
};
```
在这个实现中,每次压入新元素时,我们检查该元素是否小于或等于当前的最小值。如果是,那么我们也将它压入辅助栈。当弹出元素时,如果弹出的元素正好是当前的最小值,那么我们也将其从辅助栈中弹出。这样,辅助栈的栈顶始终保持了当前栈内的最小值。