Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
使用C++编程，其中使用了标准库中的容器stack，使用两个stack，一个用来存放最小优先的栈s1，一个用来存放所以元素s2。
对于push操作，如果x小于等于s1中的栈顶元素，则将x压入s1和s2，否则x大于s1的栈顶元素，则将x只压入s2中。
对于pop操作，如果要出栈，则正常情况下，从s2中弹出栈顶元素，但是当s1的栈顶元素与s2的栈顶元素相同的时候，则需要将s1和s2的栈顶元素都弹出来
对于top操作，访问栈顶元素，只有s2不为空，就可以直接访问栈顶元素
对于getMin擦，从s1中返回的栈顶元素就是最小的元素
C++完整代码如下：
#include<iostream> #include<stack> using namespace std; class MinStack { public: void push(int x) { if(s2.empty()) { s1.push(x); s2.push(x); return; } int tmp=s1.top(); if(x<=tmp) s1.push(x); s2.push(x); } void pop() { if(!s2.empty()) { if(s1.top()==s2.top()) s1.pop(); s2.pop(); } } int top() { if(!s2.empty()) return s2.top(); return 0; } //s1为空的时候，s2同样也会为空 int getMin() { if(!s1.empty()) return s1.top(); return 0; } private: stack<int> s1;//存放最小值 stack<int> s2;//存放所有的元素 }; int main() { MinStack minstack; minstack.push(100); minstack.push(24); minstack.push(30); cout<<minstack.getMin()<<endl; }
运行结果：
还有一种比较笨的方法是每次要push一个元素时，将元素x插入在最小栈中，但是这样需要每次将元素插入到正确的位置，因此需要排序所有的元素。
#include<iostream> #include<stack> using namespace std; class MinStack { public: void push(int x) { int tmp; while(!s1.empty()) { tmp=top(); if(x<=tmp) break; else { s1.pop(); s2.push(tmp); } } s1.push(x); while(!s2.empty()) { tmp=s2.top(); s2.pop(); s1.push(tmp); } } void pop() { if(!s1.empty()) s1.pop(); } int top() { if(!s1.empty()) return s1.top(); return 0; } int getMin() { if(!s1.empty()) return s1.top(); return 0; } private: stack<int> s1; stack<int> s2; }; int main() { MinStack minstack; minstack.push(1); minstack.push(2); minstack.push(3); cout<<minstack.getMin()<<endl; }
