3.1 棧

3.1.1 棧的基本概念

棧是一種特殊的線性表，其特殊性體現在元素插入和刪除運算上，它的插入和刪除運算僅限定在表的某一端進行，不能在表中間和另一端進行。允許進行插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的插入操作稱為進棧（或入棧），刪除操作稱為出棧（或退棧）。處于棧頂位置的數據元素稱為棧頂元素。不含任何數據元素的棧稱為空棧。

正是這種受限的元素插入和刪除運算，使得棧表現出先進后出或者后進先出的特點。舉一個例子進行說明，假設有一個很窄的死胡同，胡同里能容納若干人，但每次只能容許一個人進出。現有5個人，分別編號為①～⑤，按編號的順序依次進入此死胡同，如圖3.1（a）所示。此時若編號為④的人要退出死胡同，必須等⑤退出后才可以。若①要退出，則必須等到⑤、④、③、②依次都退出后才行，如圖3.1（b）所示。這里人進出死胡同的原則是先進去的后出來。

在該例中，死胡同就看作是一個棧，棧頂相當于死胡同口，棧底相當于死胡同的另一端，進、出死胡同可看作進棧、出棧操作。插入棧的示意圖如圖3.2所示。

棧的基本運算主要包括以下6種。

（1）初始化棧InitStack（st）：建立一個空棧st。

（2）銷毀棧DestroyStack（st）：釋放棧st占用的內存空間。

（3）進棧Push（st，x）：將元素x插入棧st中，使x成為棧st的棧頂元素。

（4）出棧Pop（st，x）：當棧st不空時，將棧頂元素賦給x，并從棧中刪除當前棧頂元素。

（5）取棧頂元素GetTop（st，x）：若棧st不空，取棧頂元素x并返回1；否則返回0。

（6）判斷棧空StackEmpty（st）：判斷棧st是否為空棧。

包含基本運算的棧如圖3.3所示，其中，op1～op6表示上述6個基本運算。

【例3.1】設一個棧的輸入序列為a、b、c、d，借助一個棧（假設棧大小足夠大）所得到的出棧序列不可能是________。

A．a、b、c、d

B．b、d、c、a

C．a、c、d、b

D．d、a、b、c

解：a、b、c、d序列經過棧的情況如圖3.4所示，根據棧的特點，很容易得出d、a、b、c是不可能的，因為d先出棧，說明a、b、c均已在棧中，按照進棧順序，從棧頂到棧底的順序應為c、b、a，出棧的順序只能是d、c、b、a。所以不可能的出棧序列是D。

【例3.2】已知一個棧的進棧序列是1，2，3，…，n，其出棧序列是p1，p2，…，pn，若p1=n，則pi的值為________。

A．i

B．n—i

C．n—i+1

D．不確定

解：p1=n，則出棧序列是唯一的，即為n，n—1，…，2，1，由此推出pi=n—i+1。本題答案為C。

【例3.3】元素a、b、c、d、e依次進入初始為空的棧中，假設棧大小足夠大。若元素進棧后可停留、可立即出棧，直到所有的元素都出棧，則所有可能的出棧序列中，以元素d開頭的出棧序列個數是________。

A．3

B．4

C．5

D．6

解：若元素d第一個出棧，a、b、c均在棧中，從棧頂到棧底的順序應為c、b、a，如圖3.5所示，此后合法的棧操作如下。

（1）e進棧，e出棧，c出棧，b出棧，a出棧，得到的出棧序列decba。

（2）c出棧，e進棧，e出棧，b出棧，a出棧，得到的出棧序列dceba。

（3）c出棧，b出棧，e進棧，e出棧，a出棧，得到的出棧序列dcbea。

（4）c出棧，b出棧，a出棧，e進棧，e出棧，得到的出棧序列dcbae。

以元素d開頭的出棧序列個數為4，本題答案為B。

3.1.2 棧的順序存儲結構

棧是一種特殊的線性表，和線性表存儲結構類似，棧也有兩種存儲結構：順序存儲結構和鏈式存儲結構。

棧的順序存儲結構稱為順序棧。順序棧通常由一個一維數組data和一個記錄棧頂元素位置的變量top組成。習慣上將棧底放在數組下標小的那端，棧頂元素由棧頂指針top所指向。順序棧類型聲明如下。

在上述順序棧定義中，ElemType為棧元素的數據類型，MaxSize為一個常量，表示data數組中最多可放的元素個數，data元素的下標范圍為0～MaxSize—1。當top=—1時表示棧空；當top=MaxSize—1時表示棧滿。

圖3.6說明了順序棧st的幾種狀態（假設MaxSize=5）。圖3.6（a）表示順序棧為棧空，這也是初始化運算得到的結果。此時棧頂指針top=—1。如果做出棧運算，則會“下溢出”。

圖3.6（b）表示棧中只含一個元素a，在圖3.6（a）的基礎上用進棧運算Push（st，'a'），可以得到這種狀態。此時棧頂指針top=0。

圖3.6（c）表示在圖3.6（b）基礎上又有兩個元素b、c先后進棧，此時棧頂指針top=2。

圖3.6（d）表示在圖3.6（c）狀態下執行一次Pop（st，x）運算得到。此時棧頂指針top=1。故b為當前的棧頂元素。

圖3.6（e）表示在圖3.6（d）狀態下執行兩次Pop（st，x）運算得到。此時棧頂指針top=—1，又變成棧空狀態。

歸納起來，對于順序棧st，其初始時置st.top=—1，它的4個要素如下。

（1）棧空條件：st.top==—1。

（2）棧滿條件：st.top==MaxSize—1。

（3）元素x進棧操作：st.top++；將元素x放在st.data[st.top]中。

（4）出棧元素x操作：取出棧元素x=st.data[st.top]；st.top——。

順序棧的基本運算算法如下。

1．初始化棧運算算法

其主要操作是設定棧頂指針top為—1，對應的算法如下。

2．銷毀棧運算算法

這里順序棧的內存空間是由系統自動分配的，在不再需要時由系統自動釋放其空間。對應的算法如下。

      void DestroyStack(SqStack st)
      {  }

3．進棧運算算法

其主要操作是：棧頂指針加1，將進棧元素放在棧頂處。對應的算法如下。

4．出棧運算算法

其主要操作是：先將棧頂元素取出，然后將棧頂指針減1。對應的算法如下。

5．取棧頂元素運算算法

其主要操作是：將棧頂指針top處的元素取出賦給變量x，top保持不動。對應的算法如下。

6．判斷棧空運算算法

其主要操作是：若棧為空（top==—1）則返回值1，否則返回值0。對應的算法如下。

提示：將順序棧類型聲明和棧基本運算函數存放在SqStack.cpp文件中。

當順序棧的基本運算函數設計好后，給出以下程序調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會順序棧的各種運算的實現過程。

上述程序的執行結果如圖3.7所示。

【例3.4】若一個棧用數組data[1..n]存儲（n為一個大于2的正整數），初始棧頂指針top為n+1，則以下元素x進棧的正確操作是________。

A．top++；data[top]=x；

B．data[top]=x；top++；

C．top——；data[top]=x；

D．data[top]=x；top——；

解：棧元素是向一端伸展的，即從棧底向棧頂方向伸展。這里初始棧頂指針top為n+1，說明data[n]端作為棧底，在進棧時top應遞減，由于不存在data[n+1]的元素，所以在進棧時應先將top遞減，再將x放在top處。本題答案為C。

3.1.3 棧的鏈式存儲結構

棧的鏈式存儲結構是采用某種鏈表結構，棧的鏈式存儲結構簡稱為鏈棧。這里采用單鏈表作為鏈棧，如圖3.8所示，該單鏈表是不帶頭結點的，通過首結點指針ls唯一標識整個單鏈表。同時，單鏈表的首結點就是鏈棧的棧頂結點（圖中首結點值為an表示最近進棧的元素是an），所以ls也作為棧頂指針，棧中的其他結點通過next域鏈接起來，棧底結點的next域為NULL。因鏈棧本身沒有容量限制，所以不必考慮棧滿的情況，這是鏈棧相比順序棧的一個優點。

鏈棧的類型定義如下。

歸納起來，鏈棧ls初始時ls=NULL，其4個要素如下。

（1）棧空條件：ls==NULL。

（2）棧滿條件：不考慮。

（3）元素x進棧操作：創建存放元素x的結點p，將其插入到棧頂位置上。

（4）出棧元素x操作：置x為棧頂結點的data域，并刪除該結點。

鏈棧的基本運算算法如下。

1．初始化棧運算算法

其主要操作是：置s為NULL標識棧為空棧。對應的算法如下。

2．銷毀棧運算算法

鏈棧的所有結點空間都是通過malloc函數分配的，在不再需要時需通過free函數釋放所有結點的空間，與單鏈表銷毀算法類似，只是這里鏈棧是不帶頭結點的。對應的算法如下。

3．進棧運算算法

其主要操作是：先創建一個新結點p，其data域值為x；然后將該結點插入到開頭作為新的棧頂結點。對應的算法如下。

4．出棧運算算法

其主要操作是：將棧頂結點（即ls所指結點）的data域值賦給x，然后刪除該棧頂結點。對應的算法如下。

說明：盡管鏈棧操作時不考慮上溢出，但仍然需要考慮出棧操作時的下溢出。

5．取棧頂元素運算算法

其主要操作是：將棧頂結點（即ls所指結點）的data域值賦給x。對應的算法如下。

6．判斷棧空運算算法

其主要操作是：若棧為空（即ls==NULL）則返回值1，否則返回值0。對應的算法如下。

      int StackEmpty(LinkStack ? ls)
      {    if(ls==NULL) return 1;
           else return 0;
      }

提示：將鏈棧結點類型聲明和鏈棧基本運算函數存放在LinkStack.cpp文件中。

當鏈棧的基本運算函數設計好后，給出以下程序調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會順序棧的各種運算的實現過程。

上述程序的執行結果如圖3.7所示。

【例3.5】以下各鏈表均不帶有頭結點，其中最不適合用作鏈棧的鏈表是________。

A．只有表尾指針沒有表頭指針的循環單鏈表

B．只有表頭指針沒有表尾指針的循環單鏈表

C．只有表頭指針沒有表尾指針的循環雙鏈表

D．只有表尾指針沒有表頭指針的循環雙鏈表

解：由于各鏈表均不帶有頭結點，這里表頭指針就是首結點指針。采用一種鏈表作為鏈棧時，通常將鏈表首結點處作為棧頂。一個鏈表適不適合作為鏈棧，就看它是否能夠高效地實現棧的基本運算，而棧的主要操作是進棧和出棧。

考慮選項A，只有表尾指針沒有表頭指針的循環單鏈表，假設表尾指針為rear，它指向循環單鏈表的尾結點，如圖3.9所示。元素x進棧的操作是：創建存放x的結點p，將結點p插入在rear結點之后作為棧頂結點，不改變rear；出棧的操作是：刪除rear結點之后的結點。兩種操作的時間復雜度均為O（1）。

考慮選項B，只有表頭指針沒有表尾指針的循環單鏈表，假設表頭指針為first，它指向循環單鏈表的首結點，如圖3.10所示。元素x進棧的操作是：創建存放x的結點p，將結點p插入在first結點之前，即p—>next=first，first=p，但還要將其改變為循環單鏈表，而尾結點需要遍歷所有結點找到，遍歷的時間為O（n），所以進棧操作的時間復雜度為O（n）；出棧的操作是：刪除first結點，刪除后仍然需要將其改變為循環單鏈表，所以出棧操作的時間復雜度為O（n）。兩種操作的時間復雜度均為O（n）。

考慮選項C和D，由于都是循環雙鏈表，可以通過表頭結點直接找到尾結點，在插入和刪除后改為循環雙鏈表的時間均為O（1），所以它們的進棧和出棧操作的時間復雜度都是O（1）。

比較起來，只有表頭指針沒有表尾指針的循環單鏈表作為鏈棧時，進棧和出棧操作的時間性能最差。本題答案為B。

3.1.4 棧的應用示例

在較復雜的數據處理過程中，通常需要保存多個臨時產生的數據，如果先產生的數據后進行處理，那么需要用棧來保存這些數據。本節通過幾個經典示例說明棧的應用方法，并且算法中均采用順序棧，實際上采用鏈棧完全相同。

【例3.6】假設以I和O分別表示進棧和出棧操作，棧的初態和終態均為空，進棧和出棧的操作序列可表示為僅由I和O組成的序列。

（1）下面所示的序列中哪些是合法的？

A．IOIIOIOO

B．IOOIOIIO

C．IIIOIOIO

D．IIIOOIOO

（2）通過對（1）的分析，設計一個算法利用鏈棧的基本運算判定操作序列str是否合法。若合法返回1；否則返回0。

解：（1）A、D均合法，而B、C不合法。因為在B中，先進棧一次，立即出棧兩次，這會造成棧下溢。在C中共進棧5次，出棧3次，棧的終態不為空。

歸納起來，這樣的操作序列是合法的，當且僅當其中所有I的個數與O的個數相等，而且任何前綴中I的個數大于或等于O的個數。

（2）本例用一個順序棧st來判斷操作序列是否合法，其中，str為存放操作序列的字符數組，n為該數組的元素個數。對應的算法如下。

說明：本例的另一種解法是用cnt累計I與O的個數差，cnt從0開始，循環遍歷str，遇到I增1，遇到0減1。cnt小于0時返回0。循環結束后cnt為0則返回1。

【例3.7】回文指的是一個字符串從前面讀和從后面讀都一樣，如＂abcba＂、＂123454321＂都是回文。設計一個算法利用棧判斷一個字符串是否為回文。

解：由于回文是從前到后以及從后到前都是一樣的，所以只要將待判斷的字符串顛倒，然后與原字符串相比較，就可以決定是否回文了。

將字符串str從頭到尾的各個字符依次進棧到順序棧st中，由于棧的特點是后進先出，則從棧頂到棧底的各個字符正好與字符串str從尾到頭的各個字符相同；然后將字符串str從頭到尾的各個字符，依次與從棧頂到棧底的各個字符相比較，如果兩者不相同，則表明str不是回文，在相同時繼續比較；如果相應字符全部匹配，則說明str是回文。對應的算法如下。

【例3.8】設計一個算法，判斷一個可能含有小括號（“（”與“）”、）、中括號（“[”與“]”）和大括號（“{”與“}”）的表達式中各類括號是否匹配。若匹配，則返回1；否則返回0。

解：設置一個順序棧st，定義一個整型flag變量（初始為1）。用i掃描表達式exp，當i＜n并且flag=1時循環：當遇到左括號“（”“[”“{”時，將其進棧；遇到“}”“]”“）”時，出棧字符ch，若出棧失敗（下溢出）或者ch不匹配，則置flag=0退出循環，否則直到exp掃描完畢為止。若棧空并且flag為1則返回1，否則返回0。

例如，對于表達式＂[（]）＂，其括號不匹配，匹配過程如圖3.11（a）所示；對于表達式＂[（）]＂，其括號是匹配的，匹配過程如圖3.11（b）所示。

對應的算法如下。

【例3.9】設計一個算法將一個十進制正整數轉換為相應的二進制數。

解：將十進制正整數轉換成二進制數通常采用除2取余數法（稱為輾轉相除法）。在轉換過程中，二進制數是從低位到高位的次序得到的，這和通常的從高位到低位輸出二進制的次序相反。為此設計一個棧，用于暫時存放每次得到的余數，當轉換過程結束時，退棧所有元素便得到從高位到低位的二進制數。如圖3.12所示是十進制數12轉換為二進制數1100的過程。

對應的算法如下。

設計如下主函數。

本程序的一次執行結果如下。

      輸入一個正整數：120↙
      對應的二進制數：1111000