數據結構與演算法—棧詳解(看完面試考試再也不怕了)
- 2019 年 10 月 6 日
- 筆記
什麼是棧
百度百科上，棧是這麼定義的：
- 棧（stack）又名
堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
稍微介紹一下關鍵名詞：
- 運算受限：也就是這個表你不能隨便的刪除插入。只能按照它的規則進行插入刪除。比如棧就只能在一端就行插入和刪除。同樣，隊列也是運算受限，只能在兩天操作。
- 線性表：棧也是一種線性表，前面詳細介紹過線性表，它表達的是一種數據的邏輯關係。也就是在棧內各個元素是相鄰的。當然在具體實現上也分
數組和鏈表實現，他們的物理存儲結構不同。但是邏輯結構(實現的目的)相同。 - 棧頂棧底： 這個描述是偏向於邏輯上的內容，因為大家知道
數組在末尾插入刪除更容易，而單鏈表通常在頭插入刪除更容易。所以數組可以用末尾做棧頂，而鏈表可以頭做棧頂。
棧的應用：
- 棧的應用廣泛，比如你的程式執行查看調用堆棧、加減運算、甚至在搜索演算法中dfs，替代遞歸等等。所以棧也是必須掌握的一門數據結構。很多規範也是棧，比如上圖放書拿書一樣！
設計與介紹
這裡我們介紹數組實現的棧和鏈表實現的棧。
數組實現
結構設計
- 對於數組來說，我們模擬棧的過程很簡單，因為棧是
後進先出，我們很容易在數組的末尾進行插入和刪除。所以我們選定末尾為棧頂。所以對於一個棧所需要的基礎元素是 一個data數組和一個top(int)表示棧頂位置。 - 那麼初始化以及構造的函數程式碼為：
private T data[]; private int top; public seqStack() { data=(T[]) new Object[10]; top=-1; } public seqStack(int maxsize) { data=(T[]) new Object[maxsize]; top=-1; }
push插入
棧的核心操作之一push：入棧操作。
- 如果top<數組長度-1。入棧。
top++;a[top]=value; - 如果top==數組長度-1；棧滿。
pop彈出並返回首位
- 如果top>=0,棧不為空，可以彈出。
return data[top--]; - 如下圖，本來棧為1，2，3，4（棧頂），執行pop操作。top變為3的位置並且返回4；
其他操作
- 其他例如peek操作時返回棧頂
不彈出.所以只需滿足題意時候return data[top]即可。
鏈表實現
有數組實現，鏈表當然也能實現。對於棧的運算。大致可以分為兩種思路：
- 像數組那樣在尾部插入刪除。大家都知道鏈表效率
低在查詢。而查詢到尾部效率很低。而我們就算用了尾指針，可以解決尾部插入效率。但是依然無法解決刪除效率(刪除需要找到前節點).還需要雙向鏈表。前面雖然詳細介紹過雙向鏈表，但是這樣未免太複雜！ - 所以我們採用帶頭節點的單鏈表在頭部插入刪除，把頭部當中棧頂，這樣精了很多。插入直接在頭節點後插入。而刪除也直接刪除頭節點後第一個元素即可。
結構設計
長話短說，短話不說。直接上程式碼就懂。 鏈表的節點：
static class node<T> { T data; node next; public node() { } public node(T value) { this.data=value; } }
基本結構：
public class lisStack <T>{ int length; node<T> head;//頭節點 public lisStack() { head=new node<>(); length=0; } //其他方法 }
push插入
與單鏈表頭插入一致，如果不太了解請先看筆者隊線性表介紹的。
和數組形成的棧有個區別。就是理論上棧沒有大小限制(不突破記憶體系統限制)。不需要考慮是否越界。
- 節點
team入棧 - 空鏈表入棧
head.next=team; - 非空入棧
team.next=head.next;head.next=team;
pop彈出
與單鏈表頭刪除一致，如果不太了解請先看筆者隊線性表介紹的。
和數組同樣需要判斷是否為空。
- 節點
team出棧 - head指向team後驅節點。
不需要考慮鏈表是否為1個節點。如果為1個節點，team.next=null.執行完畢head.next=null。變為空，滿足條件。
其他操作
- 其他例如peek操作時返回棧頂
不彈出.所以只需判空滿足題意時候return head.next.data即可。而length你可以遍歷鏈表返回長度，也可以動態設置(本文採取)跟隨棧長變化。其他操作直接看api。
實現程式碼
數組實現
package 隊棧; public class seqStack<T> { private T data[]; private int top; public seqStack() { data=(T[]) new Object[10]; top=-1; } public seqStack(int maxsize) { data=(T[]) new Object[maxsize]; top=-1; } boolean isEmpty() { return top==-1; } int length() { return top+1; } boolean push(T value) throws Exception//壓入棧 { if(top+1>data.length-1) { throw new Exception("棧已滿"); } else { data[++top]=value; return true; } } T peek() throws Exception//返回棧頂元素不移除 { if(!isEmpty()) { return data[top]; } else { throw new Exception("棧為空"); } } T pop() throws Exception { if(isEmpty()) { throw new Exception("棧為空"); } else { return data[top--]; } } public String toString() { if(top==-1) { return ""; } else { String va=""; for(int i=top;i>=0;i--) { va+=data[i]+" "; } return va; } } }
鏈表實現
package 隊棧; public class lisStack <T>{ static class node<T> { T data; node next; public node() { } public node(T value) { this.data=value; } } int length; node<T> head;//頭節點 public lisStack() { head=new node<>(); length=0; } boolean isEmpty() { return head.next==null; } int length() { return length; } public void push(T value) {//近棧 node<T> team=new node<T>(value); if(length==0) { head.next=team; } else { team.next=head.next; head.next=team;} length++; } public T peek() throws Exception { if(length==0) {throw new Exception("鏈表為空");} else {//刪除 return (T) head.next.data; } } public T pop() throws Exception {//出棧 if(length==0) {throw new Exception("鏈表為空");} else {//刪除 T value=(T) head.next.data; head.next=head.next.next;//va.next length--; return value; } } public String toString(){ if(length==0) {return "";} else { String va=""; node team=head.next; while(team!=null) { va+=team.data+" "; team=team.next; } return va; } } }
測試
總結
- 棧的邏輯比較
簡單。很容易理解，實現起來也相對容易。但是要注意數組情況的界限問題。 後面將介紹隊列，相比棧，隊列內容更豐富一些。難度也稍大一些。- 如果有
不好需要改進還請指出！
