12. Min Stack

Solution:

1) LinkedList
Node head;
    public MinStack() {
        // do intialization if necessary
        head = null;
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        // write your code here
      if (head == null) {
          head = new Node(number, number, null);
      } else {
          head = new Node(number, Math.min(number, head.min), head);
      }
    }

    /*
     * @return: An integer
     */
    public int pop() {
        // write your code here
        int rst = head.val;
        head = head.next;
        return rst;
    }

    /*
     * @return: An integer
     */
    public int min() {
        // write your code here
        return head.min;
    }
   
    private class Node {
        int val;
        int min;
        Node next;
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }


2) Two stack
Deque<Integer> s1;
    Deque<Integer> s2;
   
    public MinStack() {
        s1 = new ArrayDeque<Integer>();
        s2 = new ArrayDeque<Integer>();
    }
   
    public void push(int number) {
        s1.push(number);
        if (s2.isEmpty() || number <= min()) s2.push(number);
    }
   
    public int pop() {
        if (s1.peek() == min()) s2.pop();
        return s1.pop();
    }
   
    public int min() {
        return s2.peek();
    }