编程题：包含min函数的栈

缺乏、安全感 2022-05-23 05:50 167阅读 0赞

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

思路：空间换时间，用一个辅助栈记录当前栈的最小值。

stack.peek（）和stack.pop()的区别：

两者都是返回stack栈顶的值，peek()返回值但不删除该元素，pop()会把栈顶的元素删除。

代码：

package net.stxy.one.controller;
    
    /**
     * Created by ASUS on 2018/5/26
     *
     * @Authod Grey Wolf
     */
    
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class Test2 {
    
        //数据栈
        private Stack<Integer>data=new Stack<>();
        //辅助栈
        private Stack<Integer>minData=new Stack<>();
    
        /**
         * 进栈
         * @param value
         */
        public void push(int value){
            if(minData.isEmpty()||minData.peek()>=value){
                minData.push(value);
            }else {
                //再把栈顶元素加进来，维持跟数据栈元素个数一样
                minData.push(minData.peek());
            }
            data.push(value);
        }
    
        /**
         * 出栈
         */
        public void pop(){
            if(minData.isEmpty()||data.isEmpty()){
                return;
            }
            minData.pop();
            data.pop();
        }
    
        /**
         * 返回栈顶元素
         * @return
         */
        public int top(){
            if(!data.isEmpty()){
                return data.peek();
            }
            return 0;
        }
        /**
         * 返回最小值
         * @return
         */
        public int min(){
            if (!minData.isEmpty()){
                return minData.peek();
            }
            return 0;
        }
    
    
        public static void main(String[] args) {
            Test2 test2 = new Test2();
           test2.push(3);
           test2.push(2);
           test2.push(4);
           test2.push(1);
           test2.push(5);
           int min=test2.min();
            System.out.println("min:"+min);
    
        }
    
    
    
    
    }

效果：

min:1  
  
Process finished with exit code 0

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。