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

电玩女神 2022-06-09 05:54 126阅读 0赞

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

//实现一个特殊的栈，在实现栈的基本功能的基础上在实现返回栈中最小元素的操作
    import java.util.*;
    class MyStack1 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
    
        public MyStack1(){
            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);
            }
            this.stackData.push(newNum);
        }
    
        //出栈
        public int pop(){
            if(this.stackData.isEmpty()){
                throw new RuntimeException("Your stack is Empty");
            }
            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");
            }
            return this.stackMin.peek();
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关【栈与队列_1】设计一个有getMin功能的栈

> 实现自己梦想的最好方式就是学习~ 目录【题目】【要求】【难度】【解答】 1. 压入数据规则 2. 弹出数据

﹏ヽ暗。殇╰゛Y/ 2022年12月22日 06:26/ 0 赞/ 113 阅读

相关面试官：来，用Golang设计并实现一个有getMin功能的栈~

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

谁践踏了优雅/ 2022年09月12日 08:56/ 0 赞/ 165 阅读

相关栈和队列——用一个栈实现另一个栈的排序

【题目】　　一个栈中元素的类型为整形，现在想将该栈从顶到低从大到小顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？【解答

偏执的太偏执、/ 2022年06月09日 11:21/ 0 赞/ 160 阅读

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

【题目】　　设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作　　【要求】　　1、pop、push、getMin操作的时间复杂度

红太狼/ 2022年06月09日 06:20/ 0 赞/ 124 阅读

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

【题目】　　设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作　　【要求】　　1、pop、push、getMin操作的时间复杂度

电玩女神/ 2022年06月09日 05:54/ 0 赞/ 127 阅读

相关设计一个有getMin功能的栈

【题目】实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小的元素的操作。【要求】 1、pop、push、getMin操作的时间复杂度都是O(1)

Dear 丶/ 2022年02月24日 03:40/ 0 赞/ 161 阅读

相关很有想法的一个问题---用栈实现队列和用队列实现栈

1.栈实现队列：思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得

蔚落/ 2021年11月11日 20:04/ 0 赞/ 266 阅读

相关编写具有 getMin() 功能的栈

include <iostream> include <stack> using namespace std; class MySta

柔情只为你懂/ 2021年11月10日 22:12/ 0 赞/ 242 阅读

相关栈和队列的互相实现、以及带有GetMin的栈

两个栈实现一个队列：基本思路： 1. 创建两个栈A，B，A栈用来入栈，B栈用来出栈； 2. 入队列操作：a)A栈未满，直接入栈； b)A栈已满，B栈为空，将A栈中

Bertha 。/ 2021年09月26日 13:12/ 0 赞/ 287 阅读

相关栈/两个栈实现一个队列

Java实现 / @auther: 巨未 @DATE: 2019/1/5 0005 18:29 @Descripti

た入场券/ 2021年09月23日 07:02/ 0 赞/ 375 阅读