希望自己能够继续算法和数据结构知识的练习,这个是之前完成的一个题目,一并贴出来吧。
题目来源仍然和上篇博文一样:http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
文中使用C语言实现,我采用Java实现。
题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
实现思路:们需要一个辅助栈。每次push一个新元素的时候,同时将最小元素(或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构,用最小元素的位置将能减少空间消耗)push到辅助栈中;每次pop一个元素出栈的时候,同时pop辅助栈。
package stack;
import java.util.ArrayList;
/**
* 实现包含min函数的栈
* @author DHC
* @param <T>
*/
public class MinInStack<T> {
public static void main(String[] args) {
MinInStack<Integer> newStack = new MinInStack<Integer>();
newStack.push(4);
newStack.push(6);
newStack.push(2);
newStack.push(5);
newStack.pop();
newStack.pop();
newStack.push(1);
System.out.println(newStack.min());
}
public ArrayList<T> stack = new ArrayList<T>();
public ArrayList<Integer> minStack = new ArrayList<Integer>();
public T pop() {
int size = stack.size();
minStack.remove(size - 1);
return stack.remove(size - 1);
}
public void push(T item) {
int size = stack.size();
if (size == 0) {
minStack.add(0);
} else {
int minPosition = minStack.get(size - 1);
T minData = stack.get(minPosition);
if (compare(minData, item)) {
minStack.add(stack.size());
} else {
minStack.add(minPosition);
}
}
stack.add(item);
}
public T peek() {
int size = stack.size();
return stack.get(size - 1);
}
public T min() {
int size = minStack.size();
return stack.get(minStack.get(size - 1));
}
public boolean isEmpty() {
return stack.isEmpty();
}
/**
* 泛型元素的比较方法
* @param minData
* @param item
* @return true 代表当前元素小于之前的最小元素
*/
private boolean compare(T minData, T item) {
// 这儿不同的泛型类型可以用不同的方式实现
// 如果写成通用代码泛型之间应该肿么比较大小呢?是不是可以让泛型都继承某一接口呢?
int a = (Integer) minData;
int b = (Integer) item;
if(a > b) {
return true;
} else {
return false;
}
}
}
心得:
1、本来打算采用java中linkedList类直接生成数值栈,但是记录最小数值的另外一个栈存储的是数值栈的最小元素坐标,而Linkedlist作为栈时其坐标会变化,因此改用ArrayList实现栈。
2、可以用LinkedList直接生成具有栈行为的数据结构。
3、LinkedList采用的是链表的形式,addFirst和add方式分别插入的链表的头和尾部,与此对应,getFirst和get(list.size() - 1) 分别取得时链表头尾部的元素。
分享到:
相关推荐
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
python 实现 包含min函数的栈
java基础面试题包含min函数的栈本资源系百度网盘分享地址
本文实例讲述了Python实现包含min函数的栈。分享给大家供大家参考,具体如下: # coding=utf8 ''' 题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。 在该栈中,调用min、push及pop的...
包含min函数的栈.md
剑指Offer(Python多种思路实现):包含min函数的栈 面试30题: 题目:包含min函数的栈 题:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中,调用min、push、pop的时间复杂度都是O(1) ...
30. 包含 min 函数的栈题目链接牛客网题目描述实现一个包含 min() 函数的栈,该方法返回当前栈中最小的值。在对栈进行 push 入栈和 pop 出栈操
面试题30. 包含min函数的栈定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复
面试题30:包含min函数的栈题目定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。方法准备一个辅助栈,每次都把最小的元素(之前的最小元素
20 - 包含min函数的栈题目描述定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。# 每次pop操作时需
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。void push(int value) {这是对两个栈进行操作的一个题目,push,po
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
//如果 minval 中为空 则直接放入if(x())//如果 minval 中不为空,此时需要比较新放入元素和原有栈顶元素大小//如
代码type MinStack struct {a []int//存储元素b []int //辅助栈 维护栈的最小值/* initialize your dat
linux内核中的min、max函数1
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push...
是基于java的Min-Min等算法源代码,里面含有一个算法讲解文档,通过一个.exe文件执行,且执行结果将通过一个KMP显示算法执行结果
包含min的最小栈题目描述定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的 min 函数。public void push(int num) {pub
min函数.xls