实现一个特殊的栈，在实现栈的基本功能的基础上,再实现返回栈中最小

题目如下：

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返
回栈中最小元素的操作。
【要求】
1．pop、push、getMin操作的时间复杂度都是O(1)。
2．设计的栈类型可以使用现成的栈结构。

解题思路：设置两个栈，data栈和min栈。data栈存放所有的数，min栈存放当前栈中的最小值。

这里有两种实现方式，虽然它们的思想其实是一样的。但还是分别说一下吧。

（1）data栈和min栈不同步操作
每当一个数入栈data，就将此数和min栈的栈顶元素进行比较，如果比min栈的栈顶元素要小，就压入min栈；否则，min栈不做任何操作。在进行pop操作时，弹出data栈的栈顶元素，如果此数和min栈的栈顶相等，则min栈的栈顶元素也弹出。

public static class MyStack1 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1() {
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        public void push(int newNum) {
            // 处理min栈
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum <= this.getmin()) {
                this.stackMin.push(newNum);
            }

            // 处理data栈
            this.stackData.push(newNum);
        }

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

            // 弹出data栈的栈顶元素，如果此数和min栈的栈顶相等，min栈的栈顶也弹出
            int value = this.stackData.pop();
            if (value == this.getmin()) {
                this.stackMin.pop();
            }
            return value;
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            // 返回min栈的栈顶元素，但不弹出
            return this.stackMin.peek();
        }
    }

（2）data栈和min栈同步操作
每当一个数入栈data，就将此数和min栈的栈顶进行比较，如果当前数比min栈的栈顶小，就入栈；否则，min栈重复压入它的栈顶值。在进行pop操作时，返回data栈的栈顶元素，并且将两个栈的栈顶元素都出栈。

public static class MyStack2 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack2() {
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        public void push(int newNum) {
            // 处理min栈
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum < this.getmin()) {
                this.stackMin.push(newNum);
            } else {
                int newMin = this.stackMin.peek();
                this.stackMin.push(newMin);
            }

            // 处理data栈
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            // 返回data栈的栈顶元素，并且将两个栈的栈顶元素都出栈
            this.stackMin.pop();
            return this.stackData.pop();
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            // 返回min栈的栈顶元素，但不弹出
            return this.stackMin.peek();
        }
    }