题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路
借助一个辅助栈，每次主栈入栈的时候，辅助栈也入栈；如果入栈的数字小于辅助栈的栈顶则辅助栈压入此数字， 如果大于等于栈顶元素，则压入栈顶元素；如此辅助栈的栈顶任何时候都是此栈的最小元素。
示例
stack1(从栈顶到栈底): 9 1 2 2 1 32 111 11 3 2 15 2 8 3 2 stackMin(栈顶到栈底): 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
class Solution {
public:
void push(int value) {
if (stackMin.empty())
stackMin.push(value);
if (value < stackMin.top())
stackMin.push(value);
else
stackMin.push(stackMin.top());
stack1.push(value);
}
void pop() {
if (!stackMin.empty())
stackMin.pop();
if (!stack1.empty())
stack1.pop();
}
int top() {
if (!stack1.empty())
return stack1.top();
return 0;
}
int min() {
if (!stackMin.empty())
return stackMin.top();
return 0;
}
void outPut(){
cout << "stack1(从栈顶到栈底): " << endl;
while (!stack1.empty()) {
cout << stack1.top() << " ";
stack1.pop();
}
cout << endl << "stackMin(栈顶到栈底): " << endl;
while (!stackMin.empty()) {
cout << stackMin.top() << " ";
stackMin.pop();
}
}
bool empty(){
if (stackMin.empty() && stack1.empty())
return true;
return false;
}
private:
stack<int> stack1,stackMin;
};
int main(){
Solution stack_test;
vector<int> v_stack = {2,3,8,2,15,2,3,11,111,32,1,2,2,1,9};
for (int i = 0; i < v_stack.size() ; ++i) {
stack_test.push(v_stack[i]);
}
stack_test.outPut();
// cout << " " << stack_test.empty();
return 0;
}
