本文更新于個(gè)人博客Burnside Blog
總的來(lái)說(shuō)玩徊，棧（Stack）是一種應(yīng)用十分廣泛的線性數(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è)棧脚作，或銷毀一個(gè)棧，我們只考慮一個(gè)靜態(tài)的棧的功能實(shí)現(xiàn)缔刹。棧中的元素可以是任何的用戶自定義類型球涛，為了方便起見(jiàn)，我們假設(shè)元素的類型為int桨螺，如需要?jiǎng)e的類型宾符，只需要靈活處理即可。接下來(lái)我們申請(qǐng)一塊長(zhǎng)度為MaxSize的連續(xù)內(nèi)存來(lái)存儲(chǔ)這個(gè)棧灭翔，這時(shí)它又被稱為順序棧魏烫。
int Stack[MaxSize];
這樣我們就成功獲得了一個(gè)自己的棧「蜗洌考慮往棧中插入元素或刪除元素哄褒，所改變的只有最頂部的元素距棧底的距離，這里的距離表示的是元素個(gè)數(shù)煌张，我們把這個(gè)頂部稱為棧頂呐赡，可以用一個(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ì)使以后的操作訪問(wèn)到非法位置仰禀，因此，請(qǐng)務(wù)必確保棧是非空的蚕愤，再使用pop()答恶，為了方便確保棧是否為空，我們引入一個(gè)新的函數(shù)萍诱。
3悬嗓、查詢棧是否為空
bool empty(){
? ? return top==-1?true:false;
}
很簡(jiǎn)單，棧為空的標(biāo)志為top等于-1裕坊，直接調(diào)用即可包竹。
4、查詢椉現(xiàn)在的大兄芟埂（size）
int size(){
? ? return top+1;
}
也很簡(jiǎn)單，棧的大小為top+1饵蒂。
5声诸、查詢棧頂元素
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)綏９常疚闹胁辉偕婕胺倌樱唧w的實(shí)現(xiàn)思想與上述六個(gè)函數(shù)一樣。
棧有很多實(shí)際的應(yīng)用漓骚，其中常見(jiàn)的有：把一個(gè)十進(jìn)制數(shù)拆分為二進(jìn)制蝌衔，查詢一個(gè)括號(hào)序列是否能夠匹配，計(jì)算表達(dá)式的值等蝌蹂。我們主要來(lái)寫(xiě)查詢括號(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)賽中常用，因此不在本文中描述睡汹。
