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.

class MinStack {    stack
     
       s;    stack
      
        s_min;    public:    void push(int x) {        s.push(x);        if (s_min.empty() || x <= s_min.top()) {            s_min.push(x);        }    }    void pop() {        if (s.top() == s_min.top()) {            s_min.pop();        }        s.pop();    }    int top() {        return s.top();    }    int getMin() {        return s_min.top();    }};
      
     

老题了，用两个栈就可以了，后来想了个用链表的，可是爆内存了。唔唔唔。下面是链表的：

struct node {    int val;    node *next;    node *min;    node():val(-1), next(NULL), min(NULL){}    node(int v):val(v), next(NULL), min(NULL){}};class MinStack {    node head;    public:    void push(int x) {        node *top, *pre;        if(head.next == NULL) {            head.next = new node(x);            top = head.next;            top->min = top;        } else {            pre = head.next;            head.next = new node(x);            top = head.next;            top->next = pre;            if (x <= pre->min->val) {                top->min = top;            } else {                top->min = pre->min;            }        }    }    void pop() {        if (head.next == NULL) return;        node *tmp = head.next;        head.next = tmp->next;        delete tmp;    }    int top() {        return head.next->val;    }    int getMin() {        return head.next->min->val;    }};