《程序员代码面试指南》第一章 栈和队列 设计一个有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(){
//如果数据栈中已空,则 返回 -1
if(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()+" ");
}
}
}
上一篇:python操作三大主流数据库(1)python操作mysql①windows环境中安装python操作mysql数据库的MySQLdb模块mysql-client


下一篇:spring中操作mysql数据库