java|设计有一个getMin功能的栈( java )

设计有一个getMin功能的栈 说明
本文来自左程云老师所著的《程序员面试代码指南》第一章
题目
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
要求
1.pop、push、 getMin操作的时间复杂度都是0(1)。
2.设计的栈类型可以使用现成的栈结构。
方法
在设计上使用两个栈,一个栈用来保存当前栈中的元素,其功能和一个正常的栈
没有区别,这个栈记为stackData; 另一个栈用于保存每一步的最小值,这个栈记为stackMin。
举例
stackData存放3 4 5 1 2 1
则stackMin存放3 1 1
代码实现


import java.util.Scanner; public class MyStack { private Stack stackData; private Stack stackMin; public static void main(String[] args) { Scanner cs = new Scanner(System.in); MyStack stack = new MyStack(); System.out.println("输入数据个数:"); int n = cs.nextInt(); for(int i=0; i(); stackMin = new Stack(); } void push(int m) { stackData.push(m); if(stackMin.empty()) stackMin.push(m); else { if(stackMin.peek()>=m) stackMin.push(m); //stackMin栈顶元素大于等于m时加入 } } //此后当有元素出栈时,stackData正常出栈,如若出栈元素等于stackMin的栈顶, //则stackMin栈顶一同出栈,保证实时更新stackMin void pop() { if(stackData.empty()) throw new RuntimeException("Your empty is empty!"); int a = stackData.pop(); if(a == stackMin.peek()) stackMin.pop(); } int getMin() { if(stackData.empty()) throw new RuntimeException("Your empty is empty!"); int a = stackMin.peek(); return a; } }

【java|设计有一个getMin功能的栈( java )】说明:只为记录自己每日学习,加油 ~

    推荐阅读