容器(Container)在生活中处处可见。每种容器的类型都有各自定制、访问实体的一系列规则。
区别容器对象本身和该容器包含的对象是很重要的。从某种意义上说，研究数据结构也就是研究容器。这里，将给出容器这种抽象数据类型的行为框架，并且创建实现这种抽象数据类型的基本原型。根据一下的特性可以区别不同类型的容器：
（1）容器中的对象是否可排序。比如：按容器的一个继承属性排序，或按容器中的对象的一个属性排序。
（2）是否允许对象的复制（是否允许重复）。
（3）容器中的对象可被限制为一个特定的类型。
（4）容器中的对象可基于索引来访问。
（5）容器中的对象可基于相对位置来访问。
（6）容器中的对象可基于值访问。
（7）容器可根据其连通性（线性、非线性）来区别。
这里以Container接口为根接口来表示所有容器最一般的形式。
1.1 顶层的Container接口
在开发新的java类时，我们应该先考虑是否需要可串行化。一个可串行化的对象可以很容易的从作为对象的文件流中来读/写的。最一般的容器具有一下特性：
1）不考虑它所包含的对象的类型；
2）所包含的对象没有排序的要求；
3）接受复制的对象；
4）支持可串行化；
5）接受使本身为空的命令；
6）接受一下查询：返回所包含的对象的个数、返回容器是否为空。
我们所定义的Container接口如下：
/** Interface Container - top level container*/
package foundations;
import java.io.serializable;
public interface Container extends Serializable {
// Commands - see subinferfaces
/** Remove all objects from the container if found
*/
public void makeEmpty ();
//Queries
/** Return true if the container is empty
*/
public boolean isEmpty();
/** Return the number of objects in the container
*/
public int size();
}
1.2 最简单的容器－－堆栈和队列
这里定义最简单的容器：堆栈（Stack）和队列（Queue）
堆栈使一个容器，并具有以下特性：
1) 堆栈是有次序的，这也是堆栈的一个属性，与堆栈所包含的对象无关。堆栈中对象的次序依赖于其插入、删除的顺序。后进先出。
2）对堆栈的操作只能在一个名为top的位置上。用Push方法在堆栈顶部增加新的对象,用pop方法删除堆栈顶部的对象，用top方法查询堆栈顶部的对象。
3）用MakeEmpty方法可以清除堆栈的对象，也可用isEmpty来查询该堆栈是否为空，以及查询堆栈的大小（size()）。
接口Stack是对Container的扩展，因此它继承了Container所有的方法，并增加了新的方法:push、pop、以及查询顶部对象的方法。
/** Interface Stack - a first-in last-out container
*/
package foundations;
public interface Stack extends Container {
//Commands
/** Add an object onto the top of the stack
*/
public void push(object obj);
/** Remove an object form the top of the stack
* Throw NoSuchElementException if stack is empty
*/
public void pop();
//Queries
/** Return without removing, the top object on the stack
* Throw NoSuchElementException if stack is empty
*/
public object top();
}
队列也是一个容器，并具有以下特性：
1）队列有次序，这也是它的一个属性，与队列所包含的对象无关。队列中对象的次序依赖于其插入、删除的顺序。队列中的次序关系的主要特点是先进先出。
2）对队列的操作限制在两个位置上，即front（对头）、rear（队尾）。我们可以在尾部增加对象，在头部删除对象，或查询头部的对象。
3）可以用MakeEmpty方法可以清除队列的对象，也可用isEmpty来查询该队列是否为空，以及查询队列的大小（size()）。
接口Queue是对Container的扩展，因此它继承了Container所有的方法，并增加了新的方法:add、remove、以及查询头部对象的方法。
/** Interface Queue
*/
public interface Queue extends Container {
//Commands
/** Add an object at the rear of the queue
*/
public void add(Object obj);
/** Remove an object from the front of the queue
* Throws NoSuchElementException if queue is empty
*/
public void remove();
//Queries
/** Return without removing, the front object in the queue
* Throws NoSuchElementException if queue is empty
*/
public object front();
}
1.3 辅助性接口和类－－Comparable（可比性）和Association（关联性）
有序容器包含了一些对象，这些对象在容器中的位置（或次序）是根据它的某个属性的重要性来决定的，更确切的说，有序容器中的对象是可比较的，这个属性可以通过要求对象类来实现Comparable接口来获得。Comparable接口包含唯一一个查询方法CompareTo。
查询CompareTo返回一个整数值。
/** Interface Comparable
*/
public Interface Comparable {
//Queries
/** Return -1 if the receiver is less than obj,
* 0 if the receiver equals obj and
* 1 if the receiver is greater than obj
*/
public int compareTo (Object obj);
}
类Association允许将值和键(Key)组合起来，即在键和其值之间有一个关联。类Association在研究一个需要键－值（key－value）对的容器数据结构时起到什么重要的作用。
在字典类容器中就包含Association类的实例，字典是由键组成的，也就是说，我们查找字典中的对象时，只是查找它的键。如果字典按某种顺序（根据所包含的键的相对大小）排列的，那么我们必须保证任何输入到OrderdDictionary（有序字典）中的关联对的键也是可以比较的（Comparable）。同时，我们要求关联也必须是可串行化的，这样才能保证前面所提到的所有容器都要求是可串行化的。Association是一个类，而不是接口。
/** Class Assocation
* An instance must initialize a key on creation.
* If used as a comparable Assocation,keys must be comparable and comparions is based on keys only.
* Note that equals() does not enforce the comparable feature and requires equality of both key and value.
*/
package foundations;
import java.io.serializable;
public class Association extends Object implements Comparable,Serializable {
//Fields
private Object key;
private Object value;
/** Create an instance with specified key and null value
*/
public Assocation (Object key) {
this(key,null);
}
/** Create an instance with specified key and value
*/
public Association(Object key,Object value) {
this.key=key;
this.value=value;
}
/** Set the value
*/
public void setValue(Object value) {
this.value = value;
}
/** return key
*/
public Object key() {
return key;
}
/** return value
*/
public Object value() {
return value;
}
/**Return a string representation.
* Return a String of the form <key:value>
*/
public String toString() {
return "<"+key+":"+value+">";
}
/** Override inherited object method equals()
*/
public boolean equals (Object obj) {
if(obj instanceof Assocation)]
return (key.equals((Assocation)obj).key) && value.equals((Assocation)obj).value));
else return false;
}
/**Implement Comparable method compareTo
* Compare based only on key; key must be comparable
*/
public int compareTo (Object obj) {
return ((Comparable)key).compareTo((Association)obj.key());
}
/** Override inherited Object method hashCode().
*Return a unique int representing this object
*/
public int hashCode () {
int bits1 = key.hashCode();
int bits2 = value.hashCode();
return (bits1 <<8)^(bits2>>8);
}
}
未完，待续....