Java 实现有 getMin 功能的栈
作者：秋名山码民
- 2022 年 7 月 15 日
本文字数：1423 字
阅读完需：约 5 分钟
题目：实现栈的基本功能的情况下，再实现返回最小元素的操作
思路 1：开辟额外空间栈，一个用来本来栈的元素，另外一个用来标记最小元素，压入栈 2 始终压入当前最小值。栈顶元素始终为最小值
思路 2：与 1 不同的是，压入栈 2 如果不是最小值不执行操作，故对比 1 来说，2 稍微节省栈的空间，但是在弹出的时候会稍费时间
思路 1 实现：
package 栈和队列.getMin功能的栈;
import java.util.Stack;
public class One { public class MyStack2 { private Stack<Integer> stackData; private Stack<Integer> stackMin;
public MyStack2(){ //有参构造 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); }else{ int newMin = this.stackMin.peek(); this.stackMin.push(newMin); } this.stackData.push(newNum); }
public int pop(){ if(this.stackData.isEmpty()){ throw new RuntimeException("Your stack is Empty."); } this.stackMin.pop(); return this.stackData.pop(); }
public int getmin(){ if(this.stackMin.empty()){ throw new RuntimeException("Your stack is Empty."); } return this.stackMin.peek(); } }}
复制代码
方法 2 实现：
package 栈和队列.getMin功能的栈;
import java.util.Stack;
public class Two { //newNum，压入stackData中,判断stackMin栈顶元素比较，更小或者相等，则newNum也压入stackMin中 //当一样或大于时，stackMin栈不执行操作 public static void main(String[] args) {
}
public 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(); } }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【秋名山码民】的原创文章。
原文链接:【http://xie.infoq.cn/article/4b94bad1ca612a705c5ff3813】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
秋名山码民
关注
卷不死，就往…… 2021.10.19 加入
2019NOIP退役成员，华为云享专家，阿里云专家博主，csdn博主，努力进行算法分享，有问题欢迎私聊
评论