合工大計算機(jī)專業(yè)相關(guān)課件數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)（第二章

棧）

DataStructures胡學(xué)鋼張晶計算機(jī)與信息學(xué)院2009年2月1第二章棧

第二章棧（stack）

2.1棧的定義和運算

2.2順序棧

2.3棧的應(yīng)用

2第二章棧棧是軟件設(shè)計中最基本的數(shù)據(jù)結(jié)構(gòu)，這是本課程所介紹的第一種數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)棧結(jié)構(gòu)時，需要掌握哪些方面的內(nèi)容？為此，回顧一下上一章所介紹的數(shù)據(jù)結(jié)構(gòu)的組成部分。由此可知，對每一種結(jié)構(gòu)的學(xué)習(xí)的組成部分。邏輯結(jié)構(gòu)分析

運算實現(xiàn)（算法）

運算定義

存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的組成32.1棧的定義和運算2.1.1棧的定義棧是只能在一端插入和刪除元素的線性表。

術(shù)語：棧頂,棧底,入棧（壓棧）,出棧（彈棧）

an

an-1……

a1入棧(PUSH)出棧(POP)棧頂(top)棧底(bottom)邏輯結(jié)構(gòu)和運算a1a2…an

特性：后進(jìn)先出(LIFO)----LastinFirstout

…a1a2anan…a2a142.1棧的定義和運算2.1.2棧的運算1.棧的基本運算定義對棧的基本運算有如下幾個：(1)初始化：設(shè)置棧為空。(2)判斷棧為空：若為空，則返回TRUE，否則返回FALSE.(3)判斷棧為滿：若為滿，則返回TRUE，否則返回FALSE.(4)取棧頂元素：取出棧頂元素。條件：棧不空。否則，應(yīng)能明確給出標(biāo)識，以便程序的處理。(5)入棧：將元素入棧，即放到棧頂。如果棧滿，怎樣處理？(6)出棧：刪除當(dāng)前棧頂?shù)脑?。如因為?？斩荒苓M(jìn)行，應(yīng)怎樣處理？

運算定義52.1.2棧的運算2.棧的運算的C++描述如何用C++描述棧的內(nèi)容和運算？一種方法是：將棧的有關(guān)數(shù)據(jù)和運算封裝在一起，以C++的類的形式來封裝描述。封裝的數(shù)據(jù)和運算要便于被有關(guān)程序來調(diào)用。因此，棧的C++描述的框架如下所示：classstack{};運算描述部分?jǐn)?shù)據(jù)描述部分類的名稱類的框架62.1.2棧的運算下面討論棧的運算的C++描述的細(xì)節(jié)，先給出每一個運算的對應(yīng)描述：初始化函數(shù)的描述棧的C++類描述：

classstack{stack();

…

棧的數(shù)據(jù)成員};棧的運算(1)初始化：設(shè)置棧為空。(2)判斷棧為空：若為空，則返回TRUE，否則返回FALSE.(3)判斷棧為滿：若為滿，則返回TRUE，否則返回FALSE.(4)取棧頂元素：取出棧頂元素。條件：棧不空。

否則，應(yīng)能明確給出標(biāo)識，以便程序的處理。(5)入棧：將元素入棧，即放到棧頂。如果棧滿，怎樣處理？(6)出棧：刪除當(dāng)前棧頂?shù)脑亍Ｈ缫驗闂？斩荒苓M(jìn)行，應(yīng)怎樣處理？

采用C++的構(gòu)造函數(shù)72.1.2棧的運算判斷函數(shù)的對應(yīng)棧的C++類描述：classstack{stack();

Boolempty()

Boolfull()

棧的數(shù)據(jù)成員};棧的運算(1)初始化：設(shè)置棧為空。(2)判斷棧為空：若為空，則返回TRUE，否則返回FALSE.(3)判斷棧為滿：若為滿，則返回TRUE，否則返回FALSE.(4)取棧頂元素：取出棧頂元素。條件：棧不空。

否則，應(yīng)能明確給出標(biāo)識，以便程序的處理。(5)入棧：將元素入棧，即放到棧頂。如果棧滿，怎樣處理？(6)出棧：刪除當(dāng)前棧頂?shù)脑亍Ｈ缫驗闂？斩荒苓M(jìn)行，應(yīng)怎樣處理？判斷為空的函數(shù)判斷為滿的函數(shù)const;const;82.1.2棧的運算其他幾個函數(shù)的對應(yīng)描述分析：（1）幾個運算的條件可能有不成立的情況，因此，需要給予明確的反映。（2）設(shè)立運算是否正常的類型error_code，正常時返回success,否則返回錯誤類型，如overflow,underflow等。enumerror_code{success,overflow,underflow};（3）可以將這幾個函數(shù)的類型設(shè)置為error_code；（4）如果需要返回其他的值，可以作為參數(shù)來返回。92.1.2棧的運算由上述討論可得到其他幾個函數(shù)的功能描述：（4)取棧頂元素的運算功能描述：如果棧不空，則取出棧頂元素到參數(shù)x中，然后返回success。否則，返回downflow。對應(yīng)的運算函數(shù)為：error_codeget_top(elementtype&x)const;(5)入棧的運算功能描述：如果棧不滿，則將元素入棧，并返回success。否則，返回overflow。對應(yīng)的運算函數(shù)為：error_codepush(constelementtypex);

102.1.2棧的運算(6)出棧的運算功能描述：如果棧不空，刪除當(dāng)前棧頂?shù)脑?，并返回success。否則，返回underflow。對應(yīng)的運算函數(shù)為：error_codepop();112.1.2棧的運算由此得到棧的類stack的函數(shù)成員列表如下：classstack{stack();//初始化Boolempty()const;//判斷空Boolfull()const;//判斷滿error_codeget_top(elementtype&x)const;//取棧頂元素error_codepush(constelementtypex);//入棧error_codepop();//出棧棧的數(shù)據(jù)成員;};問題：上述類的描述是否還需要補充什么？122.2順序棧2.2.1存儲結(jié)構(gòu)：假設(shè)有一個足夠大的存儲空間（數(shù)組）data,可用于存儲棧的元素。則可將棧中元素連續(xù)地存儲到數(shù)組的各元素----順序存儲方式。如下圖所示：其中：為了能隨時知道棧中的元素個數(shù)，設(shè)置了一個計數(shù)變量count。將數(shù)組data和count作為類stack的數(shù)據(jù)成員。棧的存儲結(jié)構(gòu)…a1a2an…01n-1maxlenndatacount順序棧存儲結(jié)構(gòu)132.2順序棧由此而得到類stack的完整描述。封裝類:

classstack{public:stack();Boolempty()const;Boolfull()const;error_codeget_top(elementtype&x)const;error_codepush(constelementtypex);error_codepop();private:intcount;elementtypedata[maxlen];……//定義其它成員};

這是起什么作用的？作用是什么？142.2順序棧2.2.2運算實現(xiàn)：即類class的各函數(shù)成員的具體實現(xiàn)。初始化函數(shù)的實現(xiàn)：

stack::stack(){count=0;}…a1a2an…01n-1maxlenndatacount152.2順序棧判斷空的函數(shù)的實現(xiàn)：Boolstack::empty()const{if(count==0)returnTRUE;elsereturnFALSE;}判斷滿的函數(shù)的實現(xiàn)：Boolstack::full()const{if(count==maxlen)returnTRUE;elsereturnFALSE;//等價于：returncount==maxlen;}…a1a2an…01n-1maxlenndatacount162.2順序棧取棧頂元素的實現(xiàn)：error_codestack::get_top(elementtype&x)const{if(empty())returnunderflow;else{x=data[count-1];returnsuccess;}}…a1a2an…01n-1maxlenndatacount172.2順序棧入棧的實現(xiàn)：

error_codestack::push(constelementtypex){if(full())returnoverflow;data[count]=x;count++;returnsuccess;}…a1a2an…01n-1maxlenndatacount182.2順序棧出棧的實現(xiàn)

error_codestack::pop(){if(empty())returnunderflow;count--;returnsuccess;

}算法分析：時間性能全部是O(1)

其他方面的性能：空間的分配？。。?！璦1a2an…01n-1maxlenndatacount192.3棧的應(yīng)用表達(dá)式的計算以表達(dá)式12+5*(2+3)*6/2-4的計算過程的實現(xiàn)為例來討論棧結(jié)構(gòu)在實現(xiàn)對任意輸入的通用表達(dá)式的計算中的作用#12+5*(2+3)*6/2-4#開始時，指向第一個位置，準(zhǔn)備讀入，此時的兩個棧均為空。CurrentS=‘#’#12+5*(2+3)*6/2-4#CurrentS=‘12’由于‘#’是第一個算符，因而自動進(jìn)棧。讀到操作數(shù)（12）自動進(jìn)棧。12#202.3棧的應(yīng)用棧頂算符‘#’比當(dāng)前運算符‘＋’優(yōu)先級低，故算符‘＋’要入棧#12+5*(2+3)*6/2-4##

12+#12+5*(2+3)*6/2-4#CurrentS=‘＋’依次讀入5、×、（、2和＋后，棧頂算符‘（’比當(dāng)前算符‘＋’優(yōu)先級低，故‘＋’要入棧+#12CurrentS=‘＋’52X(3+212.3棧的應(yīng)用#12+5*(2+3)*6/2-4#

CurrentS=‘)’(X+#512棧頂算符‘＋’比當(dāng)前運算符‘）’優(yōu)先級高，故要執(zhí)行其運算2+3并入棧#12+5*(2+3)*6/2-4#CurrentS=‘)’X+#512棧頂算符‘（’與當(dāng)前運算符‘）’相對應(yīng)，故要出棧，一同釋放32+5(222.3棧的應(yīng)用#12+5*(2+3)*6/2-4#

CurrentS=‘X’+#12棧頂算符‘×’比當(dāng)前運算符‘×’優(yōu)先運算，故要執(zhí)行運算5*5并入棧#12+5*(2+3)*6/2-4#CurrentS=‘X’+#12棧頂算符‘＋’比當(dāng)前運算符‘×’優(yōu)先級低，故‘×’要入棧X5525X6232.3棧的應(yīng)用#12+5*(2+3)*6/2-4#

CurrentS=‘/

’+#12棧頂算符‘×’比當(dāng)前運算符‘/’優(yōu)先運算，故要執(zhí)行‘×’運算25*6并入棧#12+5*(2+3)*6/2-4#CurrentS=‘-’+#12棧頂算符‘/’比當(dāng)前運算符‘－’優(yōu)先級高，故要執(zhí)行‘/’運算150/2并入棧X625/1502#12+5*(2+3)*6/2-4#CurrentS=‘-

’#12棧頂算符‘＋’比當(dāng)前運算符‘－’優(yōu)先，故執(zhí)行‘＋’運算12+75并入棧75+242.3棧的應(yīng)用#12+5*(2+3)*6/2-4#

CurrentS=‘#’

#87棧頂算符‘－