本文更新于個(gè)人博客Burnside Blog
總的來(lái)說(shuō)，棧（Stack）是一種應(yīng)用十分廣泛的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，我們大多數(shù)時(shí)候可以把它理解成一個(gè)杯子，杯子只有一個(gè)口，它既是進(jìn)入的入口，也是退出的出口。的確如此，棧是一種先入后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，它支持插入與刪除兩種操作，且兩個(gè)操作僅可以在一端進(jìn)行。
為了方便起見(jiàn)，我們不使用動(dòng)態(tài)方式生成一個(gè)棧，或銷(xiāo)毀一個(gè)棧，我們只考慮一個(gè)靜態(tài)的棧的功能實(shí)現(xiàn)。棧中的元素可以是任何的用戶(hù)自定義類(lèi)型，為了方便起見(jiàn)，我們假設(shè)元素的類(lèi)型為int，如需要?jiǎng)e的類(lèi)型，只需要靈活處理即可。接下來(lái)我們申請(qǐng)一塊長(zhǎng)度為MaxSize的連續(xù)內(nèi)存來(lái)存儲(chǔ)這個(gè)棧，這時(shí)它又被稱(chēng)為順序棧。
int Stack[MaxSize];
這樣我們就成功獲得了一個(gè)自己的棧?？紤]往棧中插入元素或刪除元素，所改變的只有最頂部的元素距棧底的距離，這里的距離表示的是元素個(gè)數(shù)，我們把這個(gè)頂部稱(chēng)為棧頂，可以用一個(gè)變量top來(lái)維護(hù)，最頂部的元素為棧頂元素，不難發(fā)現(xiàn)，每一次的刪除操作，總是刪除的棧頂元素。
因此，我們會(huì)得到棧的幾個(gè)操作：
1、插入元素
int push(int x){
? ? Stack[++top]=x;
? ? return top;
}
插入一個(gè)元素很簡(jiǎn)單，只需要將棧頂指向數(shù)組內(nèi)的下一個(gè)位置，然后把該位置賦值為要插入的值即可，函數(shù)中的變量x即為需要插入的值，top為棧頂，此函數(shù)返回值為插入后的棧頂。注意，當(dāng)棧為空的時(shí)候，變量top應(yīng)當(dāng)?shù)扔?1。
2、刪除元素
int pop(){
? ? return --top;
}
刪除一個(gè)元素更簡(jiǎn)單，只需要將棧頂下移一個(gè)就可以。注意，原來(lái)的棧頂元素不需要做任何的改變，因?yàn)橹灰迦氲竭@個(gè)位置，這個(gè)位置就會(huì)立馬被賦值上被插入的新的元素，所以只需要讓棧頂下移即可，而并不需要改變棧頂元素的值。此函數(shù)返回的是刪除后的棧頂。要注意，這里有一個(gè)潛在的問(wèn)題，如果這個(gè)時(shí)候棧已空，但仍然調(diào)用了pop()，可能會(huì)使以后的操作訪(fǎng)問(wèn)到非法位置，因此，請(qǐng)務(wù)必確保棧是非空的，再使用pop()，為了方便確保棧是否為空，我們引入一個(gè)新的函數(shù)。
3、查詢(xún)棧是否為空
bool empty(){
? ? return top==-1?true:false;
}
很簡(jiǎn)單，棧為空的標(biāo)志為top等于-1，直接調(diào)用即可。
4、查詢(xún)?，F(xiàn)在的大?。╯ize）
int size(){
? ? return top+1;
}
也很簡(jiǎn)單，棧的大小為top+1。
5、查詢(xún)棧頂元素
int top(){
? ? return Stack[top];
}
請(qǐng)注意，請(qǐng)務(wù)必在棧非空的情況下使用該命令。
6、刪除棧內(nèi)的所有元素
void clear(){
? ? while(!empty()) pop();
}
很自然的實(shí)現(xiàn)，當(dāng)棧為非空時(shí)，一直刪除元素就可以了。
以上為棧的所有操作，部分書(shū)中還介紹了鏈?zhǔn)綏?，本文中不再涉及，具體的實(shí)現(xiàn)思想與上述六個(gè)函數(shù)一樣。
棧有很多實(shí)際的應(yīng)用，其中常見(jiàn)的有：把一個(gè)十進(jìn)制數(shù)拆分為二進(jìn)制，查詢(xún)一個(gè)括號(hào)序列是否能夠匹配，計(jì)算表達(dá)式的值等。我們主要來(lái)寫(xiě)查詢(xún)括號(hào)序列是否匹配，剩下兩個(gè)常見(jiàn)功能讀者可以自行完成。
括號(hào)序列，是僅由(與)構(gòu)成的序列，匹配的定義如下：
1. ()是一個(gè)合法匹配。
2. 如果A是一個(gè)合法匹配，則(A)是一個(gè)合法匹配。
3. 如果A和B都是合法匹配，則AB是一個(gè)合法匹配。
不難發(fā)現(xiàn)，()()(())((())())是一個(gè)合法匹配，而(()不是一個(gè)合法匹配。
判斷的過(guò)程也很輕松，我們只需要模擬這個(gè)匹配的過(guò)程就可以了，具體操作步驟如下：
1. 如果當(dāng)前讀取到一個(gè)(，進(jìn)棧，讀取下一位。
2. 如果當(dāng)前讀取到一個(gè))，如果棧非空，取棧頂?shù)挠依ㄌ?hào)與之匹配，讀取下一位；如果?？?，則找不到括號(hào)與之匹配，證明其不合法。
3. 如果讀完了整個(gè)括號(hào)序列?？?，則整個(gè)括號(hào)序列合法，否則不合法。
正確性顯然，不過(guò)多贅述，代碼如下：
#include<iostream>
#include<cstdio>
const int MaxSize=1000;
char Stack[MaxSize];
int top=-1,flag=true;
int main(){
? ? char c;
? ? while((c=getchar())!=EOF){
? ? ? ? if(c=='(') Stack[++top]='(';
? ? ? ? else{
? ? ? ? ? ? if(top==-1){
? ? ? ? ? ? ? ? flag=false;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? top--;
? ? ? ? }
? ? }
? ? if(top!=-1) flag=false;
? ? printf(flag?"legal":"illegal");
? ? return 0;
}
可能會(huì)有人表示輸出總是illegal，因?yàn)樵谝婚_(kāi)始讀的時(shí)候把回車(chē)也讀進(jìn)去了，可以使用文件輸入輸出，最后不換行就可以了，或者可以采用其他的輸入方式。
在某些特殊應(yīng)用中，還會(huì)使用到單調(diào)棧，因?yàn)閮H在競(jìng)賽中常用，因此不在本文中描述。
