《程序员代码面试指南》第一章 栈和队列 设计一个有getMin功能的栈

题目

实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中最小的元素的操作

要求

1.  pop、push、getMin操作时间复杂度都是O(1)
2.  设计的栈类型可以使用现成的栈结构

java代码

/*** @Description:设计一个有getMin功能的栈* @Author: lizhouwei* @CreateDate: 2018/4/5 9:54* @Modify by:* @ModifyDate:
*/
public class Chapter1_1 {private Stack<Integer> stackData;//数据栈，压栈的数据private Stack<Integer> stackMin;//辅助栈，从栈顶到栈底 由小到大有序的数据public Chapter1_1(){stackData = new Stack<Integer>(); //在new的时候 初始化stackData内存空间stackMin = new Stack<Integer>(); //在new的时候 初始化stackMin内存空间}//压入栈中public void push(int value){//将数据压入栈中stackData.push(value);//如果辅助栈是空的则直接压入if(stackMin.isEmpty()){stackMin.push(value);}else if(value<stackMin.peek()){//value比栈顶元素小stackMin.push(value);}}//弹栈public int pop(){//如果数据栈中已空,则 返回 -1if(stackData.isEmpty()){return -1;}//数据栈弹出int value =  stackData.pop();if(value ==stackMin.peek()){stackMin.pop();}return value;}//获取最小值public int getMin(){//获取辅助栈顶元素即可return stackMin.peek();}//测试public static void main(String[] args){Chapter1_1 chapter = new Chapter1_1();for(int i=10,j=11;i<20;i=i+2,j=j+10) {chapter.push(j);chapter.push(i);}System.out.println(chapter.getMin());while(!chapter.stackData.isEmpty()){System.out.print(chapter.stackData.pop()+" ");}}
}