2.设计包含min 函数的栈。
定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
/**
*
*/
package com.lhp;
import java.util.EmptyStackException;
import java.util.Stack;
import java.util.Vector;
/**
2.设计包含min 函数的栈。
定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
*/
class GStack<E extends Comparable<E>> extends Vector<E> {
/**
* v0.1
*/
private static final long serialVersionUID = -6719503943136573361L;
private Stack<Integer> minPosStack = new Stack<Integer>(); // 存储最小元素的位置
/**
* 栈的最小元素
* @return 最小元素
*/
public E min() {
return super.get(this.minPosStack.peek());
}
/**
* 入栈
* @param 元素
*/
public synchronized void push(E item) {
if (0 == super.size()) {
this.minPosStack.push(0);
} else {
if (item.compareTo(min()) <= 0) {
this.minPosStack.push(super.size());
} else {
this.minPosStack.push(this.minPosStack.peek()); // 维持不变
}
}
super.add(item);
}
/**
* 出栈
* @return 栈顶元素
*/
public synchronized E pop() {
E obj;
if (0 == super.size())
throw new EmptyStackException(); // return null
obj = super.get(super.size() - 1);
super.remove(super.size() - 1);
this.minPosStack.pop();
return obj;
}
public synchronized void print() {
if (0 == super.size()) {
System.out.print("HashCode: " + this.hashCode() + "; 空栈;");
return;
}
System.out.print("HashCode: " + this.hashCode() + "; 栈: ");
for (int i = 0; i < super.size(); i++) {
System.out.print(super.get(i) + " ");
}
System.out.println();
}
}
public class Tow {
public static void main(String[] args) {
GStack<Integer> s1 = new GStack<Integer>();
s1.push(new Integer(3));
s1.push(new Integer(6));
s1.push(new Integer(2));
s1.push(new Integer(1));
s1.push(new Integer(8));
s1.push(new Integer(7));
s1.pop();
s1.pop();
// s1.pop(); // 取消注释即得2
s1.print();
System.out.println("min(): " + s1.min());
}
}
分享到:
相关推荐
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
java基础面试题包含min函数的栈本资源系百度网盘分享地址
30. 包含 min 函数的栈题目链接牛客网题目描述实现一个包含 min() 函数的栈,该方法返回当前栈中最小的值。在对栈进行 push 入栈和 pop 出栈操
面试题30:包含min函数的栈题目定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。方法准备一个辅助栈,每次都把最小的元素(之前的最小元素
包含min的最小栈题目描述定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的 min 函数。public void push(int num) {pub
HelloNative.java 准备调用C函数的java文件 HelloNative.lib 用VC编译生成的静态库文件 HelloNative.obj 用VB编译生成的目标文件 HelloNativeTest.java 测试本地化是否成功的类文件 instanceVar.java 定义一个...
包含min函数的栈.22.判断一个栈是否是另一个栈的弹出序列23.层序遍历二叉树。24.后序遍历二叉搜索树。25.二叉树中和为某值的路径.26.复杂链表的复制27.二叉搜索树转换为双向链表.28.打印字符串中所有字符的排列29....
包含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函数的栈 测试21 第二十二题 判断一个栈是否是另一个栈的弹出序列 测试22 第三十三题 层序遍历二叉树 测试23 第二十四题 后序遍历二叉搜索树 测试24 第二十五题 二叉树中和为某值的路径
2.设计包含min函数的栈(栈) 定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 3.求子数组的最大和(数组) 题目: 输入一个整形数组,数组里有...
设计包含最小函数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...
20、包含min函数的栈 21、栈的压入、弹出序列 22、从上到下打印二叉树 23、二叉搜索树的后序遍历 24、二叉树中和为某一值的路径 25、复杂链表的复制 26、二叉搜索树与双向链表 27、字符串的排列 28、数组中出现超过...
本书是第II卷,以开发人员在项目开发中经常遇到的问题和必须掌握的技术为中心,介绍了应用Java进行桌面程序开发各个方面的知识和技巧,主要包括Java语法与面向对象技术、Java高级应用、窗体与控件应用、文件操作...
函数的栈 224 简单的计算器 225 使用队列实现栈 232 使用栈实现队列 946 合法的出栈序列 堆 相关代码 # Title 215 数组中第 k 大的数 264 295 ★★★ 寻找中位数 贪心算法 相关代码 # Title 045 跳跃游戏 055 跳跃...
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...
21包含min函数的栈 22栈的压入弹出序列 23从上往下打印二叉树 24二叉搜索树的后序遍历序列 25二叉树中和为某一值的路径 26复杂链表的复制 27二叉搜索树与双向链表 28字符串的排列 29数组中出现次数超过一半的数字 30...