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

电玩女神 2022-06-09 05:54 152阅读 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 条评论，152人围观）

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

相关阅读

相关栈和队列(一) 栈操作详解

文章目录一、物理结构和逻辑结构二、栈 1、什么是栈 2、栈中一些基本操作的实现 Stack.h

川长思鸟来/ 2024年03月23日 18:26/ 0 赞/ 58 阅读

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

零、简介记录左程云大神的程序员代码面试指南一书里面的算法实现。代码路径： [https://github.com/1956025812/algo

布满荆棘的人生/ 2023年06月27日 08:49/ 0 赞/ 14 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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