基本數據結構：棧stack）
作者：C小加 更新時間：2012-8-1
棧stack）是限制插入和刪除只能在一個位置上進行的線性表，該位置在表的末端，叫做棧頂。添加元素只能在尾節點後添加，刪除元素只能刪除尾節點，查看節點也只能查看尾節點。添加、刪除、查看依次為入棧push）、出棧pop）、棧頂節點top）。形象的說，棧是一個先進後出LIFO）表，先進去的節點要等到後邊進去的節點出來才能出來。
如圖1，是一個棧的形象圖，top指針指向的是棧頂節點，所以我們可以通過top訪問到2節點，但是0和1節點由於先於2進入這個表，所以是不可見的。如果把0節點當做頭節點，2節點當做尾節點，那麼棧限制了訪問權限，只可以訪問尾節點。
如圖2，當添加一個節點3的時候，只能在棧頂節點，也就是尾節點後添加，這樣3節點變成了棧頂，2節點變成了不可見節點，訪問的時候只能訪問到3節點。入棧時限制了插入地址，只能在棧頂添加節點。
當我們執行出棧的命令時，圖2的棧頂元素是3節點，刪除的時候只能允許刪除棧頂的元素，這樣子3節點被刪除，top指向刪除後的棧頂2節點，如圖3所示。
棧有兩種是實現結構，一種是順序存儲結構，也就是利用數組實現，一種是鏈式存儲結構，可以用單鏈表實現。數組實現棧很簡單，用一個下標標記top來表示棧頂，top==-1時，棧空，top==0時，表示棧裡只有一個元素，通過訪問top為下標的數組元素即可。出棧top自減，入棧top自加就OK了。
單鏈表實現棧要比單鏈表的實現簡單點。我們通過在表的尾端插入來實現push，通過刪除尾節點來實現pop，獲取尾節點的元素來表示top。我修改了鏈表那一章的單鏈表代碼，把頭節點當做棧頂節點，實現了一個簡單的棧模板，僅供學習所用。代碼會不定時更新。
代碼如下：
- template<class T>
- class stackNode
- {
- public:
- stackNode():next(NULL){}
- T data;//值
- stackNode* next;//指向下一個節點的指針
- };
- template<class T>
- class mystack
- {
- private:
- unsigned int stacklength;
- stackNode<T>* node;//臨時節點
- stackNode<T>* headnode;//尾結點
- public:
- mystack();//初始化
- unsigned int length();//棧元素的個數
- 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變成頭節點
- 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;//頭節點變成它的下一個節點
- delete(node);//刪除頭節點
- --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函數外，所有的方法的時間復雜度都是O(1)。這種實現方式的缺點在於對new和delete的調用的開銷是昂貴的，所以采用數組的方式實現會更好一點。
棧的應用
使用棧的時候一般不用自己重新去寫，因為STL給我們實現了一個很安全的棧，可以放心去使用。也可以用數組模擬一個，很簡單。
編譯器調用函數就用了棧結構，當第一個函數還沒執行完畢，調用第二個函數的時候，編譯器就會把第一個函數壓棧，第二個函數調用完畢的時候，就會取棧頂函數，也就是第一個函數繼續執行。
平衡符號 http://acm.nyist.net/JudgeOnline/problem.php?pid=2
中綴轉後綴 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
本文出自 “C小加&SunRise” 博客，請務必保留此出處http://lwxcy.blog.51cto.com/2467073/950320
