语言C++。请编写程序,设计并实现一个最小栈类模板MinStack,可支持任意数据类型,要求至少含有以下三种方法: 1)push方法:将一个数据压栈 2)pop方法:弹出栈顶元素 3)getmin方法:返回栈内最小元素 编写main函数用不同类型数据对其进行测试。
时间: 2024-12-24 11:29:35 浏览: 6
在C++中,我们可以创建一个模板类`MinStack`来满足这个需求。下面是一个简单的实现:
```cpp
#include <iostream>
#include <stack>
template <typename T>
class MinStack {
private:
std::stack<T> mainStack;
std::stack<T> minStack;
public:
// push method
void push(T value) {
mainStack.push(value);
if (minStack.empty() || value <= minStack.top()) {
minStack.push(value);
}
}
// pop method
void pop() {
if (!mainStack.empty()) {
T topValue = mainStack.top();
mainStack.pop();
if (topValue == minStack.top()) {
minStack.pop();
}
}
}
// getmin method
T getMin() {
return minStack.empty() ? T{} : minStack.top(); // 返回空值防止除0错误
}
};
int main() {
MinStack<int> s;
s.push(5);
s.push(-2);
s.push(0);
s.push(3);
std::cout << "Minimum element: " << s.getMin() << std::endl; // Output: Minimum element: -2
s.pop();
std::cout << "Minimum element after popping 5: " << s.getMin() << std::endl; // Output: Minimum element after popping 5: 0
return 0;
}
```
在这个例子中,我们使用了两个栈,主栈`mainStack`用于存储常规的数据,辅助栈`minStack`用于保存当前已知的最小值。`push`方法会检查新插入的元素是否小于等于最小值,如果是,则也推入到`minStack`;`pop`方法如果移除了栈顶的最小值,就从`minStack`中移除。`getMin`方法直接返回`minStack`的顶部,即最小值。
你可以使用其他类型的值替换`int`,如`float`, `double`, 或自定义类型,只要它们可以进行比较即可。
阅读全文