具体思路参见:http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
import java.util.ArrayList;
import java.util.List;
public class MinStack {
//maybe we can use origin array rather than ArrayList
private List<Integer> dataStack;
private List<Integer> auxStack;//store the position of MinElement
public static void main(String[] args) {
MinStack minStack=new MinStack();
minStack.push(3);
minStack.printStatus();
minStack.push(4);
minStack.printStatus();
minStack.push(2);
minStack.printStatus();
minStack.push(1);
minStack.printStatus();
minStack.pop();
minStack.printStatus();
minStack.pop();
minStack.printStatus();
minStack.push(0);
minStack.printStatus();
}
public MinStack(){
dataStack=new ArrayList<Integer>();
auxStack=new ArrayList<Integer>();
}
public void push(int item){
if(isEmpty()){
dataStack.add(item);
auxStack.add(0);//position=0
}else{
dataStack.add(item);
int minIndex=auxStack.get(auxStack.size()-1);
int min=dataStack.get(minIndex);
if(min>item){
auxStack.add(dataStack.size()-1);
}else{
auxStack.add(minIndex);
}
}
}
public int pop(){
int top=-1;
if(isEmpty()){
System.out.println("no element,no pop");
}else{
auxStack.remove(auxStack.size()-1);
top=dataStack.remove(dataStack.size()-1);
}
return top;
}
public int min(){
int min=-1;
if(!isEmpty()){
int minIndex=auxStack.get(auxStack.size()-1);
min=dataStack.get(minIndex);
}
return min;
}
public boolean isEmpty(){
return dataStack.size()==0;
}
public void printStatus(){
System.out.println("数据栈 辅助栈 最小值");
for(int i=0;i<dataStack.size();i++){
System.out.print(dataStack.get(i)+",");
}
System.out.print(" ");
for(int i=0;i<dataStack.size();i++){
System.out.print(auxStack.get(i)+",");
}
System.out.print(" ");
System.out.print(this.min());
System.out.println();
}
/*
步骤 数据栈 辅助栈 最小值
1.push 3 3 0 3
2.push 4 3,4 0,0 3
3.push 2 3,4,2 0,0,2 2
4.push 1 3,4,2,1 0,0,2,3 1
5.pop 3,4,2 0,0,2 2
6.pop 3,4 0,0 3
7.push 0 3,4,0 0,0,2 0
*/
}
分享到:
相关推荐
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
30. 包含 min 函数的栈题目链接牛客网题目描述实现一个包含 min() 函数的栈,该方法返回当前栈中最小的值。在对栈进行 push 入栈和 pop 出栈操
java基础面试题包含min函数的栈本资源系百度网盘分享地址
面试题30:包含min函数的栈题目定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。方法准备一个辅助栈,每次都把最小的元素(之前的最小元素
包含min函数的栈.22.判断一个栈是否是另一个栈的弹出序列23.层序遍历二叉树。24.后序遍历二叉搜索树。25.二叉树中和为某值的路径.26.复杂链表的复制27.二叉搜索树转换为双向链表.28.打印字符串中所有字符的排列29....
narrowingConversion_2.java 缩减转换引发错误示例2 notMultipleOfThree.java 把100-200之间不能被3整除的数输出 outputByDoWhile.java 用while循环随机输出数据 outputByWhile.java 用do~while循环随机输出数据...
包含min的最小栈题目描述定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的 min 函数。public void push(int num) {pub
2.设计包含min函数的栈(栈) 定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 3.求子数组的最大和(数组) 题目: 输入一个整形数组,数组里有...
1*2=2 2*2=4 1*3=3 2*3=6 3*3=9 1*4=4 2*4=8 3*4=12 4*4=16 1*5=5 2*5=10 3*5=15 4*5=20 5*5=25 1*6=6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36 1*7=7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49 1*8=8 2*8=16 3*8=24 4...
A.0次 B.1次 C.2次 D.3次 24. 定义类头时,不可能用到的关键字是( )。 A) private B)class C)extends D)implements 25.在一个应用程序中有如下定义:int a[]={1,2,3,4,5,6,7,8,9,10};,为了打印输出数组a的最后一个...
包含min函数的栈(The_stack_containing_the_min_function.java) 队列的最大值(The_maximum_value_of_the_queue.java) 堆(heap_items) 最小的k个数(The_smallest_k_number.java) 位运算(bit_...
设计包含最小函数min(),取出元素函数pop(),加入元素函数push()的栈MinStack,实现其中指定的方法(2)。 MinStack中数据存储使用Java原生的Stack,存储数据元素为int。请实现以下对应的方法,完善功能。 ...
第二十一题 包含min函数的栈 测试21 第二十二题 判断一个栈是否是另一个栈的弹出序列 测试22 第三十三题 层序遍历二叉树 测试23 第二十四题 后序遍历二叉搜索树 测试24 第二十五题 二叉树中和为某值的路径
本书是第II卷,以开发人员在项目开发中经常遇到的问题和必须掌握的技术为中心,介绍了应用Java进行桌面程序开发各个方面的知识和技巧,主要包括Java语法与面向对象技术、Java高级应用、窗体与控件应用、文件操作...
20、包含min函数的栈 21、栈的压入、弹出序列 22、从上到下打印二叉树 23、二叉搜索树的后序遍历 24、二叉树中和为某一值的路径 25、复杂链表的复制 26、二叉搜索树与双向链表 27、字符串的排列 28、数组中出现超过...
栈-队列 相关代码 # Title 020 071 094 155 包含 min 函数的栈 224 简单的计算器 225 使用队列实现栈 232 使用栈实现队列 946 合法的出栈序列 堆 相关代码 # Title 215 数组中第 k 大的数 264 295 ★★★ 寻找中位数...
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...