Posted on 2012-08-01 16:51
C小加 閱讀(7623)
評論(1) 編輯 收藏 引用 所屬分類:
數據結構和算法
基本數據結構：棧（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