能否用c++编写最小栈设计并实现一个MinStack类,要求至少含有以下三种方法 一、push方法:将一个整数进行压栈 二、pop方法:弹出栈顶元素 三、getmin方法:输出栈内最小元素 输入格式: 第一行输入一个N,表示接下来要操作的数量 随后N行表示操作: push方法后跟要压栈的元素 pop方法、getmin方法后不跟任何元素 说明:假设不包含其他无效输入,以及在执行getmin、pop方法时栈不为空 输出样例: 输出栈内最小元素
时间: 2024-03-26 18:38:30 浏览: 26
好的,以下是用C++实现的MinStack类,支持push、pop和getmin操作:
```cpp
#include <iostream>
#include <stack>
using namespace std;
class MinStack {
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= s2.top()) {
s2.push(x);
}
}
void pop() {
if (s1.top() == s2.top()) {
s2.pop();
}
s1.pop();
}
int getmin() {
return s2.top();
}
private:
stack<int> s1; // 存储元素
stack<int> s2; // 存储当前最小元素
};
```
在push操作中,如果当前元素小于等于最小元素栈的栈顶元素,则将该元素也插入最小元素栈中。在pop操作中,如果弹出的元素是最小元素,则同步弹出最小元素栈中的栈顶元素。在getmin操作中,直接返回最小元素栈的栈顶元素即可。
接下来是完整的程序代码,可以用于输入输出和测试:
```cpp
#include <iostream>
#include <stack>
using namespace std;
class MinStack {
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= s2.top()) {
s2.push(x);
}
}
void pop() {
if (s1.top() == s2.top()) {
s2.pop();
}
s1.pop();
}
int getmin() {
return s2.top();
}
private:
stack<int> s1; // 存储元素
stack<int> s2; // 存储当前最小元素
};
int main() {
int n;
cin >> n;
MinStack s;
while (n--) {
string op;
cin >> op;
if (op == "push") {
int x;
cin >> x;
s.push(x);
} else if (op == "pop") {
s.pop();
} else if (op == "getmin") {
cout << s.getmin() << endl;
}
}
return 0;
}
```
输入格式如下:
```
6
push 3
push 2
push 5
getmin
pop
getmin
```
输出格式如下:
```
2
3
```