Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
class MinStack {
public:
struct Node
{
int val;
int cntEmlem;
Node(int value,int count) : val(value),cntEmlem(count){}
};
void push(int x) {
stk.push(x);
if(minStk.empty() || x < minStk.top().val)
{
Node n(x,1);
minStk.push(n);
}
else
{
Node n = minStk.top();
n.cntEmlem++;
minStk.pop();
minStk.push(n);
}
}
void pop() {
stk.pop();
Node n = minStk.top();
minStk.pop();
n.cntEmlem--;
if(n.cntEmlem > 0)
{
minStk.push(n);
}
}
int top() {
return stk.top();
}
int getMin() {
return minStk.top().val;
}
private:
std::stack<int> stk;
std::stack<Node> minStk;
};原文:http://blog.csdn.net/akibatakuya/article/details/41280453