不完全類型和抽象數(shù)據(jù)類型的定義

立功教授數(shù)年之心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》以及《面向AMetal框架與接口的編程（上）》，書(shū)本內(nèi)容公開(kāi)后，在電子行業(yè)掀起一片學(xué)習(xí)熱潮。經(jīng)周立功教授授權(quán)，本公眾號(hào)特對(duì)《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》一書(shū)內(nèi)容進(jìn)行連載，愿共勉之。

第二章為程序設(shè)計(jì)技術(shù)，本文為2.4.1 不完全類型和2.4.2 抽象數(shù)據(jù)類型。

>>> 2.4.1 不完全類型

不完全類型是指“函數(shù)之外、類型的大小不能被確定的類型”，結(jié)構(gòu)體標(biāo)記的聲明就是一個(gè)不完全類型的典型示例。比如：

此時(shí)，struct _TypeA和struct _TypeB是互相引用的，雖然無(wú)論先聲明哪一邊都很麻煩，但可以先通過(guò)聲明結(jié)構(gòu)體標(biāo)記回避以上問(wèn)題。比如：

當(dāng)使用typedef聲明結(jié)構(gòu)體類型時(shí)，比如：

由于TypeB類型的標(biāo)記被聲明時(shí)，還不知道它的內(nèi)容，因此無(wú)法確定它的大小，這樣的類型就被稱為不完全類型。因?yàn)椴荒艽_定大小，所以不能將不完全類型變成數(shù)組，也不能將其作為結(jié)構(gòu)體的成員，或聲明為變量。但如果聲明為指針，則可以使用不完全類型。在后續(xù)定義struct _TypeB的內(nèi)容時(shí)，TypeB就不是不完全類型了。

通常在“.h”頭文件中聲明不包含任何實(shí)現(xiàn)細(xì)節(jié)的結(jié)構(gòu)體，然后在“.c”實(shí)現(xiàn)文件中定義與數(shù)據(jù)結(jié)構(gòu)的特定實(shí)現(xiàn)配合使用的函數(shù)。數(shù)據(jù)結(jié)構(gòu)的用戶可以看到聲明和函數(shù)原型，但實(shí)現(xiàn)會(huì)隱藏在“.c”文件中。只有使用數(shù)據(jù)結(jié)構(gòu)所需要的信息會(huì)對(duì)用戶可見(jiàn)，如果太多的內(nèi)部信息可見(jiàn)，用戶可能會(huì)使用這些信息從而產(chǎn)生依賴。一旦內(nèi)部結(jié)構(gòu)發(fā)生變化，則用戶代碼可能就會(huì)失效。不完全類型是因?yàn)榫幾g器看不見(jiàn)“.c”文件中的實(shí)際定義，它只能看到_demoB結(jié)構(gòu)體的類型定義，而看不見(jiàn)結(jié)構(gòu)體的實(shí)現(xiàn)細(xì)節(jié)。

下面將以數(shù)組為例介紹不完全類型的使用，盡管可以使用數(shù)組保存元素，由于數(shù)組的大小是固定的，因此數(shù)組并不會(huì)存儲(chǔ)它的大小，而且也不會(huì)檢查下標(biāo)是否越界。通常用一個(gè)指向數(shù)組的指針pBuffer和記錄數(shù)組元素個(gè)數(shù)的值count代替數(shù)組。其實(shí)現(xiàn)如下（IA_array.c）：

為了防止用戶直接訪問(wèn)結(jié)構(gòu)體的成員，通常將結(jié)構(gòu)體移到實(shí)現(xiàn)代碼中（IA_array.c）隱藏起來(lái)，然后使用不完全的類型在接口中（IA_array.h）聲明一個(gè)IntArray處理相應(yīng)的數(shù)據(jù)。雖然不完全類型描述了對(duì)象，但缺少對(duì)象大小所需的信息。比如：

其告訴編譯器_IntArray是一個(gè)結(jié)構(gòu)體標(biāo)記，卻沒(méi)有描述結(jié)構(gòu)體的成員，因此編譯器沒(méi)有足夠的信息確定結(jié)構(gòu)體的大小，其意圖是不完全類型將會(huì)在程序的其它地方將信息補(bǔ)充完整。不完全類型的使用是受限的，因?yàn)榫幾g器不知道它的大小，所以不能在接口中用它聲明變量：

但可以在接口中（IA_array.h）定義一個(gè)指針類型引用不完全類型：

在這里，僅僅聲明了它的存在，而沒(méi)有做別的任何事情。對(duì)于用戶來(lái)說(shuō)，看到的只是IA_array.h，而對(duì)_IntArray的構(gòu)造或?qū)崿F(xiàn)卻一無(wú)所知。

當(dāng)將IntArray定義為一個(gè)指向struct _IntArray結(jié)構(gòu)體類型時(shí)，即可聲明IntArray*類型的變量，將其作為函數(shù)參數(shù)進(jìn)行傳遞。即：

盡管此時(shí)還沒(méi)有定義IntArray，但指針的大小始終相同，且不依賴于它指向的對(duì)象。即便在不知道結(jié)構(gòu)體本身細(xì)節(jié)的前提下，編譯器同樣允許處理指向結(jié)構(gòu)體的指針，這就解釋了為什么C允許這種行為。雖然這個(gè)結(jié)構(gòu)體是一個(gè)不完全類型，但在實(shí)現(xiàn)代碼中信息變得完整，因此該結(jié)構(gòu)體的成員依賴于實(shí)現(xiàn)方法。

雖然數(shù)組和指針有區(qū)別，但C語(yǔ)言不會(huì)區(qū)分它們，C對(duì)數(shù)組提供的支持只是為了便于內(nèi)存管理和指針運(yùn)算，最好的證明莫過(guò)于括號(hào)運(yùn)算符居然有交換性。當(dāng)在結(jié)構(gòu)體內(nèi)創(chuàng)建一個(gè)數(shù)組時(shí)，為了避免直接對(duì)數(shù)據(jù)進(jìn)行訪問(wèn)，將通過(guò)接口函數(shù)和對(duì)象交互，詳見(jiàn)程序清單 2.30。

程序清單 2.30 訪問(wèn)數(shù)組元素和大小接口（IntArray.h）

為了說(shuō)明這些函數(shù)構(gòu)成了IntArray對(duì)象的接口，并防止函數(shù)名和其它對(duì)象的接口沖突，于是在每個(gè)函數(shù)名前使用了前綴IA_，且每個(gè)函數(shù)都有一個(gè)IntArray*型的對(duì)象作為參數(shù)，這個(gè)參數(shù)就是函數(shù)將要操作的對(duì)象。

IA_init()初始化使數(shù)組處于空元素的狀態(tài)，IA_cleanup()釋放在數(shù)組生存期中分配給用戶的內(nèi)存。剩余的函數(shù)是控制對(duì)數(shù)組中數(shù)據(jù)的訪問(wèn)，IA_setSize()設(shè)置了數(shù)組中的元素個(gè)數(shù)，且為這些元素分配存儲(chǔ)空間，IA_getSize()返回當(dāng)前數(shù)組中的元素個(gè)數(shù)。IA_setElem()和IA_getElem()用于訪問(wèn)單個(gè)數(shù)據(jù)元素，其具體實(shí)現(xiàn)詳見(jiàn)程序清單 2.31。

程序清單 2.31 訪問(wèn)數(shù)組元素和大小接口的實(shí)現(xiàn)（IntArray.c）

其中，IA_setSize()用于改變數(shù)組大小，首先釋放原有的元素，然后保存新的元素，且為新元素分配存儲(chǔ)空間。當(dāng)然，也可以優(yōu)化進(jìn)一步代碼，比如，只有數(shù)組大小增加時(shí)才重新分配空間。IA_getSize()訪問(wèn)給定下標(biāo)所指的元素，讓IntArray檢查下標(biāo)是否在界內(nèi)。

由此可見(jiàn)，IntArray的實(shí)現(xiàn)是由兩部分組成的，即保存對(duì)象信息的數(shù)據(jù)和構(gòu)成對(duì)象接口的函數(shù)，其使用范例程序詳見(jiàn)程序清單 2.32。

程序清單 2.32 使用IntArray.h范例程序

>>> 2.4.2 抽象數(shù)據(jù)類型

1. 棧的實(shí)現(xiàn)

假設(shè)需要一個(gè)字符棧，且棧的大小是固定的，即可使用數(shù)組保存棧中的元素，然后指定一個(gè)計(jì)數(shù)器表明棧中元素的數(shù)量。其數(shù)據(jù)結(jié)構(gòu)定義如下：

由于調(diào)用者并不能直接訪問(wèn)底層，因此在向棧中壓入元素之前，必須先創(chuàng)建一個(gè)棧。其函數(shù)原型為：

由于剛開(kāi)始時(shí)棧為空，暫時(shí)還沒(méi)有元素存儲(chǔ)到數(shù)組elements[0]中，因此只要將數(shù)組的下標(biāo)置為0，即可創(chuàng)建一個(gè)空棧。即：

其調(diào)用形式如下：

當(dāng)向棧中壓入一個(gè)新的元素時(shí)，將元素存儲(chǔ)在數(shù)組接下來(lái)的空間中，并計(jì)數(shù)遞增。其函數(shù)原型為：

也就是說(shuō)，當(dāng)top的值加1時(shí)，則將新的元素值value入棧。即：

當(dāng)彈出元素時(shí)，計(jì)數(shù)遞減并返回棧頂元素。其函數(shù)原型如下：

也就是說(shuō)，當(dāng)top的值減1時(shí)，則刪除棧頂結(jié)點(diǎn)，返回該結(jié)點(diǎn)的值。比如：

除了這些基本的操作之外，經(jīng)常還需要知道棧所包含的元素?cái)?shù)量，以及棧是空還是滿，這些函數(shù)的原型為：

顯然，只要返回棧頂值就知道棧中存儲(chǔ)了多少個(gè)元素，而當(dāng)stack->top為0時(shí)，說(shuō)明棧為空；當(dāng)stack->top大于等于MAXSIZE時(shí)，說(shuō)明棧已滿。

實(shí)際上，當(dāng)定義了一個(gè)結(jié)構(gòu)體指針變量stack后，（stack->top）就成為了一個(gè)變量，即可通過(guò)stack->top與stack->elements[stack->top++]分別實(shí)現(xiàn)對(duì)stack的各成員的訪問(wèn)。顯然程序暴露了“數(shù)組和下標(biāo)”這一內(nèi)部結(jié)構(gòu)，且無(wú)法阻止用戶使用stack指針變量直接訪問(wèn)結(jié)構(gòu)體的成員。比如：

由于對(duì)直接訪問(wèn)top和elements，因此用戶有可能破壞棧中的數(shù)據(jù)。如果其內(nèi)部實(shí)現(xiàn)發(fā)生變化，也必須對(duì)程序進(jìn)行相應(yīng)的修改。如果程序規(guī)模很大，則修改的工作量也很大，因此很多時(shí)候明明知道通過(guò)重構(gòu)能夠改善程序，也會(huì)因工作量太大而不愿意改變具體的實(shí)現(xiàn)。

由此可見(jiàn)，上述棧的實(shí)現(xiàn)方法不僅暴露了棧的數(shù)據(jù)結(jié)構(gòu)，而且僅有1個(gè)棧。如果需要多個(gè)棧時(shí)，怎么辦？一種方法是編寫(xiě)多個(gè)名字不同功能相同的函數(shù)，這樣就會(huì)出現(xiàn)多段處理完全相同的代碼。為了解決這個(gè)問(wèn)題，抽象的方法是將棧中的數(shù)據(jù)結(jié)構(gòu)隱藏到實(shí)現(xiàn)代碼中。

2. 建立抽象

雖然標(biāo)準(zhǔn)C提供了類似int、char、float、double這樣不可分割的原子數(shù)據(jù)類型，但如果需要表示任意大的整數(shù)，顯然原子數(shù)據(jù)類型無(wú)能為力。此時(shí)，創(chuàng)建一種新的整數(shù)類型勢(shì)在必行，而這種新的數(shù)據(jù)類型便是一種抽象數(shù)據(jù)類型ADT（Abstract Data Type）。

設(shè)計(jì)一個(gè)基于Stack的抽象數(shù)據(jù)類型，我們應(yīng)該從哪里開(kāi)始呢？一個(gè)不錯(cuò)的方法是用一句話來(lái)描述。這種描述應(yīng)該盡可能地抽象，盡量不要涉及數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，要簡(jiǎn)單到誰(shuí)都能夠理解它，因此可以描述“棧（Stack）是一個(gè)可以在同一個(gè)位置上插入（push）和刪除（pop）數(shù)據(jù)（value）的存儲(chǔ)器，該位置是存儲(chǔ)器的末端，即棧頂（top）”。該定義既未說(shuō)明棧中存儲(chǔ)什么數(shù)據(jù)，也未指定是用數(shù)組、結(jié)構(gòu)體還是其它數(shù)據(jù)形式存儲(chǔ)數(shù)據(jù)，而且也沒(méi)有規(guī)定用什么方式實(shí)現(xiàn)操作，這些細(xì)節(jié)都留給實(shí)現(xiàn)去完成。

關(guān)于棧的詳細(xì)描述如下：

• 類型名：Stack

• 類型屬性：可以存儲(chǔ)有序的數(shù)據(jù)（value）

• 類型操作：創(chuàng)建棧（newStack）和銷毀棧（freeStack），從棧頂添加數(shù)據(jù)（push）和從棧頂刪除數(shù)據(jù)（pop），確定棧是否為空（stackIsEmpty），確定棧是否已滿（stackIsFull），返回棧中元素的個(gè)數(shù)（getStackDepth），讀取棧中任何位置的元素（getStackElement）。

也就是說(shuō)，在向棧中添加元素之前，必須先創(chuàng)建一個(gè)棧。當(dāng)不再使用內(nèi)存時(shí)，必須銷毀棧。對(duì)棧的基本操作有push（進(jìn)棧）和pop（出棧），前者相當(dāng)于插入，后者相當(dāng)于刪除最后插入的元素。對(duì)空棧進(jìn)行的pop，認(rèn)為是棧ADT的錯(cuò)誤。另一方面，當(dāng)運(yùn)行push時(shí)空間用盡是一個(gè)實(shí)現(xiàn)錯(cuò)誤，但不是ADT錯(cuò)誤。

3. 建立接口

（1）隔離變化

為了防止用戶直接訪問(wèn)top和elements而破壞棧中的數(shù)據(jù)，根據(jù)以往的經(jīng)驗(yàn)，可以使用使用依賴倒置原則。將保存在結(jié)構(gòu)體中棧的實(shí)現(xiàn)所需要的數(shù)據(jù)結(jié)構(gòu)隱藏在“.c”文件中，將處理數(shù)據(jù)的接口包含在“.h”文件中，用戶將無(wú)法看到棧的數(shù)據(jù)結(jié)構(gòu)在底層是如何實(shí)現(xiàn)的。

雖然可以將一個(gè)數(shù)組看作是具有固定小的，但是內(nèi)置數(shù)組并不會(huì)存儲(chǔ)它的大小，而且也不會(huì)檢查下標(biāo)是否越界。通常將一個(gè)指向數(shù)組的指針data和記錄數(shù)組元素個(gè)數(shù)的值numData存儲(chǔ)棧的最大容量，以及記錄棧頂元素的位置top進(jìn)行打包，將棧的數(shù)據(jù)結(jié)構(gòu)隱藏在“.c”文件中。即：

對(duì)于用戶來(lái)說(shuō)，現(xiàn)在只能通過(guò)“.h”文件中的接口操作棧。盡管此時(shí)還沒(méi)有定義stackCDT，由于指針的大小始終相同，且不依賴于它指向的對(duì)象。即便在不知道結(jié)構(gòu)體本身細(xì)節(jié)的前提下，編譯器同樣允許處理指向結(jié)構(gòu)體的指針，因此可以定義一個(gè)指針類型引用不完全類型，將stackADT定義為一個(gè)指向stackCDT *結(jié)構(gòu)體類型。比如：

雖然這個(gè)結(jié)構(gòu)是一個(gè)不完全類型，但在實(shí)現(xiàn)棧的文件中信息變得完整，因此該結(jié)構(gòu)的成員依賴于棧的實(shí)現(xiàn)方法。stackADT結(jié)構(gòu)體類型的變量定義如下：

由于一個(gè)stack1指向一個(gè)存儲(chǔ)單元，即一個(gè)存儲(chǔ)單元代表一個(gè)棧，因此你想要多少個(gè)棧就有多少個(gè)棧。比如：

顯而易見(jiàn)，stackADT是代表stack1、stack2、stack3等所有具體棧的總稱的抽象數(shù)據(jù)類型，stack1、stack2和stack3分別指向不同的棧。因此只要將stack1、stack2和stack3作為實(shí)參傳遞給相應(yīng)的函數(shù)，即可訪問(wèn)與之相應(yīng)的棧。而抽象的方法是在棧的實(shí)現(xiàn)代碼和使用棧的代碼之間添加一個(gè)函數(shù)層。比如：

通常將稱為函數(shù)上下文的stackADT類型的stack作為函數(shù)的第一個(gè)參數(shù)，這個(gè)參數(shù)就是函數(shù)將要操作的對(duì)象。它代表指向當(dāng)前對(duì)象（棧）的指針，用于請(qǐng)求對(duì)象對(duì)自身執(zhí)行某些操作。而結(jié)構(gòu)體的成員變量就是通過(guò)stack指針找到自己所屬的對(duì)象的，其引用方式如下：

由此可見(jiàn)，用戶僅通過(guò)接口函數(shù)與棧交互，而不是直接訪問(wèn)它的數(shù)據(jù)。

（2）操作方法

• 創(chuàng)建棧

由于用戶完全不知道底層是如何表示的，因此必須提供一個(gè)用于創(chuàng)建一個(gè)新stackADT的函數(shù)，且將它返回給用戶。用于創(chuàng)建一個(gè)新的抽象類型的值的函數(shù)名稱以new開(kāi)始，以強(qiáng)調(diào)動(dòng)態(tài)分配。其函數(shù)原型如下：

前置條件：stackADT被定義為一個(gè)指向結(jié)構(gòu)體的指針，該結(jié)構(gòu)體包含top和numData。一旦知道最大容量，則該棧即可被動(dòng)態(tài)確定。創(chuàng)建一個(gè)具有給定最大值MAXSIZE的棧，其分別是為stackCDT結(jié)構(gòu)體分配空間和長(zhǎng)度為MAXSIZE的數(shù)組分配空間。同時(shí)將top初始化為0，并將numData置為最大值MAXSIZE。

后置條件：返回棧。

其調(diào)用形式如下：

• 銷毀棧

當(dāng)接口定義了一個(gè)分配新的抽象類型的值的函數(shù)時(shí)，通常還要為接口提供一個(gè)用于釋放用戶不再使用的棧的動(dòng)態(tài)內(nèi)存的函數(shù)。其函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧；

后置條件：釋放動(dòng)態(tài)分配的所有內(nèi)存，即先釋放棧的數(shù)組，然后釋放棧的結(jié)構(gòu)。

其調(diào)用形式如下：

• 從棧頂添加據(jù)（進(jìn)棧）

當(dāng)用戶向棧頂添加一個(gè)數(shù)據(jù)時(shí)，就是將該值存儲(chǔ)在內(nèi)部的數(shù)據(jù)結(jié)構(gòu)中。即通過(guò)在容器的頂端插入元素實(shí)現(xiàn)push，其函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧，value是待壓入棧頂?shù)臄?shù)據(jù)；

后置條件：如果棧不滿，將value放在棧頂，該函數(shù)返回true，否則棧不變，該函數(shù)返回false。

其調(diào)用形式如下：

• 從棧頂刪除數(shù)據(jù)（出棧）

當(dāng)用戶彈出棧元素時(shí)，就是將存儲(chǔ)的值返回給用戶。即通過(guò)刪除容器頂端的元素實(shí)現(xiàn)pop，其函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧，pValue為指向存儲(chǔ)返回值變量的指針；

后置條件：如果棧不空，將棧頂?shù)闹悼截惖?pValue，刪除棧頂?shù)闹担摵瘮?shù)返回true，如果刪除前棧為空，棧不變，該函數(shù)返回false。

其調(diào)用形式如下：

• 判斷棧是否為空

判斷棧是否為空的函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧；

后置條件：如果棧為空則返回true，否則返回false。

其調(diào)用形式如下：

• 判斷棧是否已滿

判斷棧是否已滿的函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧；

后置條件：如果棧已滿則返回true，否則返回false。

其調(diào)用形式如下：

• 確定棧中元素的個(gè)數(shù)

確定棧中元素的個(gè)數(shù)的函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧；

后置條件：返回棧中元素的個(gè)數(shù)。

其調(diào)用形式如下：

• 讀取棧中任何位置的元素

讀取棧棧任意位置元素的函數(shù)原型如下：

前置條件：stack指向之前創(chuàng)建的棧，index為索引值，表示返回棧中某個(gè)位置的元素， pValue為指向存儲(chǔ)返回值變量的指針；

后置條件：如果index大于top，該函數(shù)返回false，反之將index位置的值拷貝到*pValue，該函數(shù)返回true。

其調(diào)用形式如下：

由于數(shù)組的下標(biāo)是從0開(kāi)始的，當(dāng)index為0時(shí)，則getStackElemnt(stack, 0, &temp)返回棧頂?shù)脑?，getStackElemnt(stack, 1, &temp)返回接下來(lái)的那個(gè)元素，依此類推。

封裝時(shí)，頭文件中只放最小的接口函數(shù)聲明，且內(nèi)部函數(shù)都要加上static關(guān)鍵字。抽象棧的接口詳見(jiàn)程序清單 2.33，接口揭示了棧的數(shù)據(jù)類型和用戶在操作棧時(shí)需要的各種功能，這些功能實(shí)現(xiàn)了抽象棧類型的基本操作。

程序清單 2.33 抽象棧接口（stack.h）

這些函數(shù)共同創(chuàng)建了接口，每個(gè)函數(shù)都以stackADT作為它的第一個(gè)參數(shù)。當(dāng)聲明了函數(shù)接口后，即可實(shí)現(xiàn)相應(yīng)的接口。

4. 實(shí)現(xiàn)接口

由于數(shù)組的長(zhǎng)度在編譯時(shí)就已經(jīng)確定了，無(wú)法在運(yùn)行時(shí)動(dòng)態(tài)地調(diào)整。但有些應(yīng)用在編譯時(shí)并不知道應(yīng)該分配多大的內(nèi)存空間才能滿足要求，因此可以根據(jù)需要使用動(dòng)態(tài)內(nèi)存“在運(yùn)行時(shí)”為它分配內(nèi)存空間。和任何接口一樣，實(shí)現(xiàn)Stack.h接口需要編寫(xiě)一個(gè)模塊Stack.c，它提供了抽象類型的輸出函數(shù)和表示細(xì)節(jié)的代碼，詳見(jiàn)程序清單 2.34。

程序清單 2.34 抽象棧的實(shí)現(xiàn)（Stack.c）

表面上看起來(lái)getStackDepth()函數(shù)只有一行代碼，也許有人會(huì)說(shuō)，為何不直接使用“stack->top;”代替該函數(shù)呢？如果用戶在程序中使用top，那么程序?qū)⒁蕾囉趕tackADT表示的具體結(jié)構(gòu)，而使用該函數(shù)的好處是為用戶和實(shí)現(xiàn)之間提供了隔離層。由于維護(hù)代碼是軟件工程生命周期中的一個(gè)重要步驟，因此要盡量做好隨時(shí)修改的準(zhǔn)備。

當(dāng)然，上述程序還是不能創(chuàng)建兩種數(shù)據(jù)類型不同的棧，最常見(jiàn)的方法是使用void *作為數(shù)據(jù)類型，這樣就可以壓入和彈出任意類型的指針了。這里不再詳細(xì)描述，將留給讀者自己實(shí)現(xiàn)。但使用void *作為數(shù)據(jù)類型的最大缺點(diǎn)是不能進(jìn)行錯(cuò)誤檢測(cè)，存放void *數(shù)據(jù)的棧允許各種類型的指針共存，因此無(wú)法檢測(cè)由壓入錯(cuò)誤的指針類型而導(dǎo)致的錯(cuò)誤。

5. 使用接口

實(shí)際上使用棧的人并不關(guān)心棧是如何實(shí)現(xiàn)的，即使要改變棧的內(nèi)部實(shí)現(xiàn)方式，也不用對(duì)使用棧的程序做任何修改。將整數(shù)推入棧，然后再打印輸出的范例程序詳見(jiàn)程序清單 2.35。

程序清單 2.35 使用棧接口的范例程序

綜上所述，Stack棧的接口分為兩部分，其一是描述如何表示數(shù)據(jù)，其二是描述實(shí)現(xiàn)ADT操作的函數(shù)，因此必須先提供存儲(chǔ)數(shù)據(jù)的方法。設(shè)計(jì)一個(gè)結(jié)構(gòu)體，在“.h”接口中定義棧的抽象數(shù)據(jù)類型stackADT，在“.c”實(shí)現(xiàn)中定義棧的具體類型stackCDT。其次必須提供管理該數(shù)據(jù)的函數(shù)（方法），通過(guò)函數(shù)原型隱藏它們的底層實(shí)現(xiàn)。只要保留它們的接口不變，對(duì)于任何抽象都可以改變它的實(shí)現(xiàn)。實(shí)際上，當(dāng)引入一個(gè)抽象數(shù)據(jù)類型stackADT時(shí)，就是在使用依賴倒置原則，將保存在結(jié)構(gòu)體中棧的實(shí)現(xiàn)所需要的數(shù)據(jù)和處理數(shù)據(jù)的接口徹底分離，因?yàn)閟tackADT沒(méi)有暴露它的細(xì)節(jié)，用戶依賴于satcADT抽象，而不是細(xì)節(jié)。

顯然，抽象數(shù)據(jù)類型可利用已經(jīng)存在的原子數(shù)據(jù)類型構(gòu)造新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作組合新的操作。對(duì)于ADT，用戶程序除了通過(guò)接口中提到的那些操作之外，并不訪問(wèn)任何數(shù)據(jù)值。數(shù)據(jù)的表示和實(shí)現(xiàn)操作的函數(shù)都在接口的實(shí)現(xiàn)里面，與用戶完全分離。抽象的接口隱臧不相關(guān)的細(xì)節(jié)，用戶不能通過(guò)接口看到方法的實(shí)現(xiàn)，將注意力集中在本質(zhì)特征上，將程序員從關(guān)心程序如何實(shí)現(xiàn)的細(xì)節(jié)上得到解放。對(duì)于任何抽象來(lái)說(shuō)，只要保持接口不變，我們可以根據(jù)需要改變其實(shí)現(xiàn)方式。