实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返 回栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。
/*
* 实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返 回栈中最小元素的操作。
* 两种实现方式
* mystack1:如果最小栈为空,压入最小栈,再来的元素判断是否小于当前最小,如果小于当前最小栈的栈顶元素,则压入最小栈,
* 每一步都压入数据栈,弹出栈时先判断数据栈是否为空,如果不为空,先弹出数据栈元素,同时记录,并与最小栈元素比较,
* 如果相等,同时弹出最小栈元素。
* mystack2:压栈操作 先判断最小栈是否为空,如果空,压入最小栈,否则判断当前元素和最小栈栈顶元素的大小,
* 如果小于栈顶元素,压入最小栈,否则,栈顶元素重新压入最小栈。
* 弹出操作 判断数据栈是否为空,如果不为空,先弹出最小栈栈顶元素,然后弹出数据栈元素。
*/
import java.util.Stack; import javax.management.RuntimeErrorException; public class Getmin { public static class Mystack1 { private Stack stackData; private Stack stackMin; public Mystack1() { this.stackData = new Stack<>(); this.stackMin = new Stack<>(); } //获取最小 public int getmin() { if(this.stackMin.isEmpty()) { throw new RuntimeException("empty"); } return this.stackMin.peek(); } //压栈 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("empty"); } int temp = this.stackData.pop(); if(temp == this.getmin()) { this.stackMin.pop(); } return temp; } } public static class Mystack2{ private Stack stackData; private Stack stackMin; public Mystack2() { this.stackData = new Stack(); this.stackMin = new Stack(); } public int getmin() { if(this.stackMin.isEmpty()) { throw new RuntimeException("empty"); } return this.stackMin.peek(); } 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("empty"); } this.stackMin.pop(); return this.stackData.pop(); } } public static void main(String[] args) { // TODO Auto-generated method stub Mystack1 stack1 = new Mystack1(); stack1.push(3); System.out.println(stack1.getmin()); stack1.push(4); System.out.println(stack1.getmin()); stack1.push(1); System.out.println(stack1.getmin()); stack1.push(2); System.out.println(stack1.getmin()); System.out.println(stack1.pop()); System.out.println(stack1.getmin()); System.out.println("============="); Mystack2 stack2 = new Mystack2(); stack2.push(3); System.out.println(stack2.getmin()); stack2.push(4); System.out.println(stack2.getmin()); stack2.push(1); System.out.println(stack2.getmin()); stack2.push(2); System.out.println(stack2.getmin()); System.out.println(stack2.pop()); System.out.println(stack2.getmin()); } }