栈和队列——设计一个有getMin功能的栈（二）

红太狼 2022-06-09 06:20 142阅读 0赞

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

import java.util.Stack;
    class Mystack2{
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
    
        public Mystack2(){
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }
        //入栈
        public void push(int newNum){
            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);
            }
        }
        //出栈
        public int pop(){
            if(this.stackData.isEmpty()){
                throw new RuntimeException("Your stack is empty.");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }
        //取最小值
        public int getmin(){
            if(this.stackMin.isEmpty()){
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

【解析】  
　　这一篇和上一篇的两种对于此问题的解法其实都是用了另一个栈stackMin来保存stackData中的最小值，共同点是所有操作的时间复杂度都是O(1)、空间复杂度都是O(n)。区别是（一）的方案stackMin压入稍省空间，弹出操作稍费时间，（二）的方案stackMin压入稍省费空间，但是弹出稍省时间