抽象資料型別

抽象資料型別（ADT）描述一個集合承諾能做什麼，而不說它是怎麼做到的。想想自動櫃員機。從外面看，你知道它的合約：插卡、輸入密碼、領現金、查餘額。你並不知道——也不需要知道——現金是裝在轉鼓裡、托盤裡，還是牆後一隻機械臂裡。介面是承諾；機械是藏起來的。抽象資料型別對一組資料來說，正是這樣一種承諾：它支援哪些操作，以及每個操作意味著什麼。

舉個例子，堆疊這個抽象資料型別只承諾壓入、彈出、以及「看一眼頂上是什麼」，規則是後進先出。佇列這個抽象資料型別承諾相反的次序，先進先出。映射（或字典）這個抽象資料型別承諾存放「鍵到值」的配對，並能憑鍵查到值。要緊的是，這些都沒說「怎麼做」。堆疊可以由陣列實作，也可以由鏈結串列實作；映射可以是雜湊表，也可以是平衡樹。抽象資料型別是行為；資料結構則是兌現這一行為的某一台機器。

為什麼要把兩者分開？因為這樣你就能只憑那份承諾來推理正確性，然後把底下的機器換成更快的一台，而不必動用到它的那些程式碼——只要新機器守住同樣的承諾。這正是良好軟體設計的核心：面向介面編程，而非面向實作。當你讀到「佇列的入隊是 O(1)」時，那是在說佇列這個抽象資料型別的某一種具體實作，而不是在說抽象資料型別本身。