定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
感谢csdn July整理题目和答案http://blog.csdn.net/v_JULY_v/article/details/6057286
这里我写的第二题的java 代码实现。
实现原理
入栈时,比较辅助栈栈顶元素大小,如果新增元素小于等于辅助栈栈顶元素,辅助栈同时入栈。出栈时,如果出栈元素等于辅助栈栈顶元素(即出栈元素为最小值),辅助栈同时出栈
例如压栈 5,2,2,1,6,3
栈 辅助栈
5 5
2 2
2 2
1 1
6
3
出栈时
3 1
6 1
1 2
2 2
2 5
5 null
一、定义节点类,添加了遍历和添加方法,在本题目中使用不到
package cn.edu.cqupt.mircrosoft100;
public class Node {
private Integer value;
private Node next;
public Node(int value)
{
this.value=value;
}
public Node()
{
}
public void add(int value)
{
if(null==this.value)
{
this.value=value;
return;
}
if(null==next)
next=new Node();
next.add(value);
}
public void list()
{
if(null!=value)
System.out.println(value);
if(null==next)
return;
next.list();
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
二、辅助栈的实现
package cn.edu.cqupt.mircrosoft100;
public class AssistStack {
private Node top;
public void push(int value)
{
Node add= new Node(value);
if(null==top)
{
top=add;
return;
}
add.setNext(top);
top=add;
}
public Integer pop()
{
if(null==top)
return null;
Integer temp = top.getValue();
top=top.getNext();
return temp;
}
public Node getTop() {
return top;
}
public void setTop(Node top) {
this.top = top;
}
}
三、实现最小栈
package cn.edu.cqupt.mircrosoft100;
public class MinStack {
private AssistStack assistStack=new AssistStack();//辅助栈,实现O(1)min函数
private Node top;
public void push(int value)
{
Node add = new Node(value);
if(null==top)
{
top=add;
assistStack.push(value);
return;
}
add.setNext(top);
top=add;
refresh();
}
public void refresh()
{
int temp = top.getValue();
if(temp<=assistStack.getTop().getValue())
assistStack.push(temp);
}
public Integer pop()
{
Integer temp = top.getValue();
if(null==temp)
return null;
if(temp==assistStack.getTop().getValue())
assistStack.pop();
top=top.getNext();
return temp;
}
public Integer getMin()
{
if(null==assistStack.getTop())
return null;
return assistStack.getTop().getValue();
}
public static void main(String args[])
{
MinStack minStack =new MinStack();
minStack.push(5);
minStack.push(2);
minStack.push(3);
minStack.push(3);
minStack.push(6);
System.out.println("min:"+minStack.getMin());
System.out.println("pop:"+minStack.pop());
System.out.println("min:"+minStack.getMin());
System.out.println("pop:"+minStack.pop());
System.out.println("min:"+minStack.getMin());
System.out.println("pop:"+minStack.pop());
System.out.println("min:"+minStack.getMin());
System.out.println("pop:"+minStack.pop());
System.out.println("min:"+minStack.getMin());
System.out.println("pop:"+minStack.pop());
System.out.println("min:"+minStack.getMin());
}
}
分享到:
相关推荐
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
constructWithPara.java 带参数的构造方法 declareDefault.java 缺省访问权限的使用 declarePrivate.java 私有访问权限的使用 declareProtected.java 保护访问权限的使用 deriveClass.java 子类访问父类变量...
30. 包含 min 函数的栈题目链接牛客网题目描述实现一个包含 min() 函数的栈,该方法返回当前栈中最小的值。在对栈进行 push 入栈和 pop 出栈操
面试题30:包含min函数的栈题目定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。方法准备一个辅助栈,每次都把最小的元素(之前的最小元素
包含min的最小栈题目描述定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的 min 函数。public void push(int num) {pub
Get Min value of Stack
Java面试 Java超级经典100问题 Java高级开发工程师必备 Java面试宝典 1.赋值运算函数.2.单例设计模式.3.二维数组中查找目标值、4.替换字符串中的空格。5.从尾到头打印链表.6.由前序和中序遍历重建二叉树.7.用两个栈...
第七题 使用两个栈实现队列 测试7 第八题 寻求旋转带宽的最小数字 测试8 第九题 斐波那契数列的第n项(青蛙跳台阶) 测试9 第十题 二进制中1的个数 测试10 第十一题 数值的整数次方 测试11 第十二题 打印1到最大的n...
实例133 使用方法实现线程同步 172 实例134 使用代码块实现线程同步 174 实例135 使用特殊域变量实现线程同步 175 实例136 使用重入锁实现线程同步 176 实例137 使用线程局部变量实现线程同步 177 实例138 简单的...
设计包含最小函数min(),取出元素函数pop(),加入元素函数push()的栈MinStack,实现其中指定的方法(2)。 MinStack中数据存储使用Java原生的Stack,存储数据元素为int。请实现以下对应的方法,完善功能。 ...
import java.util.Scanner; class Bissextile{ public static void main(String[] arge){ System.out.print("请输入年份"); int year; //定义输入的年份名字为“year” Scanner scanner = new Scanner(System.in...
包含min函数的栈(The_stack_containing_the_min_function.java) 队列的最大值(The_maximum_value_of_the_queue.java) 堆(heap_items) 最小的k个数(The_smallest_k_number.java) 位运算(bit_...
MinMin's Online OJ 1.项目目标 仿照Leetcode实现一个简单的刷题的项目,用户可以在浏览器访问到题目列表页面,并点击题目进入题目详情页面,并在这里进行代码的编写、编译和运行,并返回结果到浏览器页面 2.项目...
5、用两个栈实现队列 6、旋转数组的最小数字 7、斐波那契数列 8、跳台阶 9、变态跳台阶 10、矩形覆盖 11、二进制中1的个数 12、数值的整数次方 13、调整数组顺序使奇数位于偶数前面 14、链表倒数第k个节点 15、反转...
使用栈实现队列 946 合法的出栈序列 堆 相关代码 # Title 215 数组中第 k 大的数 264 295 ★★★ 寻找中位数 贪心算法 相关代码 # Title 045 跳跃游戏 055 跳跃游戏 376 摇摆序列 402 移除 k 个数字 452 射击气球 ...
3. 下面的java小应用程序实现的功能是从文本域中输入你的名字"***",回车后在 Applet中显示"***,你好!" ,请完成程序。 import java.awt.*; import java.applet.*; import java.awt.event.*; public class Applet1 ...
Java实现 学习笔记 面试题03 数组中重复的数字 面试题04 二维数组中的查找 面试题05 替换空格 面试题06 从尾到头打印链表 面试题07 重建二叉树 面试题09 用两个栈实现队列 面试题10- I 斐波那契数列 面试题10- II ...