基本數(shù)據(jù)結(jié)構(gòu)：棧（stack）
作者：C小加 更新時間：2012-8-1
棧（stack）是限制插入和刪除只能在一個位置上進(jìn)行的線性表，該位置在表的末端，叫做棧頂。添加元素只能在尾節(jié)點(diǎn)后添加，刪除元素只能刪除尾節(jié)點(diǎn)，查看節(jié)點(diǎn)也只能查看尾節(jié)點(diǎn)。添加、刪除、查看依次為入棧（push）、出棧（pop）、棧頂節(jié)點(diǎn)（top）。形象的說，棧是一個先進(jìn)后出（LIFO）表，先進(jìn)去的節(jié)點(diǎn)要等到后邊進(jìn)去的節(jié)點(diǎn)出來才能出來。
如圖1，是一個棧的形象圖，top指針指向的是棧頂節(jié)點(diǎn)，所以我們可以通過top訪問到2節(jié)點(diǎn)，但是0和1節(jié)點(diǎn)由于先于2進(jìn)入這個表，所以是不可見的。如果把0節(jié)點(diǎn)當(dāng)做頭節(jié)點(diǎn)，2節(jié)點(diǎn)當(dāng)做尾節(jié)點(diǎn)，那么棧限制了訪問權(quán)限，只可以訪問尾節(jié)點(diǎn)。
如圖2，當(dāng)添加一個節(jié)點(diǎn)3的時候，只能在棧頂節(jié)點(diǎn)，也就是尾節(jié)點(diǎn)后添加，這樣3節(jié)點(diǎn)變成了棧頂，2節(jié)點(diǎn)變成了不可見節(jié)點(diǎn)，訪問的時候只能訪問到3節(jié)點(diǎn)。入棧時限制了插入地址，只能在棧頂添加節(jié)點(diǎn)。
當(dāng)我們執(zhí)行出棧的命令時，圖2的棧頂元素是3節(jié)點(diǎn)，刪除的時候只能允許刪除棧頂?shù)脑兀@樣子3節(jié)點(diǎn)被刪除，top指向刪除后的棧頂2節(jié)點(diǎn)，如圖3所示。
棧有兩種是實現(xiàn)結(jié)構(gòu)，一種是順序存儲結(jié)構(gòu)，也就是利用數(shù)組實現(xiàn)，一種是鏈?zhǔn)酱鎯Y(jié)構(gòu)，可以用單鏈表實現(xiàn)。數(shù)組實現(xiàn)棧很簡單，用一個下標(biāo)標(biāo)記top來表示棧頂，top==-1時，棧空，top==0時，表示棧里只有一個元素，通過訪問top為下標(biāo)的數(shù)組元素即可。出棧top自減，入棧top自加就OK了。
單鏈表實現(xiàn)棧要比單鏈表的實現(xiàn)簡單點(diǎn)。我們通過在表的尾端插入來實現(xiàn)push，通過刪除尾節(jié)點(diǎn)來實現(xiàn)pop，獲取尾節(jié)點(diǎn)的元素來表示top。我修改了鏈表那一章的單鏈表代碼，把頭節(jié)點(diǎn)當(dāng)做棧頂節(jié)點(diǎn)，實現(xiàn)了一個簡單的棧模板，僅供學(xué)習(xí)所用。代碼會不定時更新。代碼下載
代碼如下：
template<class T>
class stackNode
{
public:
stackNode():next(NULL){}
T data;//值
stackNode* next;//指向下一個節(jié)點(diǎn)的指針
};
template<class T>
class mystack
{
private:
unsigned int stacklength;
stackNode<T>* node;//臨時節(jié)點(diǎn)
stackNode<T>* headnode;//尾結(jié)點(diǎn)
public:
mystack();//初始化
unsigned int length();//棧元素的個數(shù)
void push(T x);//入棧
bool isEmpty();//判斷棧是否為空
void pop();//出棧
T top();//獲得棧頂元素
void clear();//清空棧
};
template<class T>
mystack<T>::mystack()
{
node=NULL;
headnode=NULL;
stacklength=0;
}
template<class T>
inline unsigned int mystack<T>::length(){return stacklength;}
template<class T>
void mystack<T>::push(T x)
{
node=new stackNode<T>();
node->data=x;
node->next=headnode;//把node變成頭節(jié)點(diǎn)
headnode=node;
++stacklength;
}
template<class T>
bool mystack<T>::isEmpty()
{
return stacklength==0;
}
template<class T>
void mystack<T>::pop()
{
if(isEmpty()) return;
node=headnode;
headnode=headnode->next;//頭節(jié)點(diǎn)變成它的下一個節(jié)點(diǎn)
delete(node);//刪除頭節(jié)點(diǎn)
--stacklength;
}
template<class T>
T mystack<T>::top()
{
if(!isEmpty())
return headnode->data;
}
template<class T>
void mystack<T>::clear()
{
while(headnode!=NULL)
{
node=headnode;
headnode=headnode->next;
delete(node);
}
node=NULL;
headnode=NULL;
stacklength=0;
}
很清楚，除了clear函數(shù)外，所有的方法的時間復(fù)雜度都是O(1)。這種實現(xiàn)方式的缺點(diǎn)在于對new和delete的調(diào)用的開銷是昂貴的，所以采用數(shù)組的方式實現(xiàn)會更好一點(diǎn)。
棧的應(yīng)用
使用棧的時候一般不用自己重新去寫，因為STL給我們實現(xiàn)了一個很安全的棧，可以放心去使用。也可以用數(shù)組模擬一個，很簡單。
編譯器調(diào)用函數(shù)就用了棧結(jié)構(gòu)，當(dāng)?shù)谝粋€函數(shù)還沒執(zhí)行完畢，調(diào)用第二個函數(shù)的時候，編譯器就會把第一個函數(shù)壓棧，第二個函數(shù)調(diào)用完畢的時候，就會取棧頂函數(shù)，也就是第一個函數(shù)繼續(xù)執(zhí)行。
平衡符號 http://acm.nyist.net/JudgeOnline/problem.php?pid=2
中綴轉(zhuǎn)后綴 http://acm.nyist.net/JudgeOnline/problem.php?pid=467
后綴試求值 http://acm.nyist.net/JudgeOnline/problem.php?pid=35
poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=3250
poj 1363 http://acm.pku.edu.cn/JudgeOnline/problem?id=1363
poj 1208 http://acm.pku.edu.cn/JudgeOnline/problem?id=1208
poj 1686 http://acm.pku.edu.cn/JudgeOnline/problem?id=1686
poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=2045
hdu 1022 http://acm.hdu.edu.cn/showproblem.php?pid=1022