1. 题目
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
要求:
- pop、push、getMin操作的时间复杂度都是。
- 设计的栈类型可以使用现成的栈结构。
2. 思路
- 用两个栈来实现，栈sData存放入栈元素，栈sMin存放最小值。
- 按照元素入栈顺序，将要入栈的第一个元素，同时压入两个栈中。后续每个元素入栈时，与sMin栈中栈顶元素比较大小，若入栈元素data 小于sMin栈顶元素，则把data同时压入两个栈中，若data大于sMin栈中栈顶元素，则只压入栈sData中。出栈时，判断两个栈顶元素是否相等，若相等则两个栈同时执行出栈操作，不相等则，只有栈sData执行出栈操作。
3. 代码
#include <iostream>
#include <exception>
#include <stack>
template<class T> class MinStack {
public:
void push(const T& num);
T pop();
T getMin() const;
private:
std::stack<T> sData; // 数据栈
std::stack<T> sMin; // 最小栈
};
template<typename T>
T MinStack<T>::getMin() const{
if (sMin.empty()) {
throw std::runtime_error("min stack is empty");
} else {
return sMin.top(); // top是获取栈顶元素
}
}
template<class T>
void MinStack<T>::push(const T& num) {
if (sData.empty()) { // 如果当前数据栈为空
sData.push(num);
sMin.push(num);
} else if (num < getMin()){ // 如果当前数小于sMin栈的元素
sData.push(num);
sMin.push(num);
} else {
sData.push(num);
}
}
template<class T>
T MinStack<T>::pop() {
if (sData.top() == sMin.top()) { // 如果sData栈顶元素等于sMin栈顶元素
sData.pop();
sMin.pop();
} else {
sData.pop();
}
}
int main() {
MinStack<int> s;
s.push(5);
s.push(3);
s.push(2);
s.push(4);
s.push(6);
s.push(3);
s.push(1);
std::cout << s.getMin() << std::endl;
s.pop();
std::cout << s.getMin() << std::endl;
s.pop();
std::cout << s.getMin() << std::endl;
s.pop();
std::cout << s.getMin() << std::endl;
s.pop();
std::cout << s.getMin() << std::endl;
s.pop();
std::cout << s.getMin() << std::endl;
s.pop();
return 0;
}
