表，棧和隊列(一)(JAVA語言描述)

文章目錄

• 抽象資料類型 ADT（abstract data type）
• 表ADT
• • 順序表簡單數組實作
  • 連結清單實作
  • JAVA Collections API 中的表
  • • Collection接口
    • Iterator接口
    • List接口，ArrayList接口，LinkedLIst接口

抽象資料類型 ADT（abstract data type）

抽象資料類型是帶有一組操作的一些對象的集合。在ADT的定義中沒有地方提到關于這組操作是如何實作的任何解釋，像表，集合，圖與他們的一些操作的對象可以被看做是抽象資料類型

表ADT

表ADT有許多操作實作，如insert和remove等。

順序表簡單數組實作

順序表由簡單數組實作，建立的時候需要估計表的大小，因為數組建立的時候需要指定大小。

數組的好處是find操作隻要常數時間，但是删除和插入操作一般需要線性時間。比如在位置0處插入資料，就必須後面的元素向後移一位騰出空間來用于插入，而如果要在最後一位插入，就直接可以插入。不過平均來看，每次插入或者删除都需要移動一半的資料，是以時間為O(N)。

連結清單實作

連結清單由一系列節點組成，這些節點不需要在記憶體中相連，隻要在節點中指定下一個節點的位置就行了。相比于順序表，連結清單的情況正好相反。執行find操作時，連結清單需要從頭周遊一遍，是以需要線性時間查找，但是執行insert和remove操作時卻很友善。如果要在某個位置i插入時，隻需要把它自己的next指向i+1位置，然後原先i位置的next指向自己就實作了插入。删除也是同樣的道理，把前一個的next指向自己的後一個位置，那麼自己就被删除了。

JAVA Collections API 中的表

JAVA語言包中含有一些普通資料結構的實作，通常叫做Collections API。其中含有Collection接口，Iterator接口還有List接口

Collection接口

Collection(集合)接口存儲一組類型相同的對象，下面是該接口的一些最重要的部分

public interface Collection<anyType> extends Iterable<anyType>{
    //傳回大小
    int size();
    //判斷是否為空
    boolean isEmpty();
    //清空
    void clear();
    //判斷是否含有某元素
    boolean contains(anyType x);
    //删除某元素
    boolean remove(anyType x);
    //添加某元素
    boolean add(anyType x);
    //周遊
    java.util.Iterator<anyType> iterator();
}
           

如下周遊

public static <anyType> void print(Collection<anyType> coll){
    for(anyType item : coll){
        System.out.println(item);
    }
}
           

Iterator接口

實作Iterable接口的集合必須實作Iterator方法，該方法傳回一個Iterator類型的對象，該Iterator是一個在java.util包中定義的接口

Iterator接口的思路是，通過Iterator方法，每個集合均可建立并傳回給客戶一個實作Iterator接口的對象，并将目前位置的概念在對象内部存儲下來，如下

public interface Iterator<anyType> {
    //判斷是否有下一項
    boolean hasNext();
    //給出集合的下一項
    anyType next();
    //删除next傳回的最新的項
    void   remove();
}
           

下面為周遊代碼

public static <anyType> void print(Collection<anyType> coll){
    Iterator<AnyType> itr = coll.iteartor();
    for(itr.hasNext()){
        anyType item = itr.next();
        System.out.println(item);
    }
}
           

使用疊代器時，使用其他的add，remove等方法是不合法的，而使用疊代器的remove是合法的。

List接口，ArrayList接口，LinkedLIst接口

java.util的list接口繼承了Collection接口，是以它包含Collection接口的所有方法，外加一些其他的方法，下面為一些重要的方法

public interface LIst<AnyType> extends Collection<AnyType>{
    //通路指定idx的值
    AnyType get(int idx);
    //更改指定idx的值
    AnyType set(int idx, AnyType newVal);
    //在指定idx後增加值
    void add(int idx, AnyType x);
      //删除指定idx的值
    void remove(int idx);

    //疊代器
    ListIterator<AnyType> listIterator(int pos);
}
           

List ADT有兩種實作形式

ArrayList類提供了一種可增長數組的實作，優點在于get()和set()操作隻需要常數時間，缺點是删除插入操作代價昂貴。

而LinkedList是一種雙連結清單的實作，删除插入的代價非常小，但是不容易做索引，get和set調用代價昂貴，除非調用接近表的端點。