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) 分别取得时链表头尾部的元素。

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

相关推荐