ADT

抽象數據類型( ADT，Abstract Data Type)是指一個數學模型以及定義在此數學模型上的一組操作。它通常是對數據的某種抽象，定義了數據的取值範圍及其結構形式，以及對數據操作的集合。 ^[1] 

例如，各種高級程序設計語言中都有“整數”類型，儘管它們在不同處理器上實現的方法不同，但對程序員而言是“相同的”，即數學特性相同。從“數學抽象”的角度看，可稱它為一個“抽象數據類型”。 ^[1] 

抽象數據類型的特徵是將使用與實現分離，從而實行封裝和隱藏信息。抽象數據類型通過一種特定的數據結構在程序的某個部分得以實現，只關心在這個數據類型上的操作，而不關心數據結構具體實現。 ^[1] 

抽象數據類型的特徵主要體現在以下幾個方面： ^[1] 

注：“抽象”的意義在於數據類型的數學特性，其數學特性和具體的計算機或語言無關。 ^[1] 

在編程語言（或庫）和教科書中，常見的幾個抽象數據類型如下：

關聯數組用字符串代替數字來索引數組中的元素。可以認為索引字符串是用來尋找元素的關鍵字。在Perl中,利用在數組名前加前綴百分號(%)來定義一個關聯數組。被賦值的值列表由索引字符串對和元素值組成。索引字符串後跟隨元素值，元素值後面跟下個索引字符串和元素值，以此類推。 ^[2] 

定義如下： ^[3] 

ADT complex{

數據對象：D={real, image | real∈實數, image∈實數} ^[3] 

數據關係：R={<real,image>} ^[3] 

基本操作： ^[3] 

}ADT Complex ^[3] 

容器類是容納、包含一組對象或對象集的對象。 ^[4]  與一個盒子中放置一套書和一個書包中放入一些鉛筆相似的方式，容器類包含一組對象或一個對象集。容器類作為通用對象收集器( generic holder)。C++語言的容器類中可以包含混合的對象。即容器類可以包含組不同類型的對象或一組相同類型的對象。 ^[4] 

當容器類包含不同類型的對象時，稱為異類容器類( heterogenous container)當容器類包含相同類型的對象時，稱為同類容器類(homogenous container)。容器類的名稱源於它的功能，如果我們使用容器類來存儲對象或從容器類中檢索對象，我們可以由此知道應該對存儲在容器類中的對象或與容器類相關聯的對象作哪些操作輸入一些數據到計算機或輸出一些數據到與計算機連接的設備是最通常的操作，除此之外，設計程序時最常進行的操作包括:查詢、排序、添加、檢索、存儲數據。 ^[4] 

實際上，命令計算機執行這些數據控制操作被認為計算機程序設計定義固有的內容。C++語言的容器類用於幫助創建這些基本的操作對數據的排序、查詢、添加、刪除、存儲以及其他的一些操作通常需要預先定義特定的數據類型和數據結構。在非面向對象的程序設計語言中，例如C語言、Fortran語言、Pascal語言和Cobol語言，計算機程序分為數據類型、數據結構以及按照這些數據結構完成的操作和算法。 ^[4] 

雙端隊列是一種插入和刪除工作在兩端都可進行的線性表。可以把雙端隊列看成是底元素連在一起的兩個棧。它們與兩個棧共享存儲空間不同的是，兩個棧的棧頂指針是兩邊延伸的。

由於雙端隊列允許在兩端進行插入刪除工作，因此需要建立兩個指針，分別指向雙端隊列中兩端的元素。允許在一端進行插入和刪除，另一端只允許插入的雙端隊列稱為輸出受限雙端隊列;允許在一端進行插入和刪除，而另一端只允許刪除的雙端隊列稱為輸入受限雙端隊列。 ^[5] 

列表是一個特別靈活的結構，因為它可以根據要求而增長和收縮而且其中任何位置都可被訪問，可以插入和刪去元素。幾個列表可以連接在一起以形成更大的列表，也可以把一個列表分開成若干個子列表。在諸如信息查尋，程序設計翻譯及模擬等應用中都會使用列表，在一些存儲管理技術中也廣泛地使用列表處理。從數學上説，列表就是一個給定類型的零個或多個元素的序列。 ^[6] 

即多重映像容器，與一般映像map不同的是，多重映像multimap中允許出現相同的鍵值。多重映像容器中，沒重載下標運算符“[ ]”本容器的成員函數“iterator find ( const Key& key) ;"，返回的是容器中第1個鍵值為key的iterator(遊標值)--注意該容器允許出現相同鍵值。其他成員函數與一般映像map相類似。 ^[7] 

優先隊列( Priority Queue)是一種抽象數據類型( Abstract Data Type)，可以把它看成種容器，裏面有一些元素，這些元素稱為隊列的結點(Node)。優先隊列的結點至少要包含一種性質：有序性，也就是説任意兩個結點可以比較大小。為了具體起見，我們假設這些結點中都包含一個鍵值(Key)，結點的大小通過比較它們的鍵值而定。優先隊列並不是按照入隊的順序簡單地執行先進先出( First in first out )，而是按照一定的優先級(鍵值的大小)調用。優先隊列最早出現在操作系統中，實現對任務或進程的調度。 ^[8] 

優先隊列在信息學競賽中十分常見，在統計問題、最值問題、模擬問題和貪心問題等類型的題目中都有着廣泛的應用。優先隊列有三種基本操作：插入結點( Insert )、取最小結點( Get Min )和刪除最小結點( Delete min )。優先隊列有着多種具體實現方法，不同實現方法的三種基本操作的時間複雜度也有很大的區別。比如，採用一維數組或線性鏈表實現，插入結點的時間複雜度只需要O(1)，但取最小結點和刪除最小結點的時間複雜度為O(n)；採用二叉排序樹實現，三種基本操作的時間複雜度都為O(log₂n)，但二又排序樹可能退化成線性表。 ^[8] 

隊列( Queue)是隻允許在一端進行插入操作，而在另外一端進行刪除操作的線性表。只允許插入的一端稱為隊尾rea，只允許刪除的一端稱為隊頭front)°。事實上，在隊列中，這兩種操作已經不再稱為“插入”和“刪除”，而是稱為“入隊”和“出隊”。 ^[9] 

隊列是一種先進先出( First-In First-Out，FIFO)的結構，具有很強的順序特徵。隊列會記錄下零散無序的數據進入隊列的順序，並且在出隊的時候保持這個順序，以方便程序算對其進行利用。 ^[9] 

隊列中不允許對除了隊頭和隊尾之外的其他元素進行任何形式的操作。這種限制使得隊列雖然名義上是一種線性表，但是它已經幾乎喪失了線性表的所有特點，無法對其進行線性表的大部分操作。 ^[9] 

隊列就像一個管道一樣，將位於管道中間的數據保護起來，只留下管道的兩端可供程序員進行操作。 ^[9] 

STACK，棧是一種特殊的表，這種表只在表頭進行插入和刪除操作。因此，表頭對於棧來説具有特殊的意義，稱為棧頂。相應地，表尾稱為棧底。不含任何元素的棧稱為空棧。

堆棧的行為特徵：假設一個棧S中的元素為a_n，a_n-1，,,, ,a1，則稱a₁為棧底元素，a_n為棧頂元素。棧中的元素按a，a₂，,,, ，a_n-1，a_n的次序進棧。在任何時候，出棧的元素都是棧頂元素。換句話説，棧的修改是按後進先出的原則進行的。因此，棧又稱為後進先出表，簡稱LIFO表。 ^[3] 

ADT String

數據元素集合: ^[10] 

字符的一個有限序列。 ^[10] 

基本操作： ^[10] 

樹的抽象數據類型的定義如下:

ADT Tree {

(1)數據對象D：一個集合，該集合中的所有元素具有相同的特性。 ^[11] 

(2)數據關係R：若D為空或D中僅含有一個數據元素，則R={ ∅ }，否則R={ H }，H關係如下：

a.在D中存在唯一的稱為根的數據元素root，它在關係H下沒有前驅。 ^[11] 

b.除root以外，D中其餘結點存在m(m≥0)個不相交的劃分，每個劃分都是一棵樹，是根的子樹。

(3)樹的基本操作。 ^[11] 

} ADT Tree ^[11] 

抽象數據類型是一個數學模型以及定義在其上的一組操作組成，因此，抽象數據類型一般通過數據對象、數據關係以及基本操作來定義，即抽象數據類型三要素是(D，R，P)。 ^[9] 

ADT抽象數據類型名{ ^[9] 

數據對象：<數據對象的定義>

數據關係：<數據關係的定義>

基本操作：<基本操作的定義>

} ADT抽象數據類型名 ^[9] 

其中基本操作的定義格式為： ^[9] 

基本操作名（參數表）

初始條件：<初始條件描述>

操作結果：<操作結果描述> ^[9] 

實現於程序時，抽象數據類型只顯現出其接口，並將實現加以隱藏。用户只需關心它的接口，而不是如何實現。未來更可以改變實現的方式。（其支持信息隱藏原理，或保護程序免受變化的衝擊。） ^[9] 

抽象數據類型的強處在於對用户隱藏了實現細節，僅公開其接口。這表示抽象數據類型可以用各種方法來實現，只要遵循其接口，就不會影響到用户。 ^[9] 

在抽象數據類型和數據結構之間，有一個實現上的微妙差別。例如，列表的抽象數據類型可以數組為基礎、或者使用鏈表來實現。列表即是一種具良好運算（加入元素、移除元素等等）定義的抽象數據類型。鏈表是以指針為基礎的數據結構，且可用來創建一個列表。鏈表常用於列表的抽象數據類型。 ^[9] 

同樣地，二叉樹搜索法的抽象數據結構可以幾個方式實現：二叉樹、AVL樹、紅黑樹、數組等等。且無須關心其實現，二叉樹搜索法總是有相同的運算（插入、移除、查找等等）。 ^[9] 

從實現中分離出接口，並不表示用户不該知道實現的方法，而是用户不能依賴於實現細節。例如，一個抽象數據類型可以用腳本語言創建，或其它可以被反編譯的語言（如C語言）。即使用户可發現實現的方法，只要所有客户端程序遵循該接口，且改變實現方式時不會產生影響，那就仍是抽象數據類型。 ^[9] 

在面向對象的用語中，抽象數據類型相當於類別；抽象數據類型的實體就相當於對象。某些語言包含了用於宣告抽象數據類型的構造函數。例如，C++ 和 Java 為此提供了類的構造函數。 ^[9] 

抽象數據結構即根據所要運算的數據以及其計算複雜性所定義的抽象存儲區，而不關心具體的數據結構的實現。 ^[4] 

就實現高效率的算法而言，對數據結構的選擇相當重要。抽象數據結構的選擇，決定了高效率的算法的設計，和估計其計算複雜性。 ^[4] 

這個概念與編程語言理論中所使用的抽象數據類型非常接近，大致上抽象數據結構和抽象數據類型的名稱，和具體的數據結構的名稱一致。 ^[4] 

一部分抽象數據類型在程序設計中相當普遍且實用，所以在某些編程語言中，成為原生類型、或加進標準庫中。例如，Perl 的數組可以用列表或雙端隊列之類的抽象數據類型來實現，散列表也可以用 Map 或 Table 來做。C++ 標準庫和 Java 庫也提供了列表、堆棧、隊列、Map、優先權隊列和字符串。 ^[4]