设计一个有getMin功能的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package chapter01_stackandqueue;
import java.util.Stack;
/**
*
* 实现一个特殊的栈，在实现栈的基本功能的基础上，在实现返回栈中最小元素的操作。 要求： 1. pop、push、getMin操作的时间复杂度都是O(1)
* 2. 设计的栈类型可以使用现成的栈结构
*
* @author dream
*
*/
public class Problem01_GetMinStack {
public static class MyStack1 {
/**
* 两个栈，其中stacMin负责将最小值放在栈顶，stackData通过获取stackMin的peek()函数来获取到栈中的最小值
*/
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
/**
* 在构造函数里面初始化两个栈
*/
public MyStack1() {
stackData = new Stack<Integer>();
stackMin = new Stack<Integer>();
}
/**
* 该函数是stackData弹出栈顶数据，如果弹出的数据恰好等于stackMin的数据，那么stackMin也弹出
* @return
*/
public Integer pop() {
Integer num = (Integer) stackData.pop();
if (num == getmin()) {
return (Integer) stackMin.pop();
}
return null;
}
/**
* 该函数是先判断stackMin是否为空，如果为空，就push新的数据，如果这个数小于stackMin中的栈顶元素，那么stackMin需要push新的数，不管怎么样
* stackData都需要push新的数据
* @param value
*/
public void push(Integer value) {
if (stackMin.isEmpty()) {
stackMin.push(value);
}
else if (value < getmin()) {
stackMin.push(value);
}
stackData.push(value);
}
/**
* 该函数是当stackMin为空的话第一次也得push到stackMin的栈中，返回stackMin的栈顶元素
* @return
*/
public Integer getmin() {
if (stackMin == null) {
throw new RuntimeException("stackMin is empty");
}
return (Integer) stackMin.peek();
}
}
public static void main(String[] args) throws Exception {
/**
* 要注意要将MyStack1声明成静态的，静态内部类不持有外部类的引用
*/
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());
System.out.println(stack1.pop());
System.out.println(stack1.getmin());
System.out.println("=============");
}
}
复制代码