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

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

思路：建立两个栈，一个data栈压入数据（和正常的压栈一样），另一个min栈压入最小值。如果压入的数据比当前最小值小则压入min栈，大于当前最小值则重复压入当前min栈栈顶元素。 min栈和data保持同步的入栈出栈操作，这样始终保持min栈栈顶元素为最小值。

public static class MyStack1 {
    
        private StackInteger>
     stackData;
    
        private StackInteger>
     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();

        }

    }
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！