【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。
方案一的代码实现如下：
代码语言：javascript复制 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 }运行结果如下：
代码语言：javascript复制1
1
2
1
5
4
3
Your stack is empty!方法二的实现代码如下：
代码语言：javascript复制 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 }运行结果如下：
代码语言：javascript复制1
1
2
1
5
4
3
Your stack is empty!
