【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。
方案一的代码实现如下：
1 import java.util.Stack; 2 public class MyStack1 { 3 private Stack<Integer> stackData; 4 private Stack<Integer> stackMin; 5 public MyStack1() 6 { 7 this.stackData=new Stack<Integer>(); 8 this.stackMin=new Stack<Integer>(); 9 } 10 public void push(int newNum) 11 { 12 if(this.stackMin.isEmpty()||newNum<=this.getmin()) 13 this.stackMin.push(newNum); 14 this.stackData.push(newNum); 15 } 16 public int pop() 17 { 18 if(this.stackData.isEmpty()) 19 System.out.println("Your stack is empty!"); 20 int value=this.stackData.pop(); 21 if(value==this.getmin()) 22 this.stackMin.pop(); 23 return value; 24 } 25 public int getmin() 26 { 27 if(this.stackMin.isEmpty()) 28 System.out.println("Your stack is empty!"); 29 return this.stackMin.peek(); 30 } 31 public static void main(String[] args) 32 { 33 MyStack1 s=new MyStack1(); 34 s.push(3); 35 s.push(4); 36 s.push(5); 37 s.push(1); 38 s.push(2); 39 s.push(1); 40 System.out.println(s.getmin()); 41 System.out.println(s.pop()); 42 System.out.println(s.pop()); 43 System.out.println(s.pop()); 44 System.out.println(s.pop()); 45 System.out.println(s.pop()); 46 System.out.println(s.pop()); 47 System.out.println(s.pop()); 48 } 49 }
运行结果如下：
1
1
2
1
5
4
3
Your stack is empty!
方法二的实现代码如下：
1 import java.util.Stack; 2 public class MyStack2 { 3 private Stack<Integer> stackData; 4 private Stack<Integer> stackMin; 5 public MyStack2() 6 { 7 this.stackData=new Stack<Integer>(); 8 this.stackMin=new Stack<Integer>(); 9 } 10 public void push(int newNum) 11 { 12 if(this.stackMin.isEmpty()||newNum<this.getmin()) 13 this.stackMin.push(newNum); 14 else 15 { 16 int newMin=this.stackMin.peek(); 17 this.stackMin.push(newMin); 18 } 19 this.stackData.push(newNum); 20 } 21 public int pop() 22 { 23 if(this.stackData.isEmpty()) 24 System.out.println("Your stack is empty!"); 25 this.stackMin.pop(); 26 return this.stackData.pop(); 27 } 28 public int getmin() 29 { 30 if(this.stackMin.isEmpty()) 31 System.out.println("Your stack is empty!"); 32 return this.stackMin.peek(); 33 } 34 public static void main(String[] args) 35 { 36 MyStack2 s=new MyStack2(); 37 s.push(3); 38 s.push(4); 39 s.push(5); 40 s.push(1); 41 s.push(2); 42 s.push(1); 43 System.out.println(s.getmin()); 44 System.out.println(s.pop()); 45 System.out.println(s.pop()); 46 System.out.println(s.pop()); 47 System.out.println(s.pop()); 48 System.out.println(s.pop()); 49 System.out.println(s.pop()); 50 System.out.println(s.pop()); 51 } 52 }
运行结果如下：
1
1
2
1
5
4
3
Your stack is empty!
