簡介
什么是棧？棧是一種只運行從一端插入和刪除數(shù)據(jù)的線性表。一種形象的表示就像我們往一個大小受限的籮筐里放磚頭判哥，我們只能從從口放進去也只能從口取出來，而且是順序的后進先出碉考，不能從中間挑一個拿出來塌计。棧主要有兩個操作，一個入棧一個出棧侯谁。棧的實現(xiàn)方式可以用鏈表也可以用數(shù)組锌仅，我們將用數(shù)組來實現(xiàn)的棧叫做順序棧，用鏈表實現(xiàn)的棧叫做鏈式棧墙贱。
實現(xiàn)
基于鏈表的鏈式棧java代碼實現(xiàn)：
#Node.java
public class Node {
private int data;
public Node next;
public Node(int data){
this.data=data;
}
}
#linkStack.java
public class LinkStack {
Node top=null;
public boolean isEmpty(){
return top==null;
}
//入棧
public void push(int data){
Node newNode=new Node(data);
newNode.next=top;
top=newNode;
}
//出棧并移除棧頂
public Node pop(){
if (isEmpty()){
return null;
}
Node d=top;
top=top.next;
return d;
}
//進返回棧頂热芹，不移除
public Node peek(){
if (isEmpty()){
return null;
}
return top;
}
}
對于數(shù)組方式的實現(xiàn)基本差別不大，這里就不寫了惨撇。接下來探討下棧操作的算法復雜度是多少伊脓。由于入棧和出棧操作都只有一個操作，所以時間復雜度為O（1）;那么對于空間復雜度呢魁衙？一個存儲了n個數(shù)據(jù)的棧丽旅，空間復雜度是不是O（n）呢？其實不是纺棺，因為棧的兩個操作入棧和出棧榄笙，運行時都只需一個到兩個臨時變量來做存儲，我們在分析算法空間復雜度的時候是不需要將存儲數(shù)據(jù)本來就需要的那些空間算進了的祷蝌，所以空間復雜度也為O（1）茅撞。
動態(tài)擴容
上面提到的兩種實現(xiàn)方法的棧有什么不一樣呢？其實數(shù)組是一種固定大小的數(shù)據(jù)結構巨朦，正是由于這個特性米丘，使得數(shù)組實現(xiàn)的鏈表所容納的數(shù)據(jù)是受限的，當棧滿了之后我們就無法繼續(xù)添加數(shù)據(jù)了糊啡，而鏈表就不受這個限制拄查，那么是不是就是說鏈表實現(xiàn)的棧比數(shù)組更好，我們應該不使用數(shù)組實現(xiàn)棧呢棚蓄？其實不是的堕扶，鏈表實現(xiàn)的棧由于需要存儲一個next指針，所以它每個節(jié)點都會比數(shù)組多消耗更多的內存空間梭依。當然我們前面有些關于數(shù)組的文章稍算，里面有提到數(shù)組的動態(tài)擴容是怎么實現(xiàn)，那么既然數(shù)組可以實現(xiàn)動態(tài)擴容役拴，那么用數(shù)組實現(xiàn)的棧同樣也可以做到動態(tài)擴容糊探，這樣就不會再有空間受限的問題了。當然擴容也同樣會帶來新的問題，就是在擴容時復雜度提高到O（n）科平。
動態(tài)擴容算法復雜度分析：
對于出棧操作褥紫，由于不會涉及到數(shù)據(jù)的搬移，所以復雜度無論何時都為O（1）瞪慧，那么入棧操作髓考，當空間足夠多時，也不需要數(shù)據(jù)搬移汞贸，所以復雜度也為O（1）绳军，但是當空間不足，需要擴容時矢腻，由于數(shù)組擴容需要將原有的數(shù)據(jù)搬移到新創(chuàng)建的數(shù)組中门驾，這時復雜度就變?yōu)榱薕（n），所以對于入棧操作多柑，最好情況時間復雜度為O（1）奶是，最壞為O（n），那么平靜是多少呢竣灌？前面的文章有介紹過平均時間復雜度如何求聂沙。我們會用到攤還分析法。我們這里約定每次擴容都為原數(shù)組大小的2倍初嘹，當前滿棧為k個數(shù)據(jù)及汉，并且不涉及出棧操作，所以達到擴容條件時進行了k此O（1）的入棧操作屯烦，而后會進行k個數(shù)據(jù)的數(shù)組內存搬移操作坷随，將k個搬移操作均攤到每次入棧操作，就能得到均攤時間復雜度為O（1）驻龟。
棧的應用
我們寫代碼時函數(shù)的調用就是用類似棧的數(shù)據(jù)結構來存儲調用的函數(shù)的温眉，這里我們來分析一個用棧來實現(xiàn)表達式求值的一個例子。用計算機的思維來求解：1+2*3-4這個表達式翁狐，
實際上計算機是通過兩個棧來實現(xiàn)這些運算操作的类溢，其中一個棧用來保存操作的數(shù)，另一個用來保存運算符露懒。它先從左到右遍歷表達式闯冷，當遇到數(shù)字就直接壓入操作數(shù)棧，當遇到云算符隐锭，就與云算符棧頂元素進行比較窃躲，如果當前運算符比棧頂運算符的優(yōu)先級高，就將當前運算符壓入運算符棧棧頂钦睡，如果當前運算符比棧頂運算符優(yōu)先級低或者相等，就從數(shù)字棧取出兩個操作數(shù)來進行運算，運算結果壓入數(shù)字棧頂荞怒，然后繼續(xù)與運算符棧棧頂進行比較洒琢，進行跟前面一樣的操作，知道整個表達式運算完成褐桌。
關于棧的學習就先到這里了衰抑。
