首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

Java语言兑现包含min函数的栈

2012-09-21 
Java语言实现包含min函数的栈希望自己能够继续算法和数据结构知识的练习,这个是之前完成的一个题目,一并贴

Java语言实现包含min函数的栈

希望自己能够继续算法和数据结构知识的练习,这个是之前完成的一个题目,一并贴出来吧。


题目来源仍然和上篇博文一样: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) 分别取得时链表头尾部的元素。

热点排行