【从浅到深的算法技巧】集合类数据类型的实现

2.9 集合类数据类型的实现

2.9.1 定容栈

作为热身，我们先来看一种表示容量固定的字符串栈的抽象数据类型，它的API和Stack的API有所不同:它只能处理String值，它要求用例指定一个容量且不支持迭代。

对于FixedCapacityStackofStrings,我们显然可以选择String数组。它的实例变量为一个用于保存栈中的元素的数组a[],和一个用于保存栈中的元素数量的整数N。要删除一个元素， 我们将N减1并返回a[N]。要添加个元素，我们将a[N]设为新元素并将N加1。这些操作能够保证以下性质:

一种表示定容 字符串栈的抽象数据类型

public class FixedCapacityStackofStrings
FixedCapacityStackofStrings(int cap)	创建一个容量为cap的空栈
void push(String item)	添加一个字符串
String pop()	删除最近添加的字符串
boolean isEmpty()	栈是否为空
int size()	栈中的字符串数量

测试用例

public static void main(String[] args){
	FixedCapacityStackofStrings s;
	s = newFixedCapacityStackofStrings(100);
	while (!StdIn.isEmpty()){
		String item = StdIn. readString();
		if Clitem. equals("-")){
			s.push(item);
		}else if (!s.isEmpty()){
			System.out.println(s.pop() +" ");
		} else{
			System.out.println("(" + s.size() +" left on stack)");
		}
	}

数据类型的实现

public class FixedCapacityStackofStrings{
	private String[] a; // stack entries
	private int N;//size
	public FixedCapacityStackOfStrings(int cap){
		a= new String[cap];
	}
	pubic boolean isEmpty(){ 
		return N == 0; 
	}
	public void push(String item){
		a[N++]=item;
	}
	public String pop(){
		return a[--N];
	} 
}

1.数组中的元素顺序和它们被插入的顺序相同;

2.当N为0时栈为空;

3.栈的顶部位于a[N-1] (如果栈为空)。

测试用例会从标准输人读取多个字符串并将它们压入一个栈，当遇到-时它会将栈的内容弹出并打印结果。这种实现的主要性能特点是push和pop操作所需的时间独立于栈的长度。许多应用会因为这种简洁性而选择它。

2.9.2 泛型

FixedCapaci tyStackOfStrings的第一个缺点是它只能处理String对象。如果需要一个double值的栈，你就需要用类似的代码实现另一个类，也就是把所有的String都替换为double。这还算简单，但如果我们需要Transaction类型的栈或者Date类型的队列等，情况就很棘手了。而Java 的参数类型(泛型)就是专门用来解决这个问题的。但如何才能实现一个泛型的栈呢?我们实现了一个FixedCapacityStack类，该类和FixedCapacityStackofStrings类的区别仅在于加粗部分的代码我们把所有的String都替换为Item并用下面这行代码声明了该类:

public class FixedCapacityStack

Item是一个类型参数，用于表示用例将会使用的某种具体类型的象征性的占位符。可以将FixedCapacityStack理解为某种元素的栈。在实现FixedCapacityStack时，我们并不知道Item的实际类型，但用例只要能在创建栈时提供具体的数据类型，它就能用栈处理任意数据类型。实际的类型必须是引用类型，但用例可以依靠自动装箱将原始数据类型转换为相应的封装类型。Java会使用类型参数Item来检查类型不匹配的错误——具体的数据类型还不知道，赋予Item类型变量的值也必须是Item类型的。在这里有一个细节非常重要:我们希望用以下代码在FixedCapacityStack的构造函数的实现中创建一个泛型的数组:

a = new Item[cap];

创建泛型数组在Java中是不允许的。我们需要使用类型转换:

a = (Item[]) new object[cap];

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

public class FixedCapacityStack
FixedCapacityStack(int cap)	创建一个容量为cap的空栈
id push(Item item)	添加一个字符串
Item pop()	删除最近添加的字符串
boolean isEmpty()	栈是否为空
int size()	栈中的元素数量

测试用例

public static void main(String[] args){

FixedCapacityStackofStrings s;
s = newFixedCapacityStackofStrings(100);
while (!StdIn.isEmpty()){
	String item = StdIn. readString();
	if Clitem. equals("-")){
		s.push(item);
	}else if (!s.isEmpty()){
		System.out.println(s.pop() +" ");
			} else{
		System.out.println("(" + s.size() +" left on stack)");
	}
}

数据类型的实现

public class FixedCapacityStackofStrings{
private String[] a; // stack entries
private int N;//size
public FixedCapacityStackOfStrings(int cap){
	a= new String[cap];
}
pubic boolean isEmpty(){ 
	return N == 0; 
}
public void push(String item){
	a[N++]=item;
}
public String pop(){
	return a[--N];
} 

2.9.3 调整数组大小

选择用数组表示栈内容意味着用例必须预先估计栈的最大容量。在Java中:数组一旦创建，其大小是无法改变的，因此栈使用的空间只能是这个最大容量的部分。选择大容量的用例在栈为空或几乎为空时会浪费大量的内存。另一方面，如果集合变得比数组更大那么用例有可能溢出。为此，push()方法需要在代码中检测栈是否已满，我们的API中含有一个isFull()方法来允许用例检测栈是否已满。因此，我们修改了数组的实现，动态调整数组a[]的大小，使得它既足以保存所有元素，又不至于浪费过多的空间。实际上，完成这些目标非常简单。首先，实现一个方法将栈移动到另一个大小不同的数组中:

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

现在，在push()中，检查数组是否太小。具体来说，我们会通过检查栈大小N和数组大小a.length是否相等来检查数组是否能够容纳新的元素。如果没有多余的空间，我们会将数组的长度加倍。然后就可以和从前一样用a[N++] = item 插入新元素:

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

类似，在pop()中，首先删除栈顶的元素，然后如果数组太大我们就将它的长度减半。在数组长度被减半之后，它的状态约为半满，在下次需要改变数组大小之前仍然能够进行多次push()和pop()操作。

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

在这个实现中，栈永远不会溢出，使用率也永远不会低于四分之一( 除非栈为空，那种情况下数组的大小为1)。

2.9.4 对象游离

Java 的垃圾收集策略是回收所有无法被访问的对象的内存。在我们对pop()的实现中，被弹出的元素的引用仍然存在于数组中。这个元素实际上已经是一个孤儿了——它永远也不会再被访问了，但Java的垃圾收集器没法知道这一一点， 除非该引用被覆盖。即使用例已经不再需要这个元素了，数组中的引用仍然可以让它继续存在。这种情况(保存一个不需要的对象的引用)称为游离。在这里，避免对象游离很容易，只需将被弹出的数组元素的值设为null即可，这将覆盖无用的引用并使系统可以在用例使用完被弹出的元素后回收它的内存。

2.9.5 迭代

集合类数据类型的基本操作之一就是，能够使用Java的foreach语句通过选代遍历并处理集合中的每个元素。这种方式的代码既清晰又简洁，且不依赖于集合数据类型的具体实现。在讨论迭代的实现之前，我们先看段能够打印出一个字符串集合中的所有元素的用例:

Stack collection = new Stack();
for (String s : collection){
   System.out.println(s);
}

这里，foreach 语句只是while语句的一种简写方式(就好像for语句一样)。它本质上和以下while语句是等价的:

Iterator = collection. iterator();
while(i.hasNext()){
   String s = i.next();
   System.out.println(s);
}

这段代码展示了一些在任意可迭代的集合数据类型中我们都需要实现的东西:

1.集合数据类型必须实现一个iterator()方法并返回一个Iterator对象;

2.Iterator类必须包含两个方法: hasNext( (返回一个布尔值)和next() (返回集合中的一个泛型元素)。

在Java中，我们使用接口机制来指定一个类所必须实现的方法。对于可迭代的集合数据类型，Java已经为我们定义了所需的接口。要使一个类可迭代，第一步就是在它的声明中加入 implements Iterable, 对应的接口( 即java.lang.Iterable )为:

public interface {
    IteratorcTtem iterator();
}

然后在类中添加一个方法iterator()并返回一个迭代器Iterator。迭代器都是泛型的，因此我们可以使用参数类型Item来帮助用例遍历它们指定的任意类型的对象。对于一直使用的数组表示法，我们需要逆序迭代遍历这个数组，因此我们将迭代器命名为ReverseArrayIterator,并添加了以下方法:

public Iterator iterator(){
     return new ReverseArrayIterator();
}

迭代器是什么? 它是一个实现了hasNext()和next()方法的类的对象，由以下接口所定义(即javatil.terator :

public interface Iterator{
     boolean hasNext();
     Item next():
     void remove();
}

尽管接口指定了一个remove()方法，但remove()方法总为空，因为我们希望避免在迭代中穿插能够修改数据结构的操作。对于ReverseArrayIterator,这些方法都只需要一行代码，它们实现在栈类的一个嵌套类中:

private class ReversearrayIterator implements Iterator{
    private int i =N;
    public boolean hasNext() { return i > 0; }
    public Item next()  { return a[--i]; }
    public void remove()  {     }
}

请注意，嵌套类可以访问包含它的类的实例变量，在这里就是a[]和N (这也是我们使用嵌套类实现迭代器的主要原因)。从技术角度来说，为了和Iterator的结构保持一致， 我们应该在两种情况下抛出异常:如果用例调用remove()则抛出UnsupportedOperationException,如果用例在调用next(时i为0则抛NoSuchElementException。因为我们只会在foreach语法中使用迭代器，这些情况都不会出现，所以我们省略了这部分代码。还剩下一个非常 重要的细节，我们需要在程序的开头加上下面这条语句:

import java.util.Iterator;

现在，使用foreach处理该类的用例能够得到的行为和使用普通的for循环访问数组一样，但它无知道数据的表示方法是数组(即实现细节)。例如，我们无需改变任何用例代码就可以随意切换不同的表示方法。更重要的是，从用例的角度来来说，无需知晓类的实现细节用例也能使用迭代。

上述算法是Stack API的一种能够动态改变数组大小的实现。用例能够创建任意类型数据的栈，并支持用例用foreach语句按照后进先出的顺序迭代访问所有栈元素。

例如，我们在实现Queue的API时，可以使用两个实例变量作为索引, 一个变量head指向队列的开头，一个变量tail指向队列的结尾，在删除一个元素时， 使用head访问它并将head加1;在插入一个元素时，使用tail保存它并将tail加1。如果某个索引在增加之后越过了数组的边界则将它重置为0。实现检查队列是否为空、是否充满并需要调整数组大小的细节也是很重要的。

ResizingArrayQueue 的缺点在于某些pushO和popO操作会调整数组的大小:这项操作的数据。耗时和栈大小成正比。下面， 有一种克服该缺陷的方法， 使用一种完全不同的方式来组织算法下压(LIFO) 栈(能够动态调整数组大小的实现)

import java. util.Iterator;
public class ResizingArrayStack implements Iterable{
	private Item[] a = (Item[]) new Object[1];  //栈元素
	private int N = 0;  //元素数量
	public boolean isEmpty() { returnN = 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);
		public Item pop(){
			Item item = a[--N];
		}
		pubric string pop(){
			//从栈顶删除元素
			String item = a[--N];
			a[NJ = null; //避免对象游离
			if (N> 0 && N = a.length/4) resize(a. length/2);
			return item;
		}
		private class ReverseArrayIterator implements Iterator{
			//支持后进先出的选代
			private int i = N;
			public boolean hasNext() { return i > 0;  }
			public Item next()  { return a[--i]; }
			public void remove()  {     }
		} 
}

保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。