容器(Container)在生活中處處可見。每種容器的類型都有各自定制、訪問實體的一系列規(guī)則。
區(qū)別容器對象本身和該容器包含的對象是很重要的。從某種意義上說，研究數(shù)據(jù)結(jié)構(gòu)也就是研究容器。這里，將給出容器這種抽象數(shù)據(jù)類型的行為框架，并且創(chuàng)建實現(xiàn)這種抽象數(shù)據(jù)類型的基本原型。根據(jù)一下的特性可以區(qū)別不同類型的容器：
（1）容器中的對象是否可排序。比如：按容器的一個繼承屬性排序，或按容器中的對象的一個屬性排序。
（2）是否允許對象的復(fù)制（是否允許重復(fù)）。
（3）容器中的對象可被限制為一個特定的類型。
（4）容器中的對象可基于索引來訪問。
（5）容器中的對象可基于相對位置來訪問。
（6）容器中的對象可基于值訪問。
（7）容器可根據(jù)其連通性（線性、非線性）來區(qū)別。
這里以Container接口為根接口來表示所有容器最一般的形式。
1.1 頂層的Container接口
在開發(fā)新的java類時，我們應(yīng)該先考慮是否需要可串行化。一個可串行化的對象可以很容易的從作為對象的文件流中來讀/寫的。最一般的容器具有一下特性：
1）不考慮它所包含的對象的類型；
2）所包含的對象沒有排序的要求；
3）接受復(fù)制的對象；
4）支持可串行化；
5）接受使本身為空的命令；
6）接受一下查詢：返回所包含的對象的個數(shù)、返回容器是否為空。
我們所定義的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) 堆棧是有次序的，這也是堆棧的一個屬性，與堆棧所包含的對象無關(guān)。堆棧中對象的次序依賴于其插入、刪除的順序。后進(jìn)先出。
2）對堆棧的操作只能在一個名為top的位置上。用Push方法在堆棧頂部增加新的對象,用pop方法刪除堆棧頂部的對象，用top方法查詢堆棧頂部的對象。
3）用MakeEmpty方法可以清除堆棧的對象，也可用isEmpty來查詢該堆棧是否為空，以及查詢堆棧的大小（size()）。
接口Stack是對Container的擴(kuò)展，因此它繼承了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）隊列有次序，這也是它的一個屬性，與隊列所包含的對象無關(guān)。隊列中對象的次序依賴于其插入、刪除的順序。隊列中的次序關(guān)系的主要特點是先進(jìn)先出。
2）對隊列的操作限制在兩個位置上，即front（對頭）、rear（隊尾）。我們可以在尾部增加對象，在頭部刪除對象，或查詢頭部的對象。
3）可以用MakeEmpty方法可以清除隊列的對象，也可用isEmpty來查詢該隊列是否為空，以及查詢隊列的大小（size()）。
接口Queue是對Container的擴(kuò)展，因此它繼承了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（關(guān)聯(lián)性）
有序容器包含了一些對象，這些對象在容器中的位置（或次序）是根據(jù)它的某個屬性的重要性來決定的，更確切的說，有序容器中的對象是可比較的，這個屬性可以通過要求對象類來實現(xiàn)Comparable接口來獲得。Comparable接口包含唯一一個查詢方法CompareTo。
查詢CompareTo返回一個整數(shù)值。
/** 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)組合起來，即在鍵和其值之間有一個關(guān)聯(lián)。類Association在研究一個需要鍵－值（key－value）對的容器數(shù)據(jù)結(jié)構(gòu)時起到什么重要的作用。
在字典類容器中就包含Association類的實例，字典是由鍵組成的，也就是說，我們查找字典中的對象時，只是查找它的鍵。如果字典按某種順序（根據(jù)所包含的鍵的相對大小）排列的，那么我們必須保證任何輸入到OrderdDictionary（有序字典）中的關(guān)聯(lián)對的鍵也是可以比較的（Comparable）。同時，我們要求關(guān)聯(lián)也必須是可串行化的，這樣才能保證前面所提到的所有容器都要求是可串行化的。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);
}
}
未完，待續(xù)....