下面介绍背包、队列和栈（基于数组）的实现，是对《算法（第四版）》1.3 节的部分总结。

API 是开发的起点，所以先给出 API：

表 1 泛型可迭代的基础集合数据类型的 API

总的思路是先给出一个简单而经典的实现，然后讨论它的改进并得到表 1 中的 API 的所有实现。

定容栈

从简单的开始，我们先实现一种表示容量固定的字符串栈的抽象数据类型，如表 2 所示。

它的 API 和 Stack 的 API 有所不同：它只能处理 String 值，它要求用例指定一个容量且不支持迭代。实现一份 API 的第一步就是选择数据的表示方式。对于 FixedCapacityStackOfStrings，我们显然可以选择 String 数组。由此我们可以得到表 2 中底部的实现。

表 2 一种表示定容字符串栈的抽象数据类型 表 3 FixedCapacityStackOfStrings 的测试用例的轨迹

这种实现的主要性能特点是 push 和 pop 操作所需的时间独立于栈的长度。许多应用会因为这种简洁性而选择它。但几个缺点限制了它作为通用工具的潜力，下面尝试改进它。

泛型定容栈

FixedCapacityStackOfStrings 的第一个缺点是它只能处理 String 对象。对此，我们可在代码中引入泛型（有关泛型的介绍见简单了解一下 Java 泛型）。表 4 中的代码展示了实现的细节。

表 4 一种表示泛型定容栈的抽象数据类型

调整数组大小

在 Java 中，数组一旦创建，其大小是无法改变的，因此栈使用的空间只能是这个最大容量的一部分。创建大容量的栈在栈为空或几乎为空时会浪费大量的内存。而小容量的栈可能不满足保存大量数据的要求。

所以 FixedCapacityStack 最好能够支持动态调整数组大小，使得它既足以保存所有元素，又不至于浪费过多的空间。

为此，我们可以添加一个 resize(int) 方法。

private void resize(int max)
{	// 将大小为 N < = max 的栈移动到一个新的大小为 max 的数组中
	Item[] temp = (Item[]) new Object[max];
	for (int i = 0; i < N; i++)
		temp[i] = a[i];
	a = temp;
}

然后在 push() 中，检查数组是否太小，太小时增大数组长度。

public void push(Item item)
{	// 将元素压入栈顶
	if (N == a.length) resize(2*a.length);
	a[N++] = item;
}

类似地，在 pop() 中，首先删除栈顶的元素，之后如果数组太大我们就将它的长度减半。

public Item pop()
{	// 从栈顶删除元素
	Item item = a[--N];
	a[N] = null;  // 避免对象游离
	if (N > 0 && N == a.length/4) resize(a.length/2);
	return item;
}

push() 和 pop() 操作中数组大小调整的轨迹见表 5。

表 5 一系列 push() 和 pop() 操作中数组大小调整的轨迹

迭代

集合类数据类型的基本操作之一就是，能够使用 Java 的 foreach 语句通过迭代遍历并处理集合中的每个元素。有关在代码中加入迭代的方法见 Java 可迭代的数据类型。

栈的实现

有了前面的准备，我们能够写出下压栈能动态调整数组大小的实现。

栈的实现（基于数组）

import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<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;  // 避免对象游离（请见 1.3.2.4 节）
		if (N > 0 && N == a.length/4) resize(a.length/2);
		return item;
	}
	public Iterator<Item> iterator()
	{  return new ReverseArrayIterator();  }
	private class ReverseArrayIterator implements Iterator<Item>
	{	// 支持后进先出的迭代
		private int i = N;
		public boolean hasNext() {  return i > 0;    }
		public    Item next()    {  return a[--i];   }
		public    void remove()  {                   }
	}
}

背包和队列的实现

受上述栈的实现过程的启发，我们可以类似写出背包和队列的实现。

对于背包，将栈实现中的 push(Item) 方法的方法名改为 add 并删除添加元素的方法即可。

背包的实现（基于数组）

import java.util.Iterator;
public class ResizingArrayBag<Item> implements Iterable<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 add(Item item)
	{	// 将元素添加到背包
		if (N == a.length) resize(2*a.length);
		a[N++] = item;
	}
	public Iterator<Item> iterator()
	{  return new ReverseArrayIterator();  }
	private class ReverseArrayIterator implements Iterator<Item>
	{	// 支持后进先出的迭代
		private int i = N;
		public boolean hasNext() {  return i > 0;    }
		public    Item next()    {  return a[--i];   }
		public    void remove()  {                   }
	}
}

对于队列，可以使用两个实例变量作为索引，一个变量 head 指向队列的开头，一个变量 tail 指向队列的结尾，如表 6 所示。在删除一个元素时，使用 head 访问它并将 head 加 1；在插入一个元素时，使用 tail 保存它并将 tail 加 1。如果某个索引在增加之后越过了数组的边界则将它重置为 0。

表 6 ResizingArrayQueue 的测试用例的轨迹

下面是 ResizingArrayQueue 的实现。

队列的实现（基于数组）

import java.util.Iterator;
public class ResizingArrayQueue<Item> implements Iterable<Item> {
	private static final int INIT_CAPACITY = 8;
	private Item[] a = (Item[]) new Object[INIT_CAPACITY];
	private int N = 0;
	private int head = 0;
	private int tail = 0;
	public boolean isEmpty() { return N == 0; }
	public int size() { return N; }
	private void resize(int max) {
		Item[] temp = (Item[]) new Object[max];
		for (int i = 0; i < N; i++) temp[i] = a[(head + i) % a.length];
		a = temp;
		head = 0;
		tail = N;
	}
	public void enqueue(Item item) {
		if (N == a.length) resize(2 * a.length);
		a[tail++] = item;
		if (tail == a.length) tail = 0;
		N++;
	}
	public Item dequeue() {
		Item item = a[head];
		a[head++] = null;
		if (head == a.length) head = 0;
		N--;
		if (N > 0 && N == a.length / 4) resize(a.length / 2);
		return item;
	}
	public Iterator<Item> iterator() {
		return new ResizingArrayQueueIterator();
	}
	private class ResizingArrayQueueIterator
			implements Iterator<Item> {
		private int i = 0;
		public boolean hasNext() { return i < N; }
		public Item next() {
			Item item = a[(i + head) % a.length];
			i++;
			return item;
		}
	}
}