能够动态调整数组大小的下压栈 Java实现

背景

参考《算法 第四版》用Java实现一份泛型的可迭代的Stack API，这是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。

优缺点

优点

• 每项操作的用时都与集合大小无关；
• 空间需求总是不超过集合大小乘以一个常数。

缺点

缺点在于某些push()和pop()操作会调整数组的大小：这项操作的耗时和栈大小成正比。

Java实现

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterator<Item> {
	private Item[] a = (Item[]) new Object[1];		// 栈元素
	private int N = 0;		// 元素数量

	public boolean isEmpty() {
		return N == 0;
	}

	public int size() {
		return N;
	}

	private void resize(int max) {		// 将栈移动到一个大小为max的新数组
		Item[] temp = (Item[]) new Object[max];

		for(int i = 0; i < N; i++) {
			temp[i] = a[i];
		}

		a = temp;
	}

	public void push(Item item) {		//将元素添加到栈顶
		if(N == a.length) {
			resize(2 * a.length);
		}

		a[N++] = item;
	}

	public Item pop() {		//从栈顶删除元素
		Item item = a[--N];
		a[N] = null;	//避免对象游离

		if(N > 0 && N == a.length/4) {
			resize(a.length/2);
		}

		return item;
	}

	public Iterator<Item> Iterator() {
		return new ResizingArrayIterator();
	}

	private class ResizingArrayIterator implements Iterator<Item> {		//支持后进先出的迭代
		private int i = N;

		public boolean hasNext() {
			return i > 0;
		}

		public Item next() {
			return a[--i];
		}

		public void remove() {
			// nothing
		}
	}
}