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