欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法之栈的最小值

程序员文章站 2022-03-04 21:08:04
...

题目:
实现一个特殊的栈,在实现栈功能基础上,并实现返回栈的最小值

要求:
pop,push,getMin方法的时间复杂度O(1)
设计的栈类型可以使用现成的栈结构

Java的Stack类

Java的Stack类:
1. boolean empty()——测试堆栈是否为空。
2. Object peek( )——查看堆栈顶部的对象,但不从堆栈中移除它。
3. Object pop( )——移除堆栈顶部的对象,并作为此函数的值返回该对象。
4. Object push(Object element)——把项压入堆栈顶部。
5. int search(Object element)——返回对象在堆栈中的位置,以 1 为基数。

代码

package cn.scnu.stack;

/**
 * 题目:实现一个特殊的栈,在实现栈功能基础上,并实现返回栈的最小值
 *
 * 要求:
 *      pop,push,getMin方法的时间复杂度O(1)
 *      设计的栈类型可以使用现成的栈结构
 */

import java.util.Stack;

/**
 * Java的Stack类
 * 1 boolean empty()——测试堆栈是否为空。
 * 2 Object peek( )——查看堆栈顶部的对象,但不从堆栈中移除它。
 * 3 Object pop( )——移除堆栈顶部的对象,并作为此函数的值返回该对象。
 * 4 Object push(Object element)——把项压入堆栈顶部。
 * 5 int search(Object element)——返回对象在堆栈中的位置,以 1 为基数。
 */
class MyStack{
    private Stack<Integer> stackData = new Stack<>();
    private Stack<Integer> stackMin = new Stack<>();

    public void push(Integer num){
        this.stackData.push(num);
        if(this.stackMin.empty()){
            this.stackMin.push(num);
        }else if (num<=this.getMin()){ //小于等于在于如果两个相等的值,都是最小值,就算弹出其中一个,另一个也是剩下的最小值
            this.stackMin.push(num);
        }

    }
    public Integer pop(){
        if (this.stackData.empty()) {
            throw  new RuntimeException("你的栈为空");
        }else {
            int value  = this.stackData.pop();
            if(value == this.getMin()){
                this.stackMin.pop();
            }
            return value;
        }

    }
    public Integer getMin(){
        if(this.stackMin.empty()){
            throw  new RuntimeException("你的栈为空!!");
        }else{
            return this.stackMin.peek();
        }
    }

}

public class Demo01 {
    public static void main(String[] args) {

        /*
            算法实现原理
         */
        MyStack myStack = new MyStack();  //初始化一个栈

        /*
            添加数据:
                    1. 将数据添加到栈
                    2. 判断当前最小值存在不存在
                        1) 如果不存在,将该数据保存到最小值
                        2) 如果存在,将该数据和最小值比较,如果该数据小,则替换。
         */
        myStack.push(12);

        /*
            获取最小值:
                即,如果最小值栈不为空,那么最小值就是最顶的值
         */
        int min = myStack.getMin();
        System.out.println(min);
                /*
            弹出数据:
                    1. 将数据弹出
                    2. 如果该数据和最小值相等,则将最小值的栈也弹出一个
                    3. 如果不想等,那么最小值的栈不变
         */
        int num = myStack.pop();
        System.out.println(num);

        /*
            测试
         */
        MyStack myStack1 = new MyStack();

        for (int i = 10; i >0 ; i--) {
            myStack1.push(i);
        }
        //获取栈的最小值
        System.out.println("最小值="+myStack1.getMin());
        //获取一个栈的数据
        System.out.println(myStack1.pop());
        System.out.println("最小值="+myStack1.getMin());


    }

}

方法2


class MyStack2{
    private Stack<Integer> stackData = new Stack<>();
    private Stack<Integer> stackMin = new Stack<>();

    public void push(Integer num){
        this.stackData.push(num);
        if(this.stackMin.empty()){
            this.stackMin.push(num);
        }else if (num<=this.getMin()){
            this.stackMin.push(num);
        }else{
            //当num>this.getMin,则将上一个最小值重复压入,这样在取出的时候就不需要进行判断了
            int newNum = stackMin.peek();
            this.stackMin.push(newNum);
        }

    }
    public Integer pop(){
        if (this.stackData.empty()) {
            throw  new RuntimeException("你的栈为空");
        }
        this.stackMin.pop();
        return this.stackData.pop();

    }
    public Integer getMin(){
        if(this.stackMin.empty()){
            throw  new RuntimeException("你的栈为空!!");
        }else{
            return this.stackMin.peek();
        }
    }

}

区别如下

数据结构与算法之栈的最小值

相关标签: 算法