算法案例(2)----------实现一个具有getMin功能的栈

布满荆棘的人生 2023-06-27 08:49 40阅读 0赞

# 零、简介 #

*  记录 左程云 大神的  程序员代码面试指南 一书里面的算法实现。
 *  代码路径： [https://github.com/1956025812/algorithm][https_github.com_1956025812_algorithm] 
 *  2020年开始每周一道算法，成就自己的算法之路~

# 一、题目 #

*  题目： 实现一个具有getMin功能的栈。
 *  要求： pop、push、getMin的时间复杂度都是o(1)。可以使用现有的栈结构。

# 二、实现思路 #

*  内部定义另一个临时栈，始终存放最小值即可。
 *  push数据的时候，与临时栈栈顶元素比较，如果小于或等于，则同步push到临时栈的栈顶；
 *  pop数据的时候，与临时栈栈顶元素比较，如果一样，则同步将临时栈的数据pop出来；
 *  getMin功能，临时栈的栈顶元素始终都是最小值，一个pop操作的复杂度就是o(1);

# 三、案例 #

## 3.1 代码 ##

package day20200101;
    
    import java.util.Stack;
    
    /**
     * 题目：  设计一个有getMin功能的栈
     * 要求：
     * 1. pop、push、getMin的时间复杂度都是o(1)
     * 2. 设计的栈类型可以使用现成的栈结构
     * <p>
     * 思路：
     * 构造一个临时的栈，用来存放最小的数据。
     * push数据的时候与临时栈的栈顶元素做比较，如果小于或等于，就放到临时栈。注意： 小于和等于都要放。
     * pop数据的时候与临时栈的栈顶元素做比较，如果一样，则同步pop
     */
    public class MyMinStack {
    
        private Stack<Integer> dataStack;
        private Stack<Integer> tempStack;
    
        public MyMinStack() {
            this.dataStack = new Stack<>();
            this.tempStack = new Stack<>();
        }
    
        /**
         * push方法
         *
         * @param data 新数据
         */
        public void push(Integer data) {
            dataStack.push(data);
    
            if (tempStack.isEmpty()) {
                tempStack.push(data);
            } else {
                if (data <= tempStack.peek()) {
                    tempStack.push(data);
                }
            }
        }
    
    
        /**
         * pop方法
         *
         * @return 栈顶元素
         */
        public Integer pop() {
            if (dataStack.isEmpty()) {
                throw new RuntimeException("当前栈dataStata没有数据");
            }
    
            // 如果要pop的元素正好是最小元素，则要同时一起将临时栈的元素pop
            Integer popData = dataStack.peek();
            if (popData.equals(tempStack.peek())) {
                tempStack.pop();
            }
    
            return dataStack.pop();
        }
    
    
        /**
         * getMin方法
         *
         * @return 栈的最小元素
         */
        public Integer getMin() {
            if (tempStack.isEmpty()) {
                throw new RuntimeException("当前栈dataStata没有数据");
            }
            return tempStack.pop();
        }
    
    
        public static void main(String[] args) {
            MyMinStack myMinStack = new MyMinStack();
            myMinStack.push(3);
            myMinStack.push(2);
            myMinStack.push(3);
            myMinStack.push(6);
            myMinStack.push(1);
            System.out.println(myMinStack.getMin());
            myMinStack.pop();
            System.out.println(myMinStack.getMin());
        }
    }

## 3.2 测试 ##

1
    2

[https_github.com_1956025812_algorithm]: https://github.com/1956025812/algorithm