【题目】

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1. pop、push、getMin操作的时间复杂度都是O(1)。
2. 设计的栈类型可以使用现成的栈结构。

package leif.algorithm_and_data_structure.stack_and_queue;

import java.util.Stack;

public class MyStack1 {
    private Stack<Integer> stackData = new Stack<Integer>();
    private Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int newNum) {
        stackData.push(newNum);

        if (stackMin.isEmpty() || newNum <= stackMin.peek()) {
            stackMin.push(newNum);
        }
    }

    public int pop() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }

        int value = stackData.pop();

        if (value == stackMin.peek()) {
            return stackMin.pop();
        }

        return value;
    }

    public int getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }

        return stackMin.peek();
    }
}

package leif.algorithm_and_data_structure.stack_and_queue;

import java.util.Stack;

public class MyStack2 {
    private Stack<Integer> stackData = new Stack<Integer>();
    private Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int newNum) {
        stackData.push(newNum);

        if (stackMin.isEmpty() || newNum <= stackMin.peek()) {
            stackMin.push(newNum);
        } else {
            stackMin.push(stackMin.peek());
        }
    }

    public int pop() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }

        stackMin.pop();
        return stackData.pop();
    }

    public int getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }

        return stackMin.peek();
    }
}