看书时遇到这样一道题，挺有趣的数据结构，所以记录下来
题目:
实现一个栈，该栈带有出栈(pop)，入栈(push)，取最小元素(getMin)，三个方法。要保证这3个方法的时间复杂度都是O(1)
算法：
1.定义两个栈，一个栈自定义栈用于入栈、出栈，一个辅助栈用于动态存放自定义栈的最小值
2.入栈操作，当元素压入 自定义栈 的时候，会判断辅助栈是否为空，
如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入(push) 辅助栈。
因为当第一个元素入栈时，这个唯一的元素也就是自定义栈当前最小的值，所以也压入(push) 辅助栈
3.出栈操作，如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。
代码如下：
入栈操作
如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/** * 入栈操作 * @param element 入栈的元素 */ public void push(int element){ mainStack.push(element); //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈 if(minStack.empty()|| element <= minStack.peek()){ //empty() 表示的是测试堆栈是否为空。 //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。 minStack.push(element); } }
出栈操作
如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈(pop)。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12/** * 出栈操作 */ public Integer pop(){ //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 if(mainStack.peek().equals(minStack.peek())){ minStack.pop(); } return mainStack.pop(); }
获取栈的最小元素(getMin方法)
复制代码
1
2
3
4
5
6
7
8
9
10/** * 获取栈的最小元素 */ public int getMin() throws Exception{ if(mainStack.empty()){ throw new Exception ("stack is empty"); } return minStack.peek(); }
主函数
元素入栈，输出最小值，元素出栈，再输出最小值
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public static void main(String[] args) throws Exception { MinStack stack=new MinStack(); stack.push(4); stack.push(9); stack.push(7); stack.push(3); stack.push(8); stack.push(5); System.out.println(stack.getMin()); stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.getMin()); }
运行结果：
3
4
完整代码
复制代码
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
53package min_ini; import java.util.Stack; public class MinStack { private Stack<Integer> mainStack=new Stack<Integer>(); private Stack<Integer> minStack=new Stack<Integer>(); /** * 入栈操作 * @param element 入栈的元素 */ public void push(int element){ mainStack.push(element); //如果辅助栈为空，或者新元素小于等于辅助栈栈顶，则将新元素压入辅助栈 if(minStack.empty()|| element <= minStack.peek()){ //empty() 表示的是测试堆栈是否为空。 //peek() 表示的是查看堆栈顶部的对象，但不从堆栈中移除它。 minStack.push(element); } } /** * 出栈操作 */ public Integer pop(){ //如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈 if(mainStack.peek().equals(minStack.peek())){ minStack.pop(); } return mainStack.pop(); } /** * 获取栈的最小元素 */ public int getMin() throws Exception{ if(mainStack.empty()){ throw new Exception ("stack is empty"); } return minStack.peek(); } public static void main(String[] args) throws Exception { MinStack stack=new MinStack(); stack.push(4); stack.push(9); stack.push(7); stack.push(3); stack.push(8); stack.push(5); System.out.println(stack.getMin()); stack.pop(); stack.pop(); stack.pop(); System.out.println(stack.getMin()); } }
最后
以上就是无语月饼最近收集整理的关于【算法】最小栈的实现(getMin)的全部内容，更多相关【算法】最小栈内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复