抽象數(shù)據(jù)類型(ADT)是一種只能通過接口訪問的數(shù)據(jù)類型，它是字段與基于字段的操作所構(gòu)成的集合。這里的接口不是interface，而是訪問數(shù)據(jù)的途徑，接口把數(shù)據(jù)的表示和操作方法的實(shí)現(xiàn)完全分離開來。兩種最基本的ADT是堆棧和隊(duì)列，并且根據(jù)我們的需要，可以構(gòu)建更為復(fù)雜的ADT，例如可以對(duì)數(shù)據(jù)項(xiàng)進(jìn)行計(jì)數(shù)，檢查數(shù)據(jù)項(xiàng)是否存在重復(fù)等等。
在很多實(shí)際應(yīng)用中，我們都不允許存在數(shù)據(jù)項(xiàng)重復(fù)的情況，需要對(duì)用戶提交的重復(fù)數(shù)據(jù)進(jìn)行合適的處理。讓用戶保證不提交重復(fù)的數(shù)據(jù)可以避免這種情況的發(fā)生，但顯然這種方法并不實(shí)際，既然使用ADT就是為了給使用它的程序員提供簡(jiǎn)單明了的數(shù)據(jù)類型解決方案，那么我們就應(yīng)該在ADT中來解決這個(gè)問題。以隊(duì)列為例，一般可以通過兩種策略來處理這個(gè)問題：
1. 放棄新輸入的數(shù)據(jù)項(xiàng)：當(dāng)最新放入隊(duì)列中的數(shù)據(jù)項(xiàng)已經(jīng)在隊(duì)列中時(shí)，放棄當(dāng)前輸入的數(shù)據(jù)項(xiàng)。
2. 放棄舊的數(shù)據(jù)項(xiàng)，保存新輸入的數(shù)據(jù)項(xiàng)：當(dāng)最新放入隊(duì)列中的數(shù)據(jù)項(xiàng)已經(jīng)在隊(duì)列中時(shí)，放棄已經(jīng)存在于隊(duì)列中的數(shù)據(jù)項(xiàng)，保存當(dāng)前放入的數(shù)據(jù)項(xiàng)。
對(duì)于第一種處理方式，在一種特殊的情況下，數(shù)據(jù)項(xiàng)存儲(chǔ)的數(shù)據(jù)是0~N-1之間的整數(shù)，那么可以通過增加一個(gè)新的數(shù)組a[i]或鏈表來儲(chǔ)存boolean類型數(shù)據(jù)，當(dāng)隊(duì)列中第i個(gè)位置上已經(jīng)存在數(shù)據(jù)i時(shí)(i<=N-1)，設(shè)置a[i]=boolean，那么可以通過a[i]來判斷數(shù)據(jù)i是否已經(jīng)存在于隊(duì)列中。第二種處理方式比第一種更為復(fù)雜一些，如果有必要，還可以讓用戶去選擇采取哪種策略來避免重復(fù)的數(shù)據(jù)項(xiàng)。但不管怎么樣，我們可以通過構(gòu)建不同類型的ADT，并在ADT中實(shí)現(xiàn)某些我們所需要的功能，將能極大限度地保證數(shù)據(jù)結(jié)構(gòu)和算法的靈活性與清晰的結(jié)構(gòu)，使基于ADT的實(shí)現(xiàn)能滿足各種不同的具體應(yīng)用，并方便類的重構(gòu)。