數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解

星光閃亮圖書館 2019-09-06

展開全文

什么是棧

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

稍微介紹一下關(guān)鍵名詞：

運算受限：也就是這個表你不能隨便的刪除插入。只能按照它的規(guī)則進行插入刪除。比如棧就只能在一端就行插入和刪除。同樣，隊列也是運算受限，只能在兩天操作。
線性表：棧也是一種線性表，前面詳細介紹過線性表，它表達的是一種數(shù)據(jù)的邏輯關(guān)系。也就是在棧內(nèi)各個元素是相鄰的。當(dāng)然在具體實現(xiàn)上也分數(shù)組和鏈表實現(xiàn)，他們的物理存儲結(jié)構(gòu)不同。但是邏輯結(jié)構(gòu)(實現(xiàn)的目的)相同。
棧頂棧底： 這個描述是偏向于邏輯上的內(nèi)容，因為大家知道數(shù)組在末尾插入刪除更容易，而單鏈表通常在頭插入刪除更容易。所以數(shù)組可以用末尾做棧頂，而鏈表可以頭做棧頂。

棧的應(yīng)用：

棧的應(yīng)用廣泛，比如你的程序執(zhí)行查看調(diào)用堆棧、加減運算、甚至在搜索算法中dfs，替代遞歸等等。所以棧也是必須掌握的一門數(shù)據(jù)結(jié)構(gòu)。很多規(guī)范也是棧，比如上圖放書拿書一樣！

設(shè)計與介紹

這里我們介紹數(shù)組實現(xiàn)的棧和鏈表實現(xiàn)的棧。

數(shù)組實現(xiàn)

結(jié)構(gòu)設(shè)計

對于數(shù)組來說，我們模擬棧的過程很簡單，因為棧是后進先出，我們很容易在數(shù)組的末尾進行插入和刪除。所以我們選定末尾為棧頂。所以對于一個棧所需要的基礎(chǔ)元素是一個data數(shù)組和一個top(int)表示棧頂位置。
那么初始話以及構(gòu)造的函數(shù)代碼為：

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<數(shù)組長度-1。入棧。top++;a[top]=value;
如果top==數(shù)組長度-1；棧滿。

數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解

pop彈出并返回首位

如果top>=0,棧不為空，可以彈出。return data[top--];
如下圖，本來棧為1，2，3，4（棧頂），執(zhí)行pop操作。top變?yōu)?的位置并且返回4；

數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解

其他操作

其他例如peek操作時返回棧頂不彈出.所以只需滿足題意時候return data[top]即可。

鏈表實現(xiàn)

有數(shù)組實現(xiàn)，鏈表當(dāng)然也能實現(xiàn)。對于棧的運算。大致可以分為兩種思路：

像數(shù)組那樣在尾部插入刪除。大家都知道鏈表效率低在查詢。而查詢到尾部效率很低。而我們就算用了尾指針，可以解決尾部插入效率。但是依然無法解決刪除效率(刪除需要找到前節(jié)點).還需要雙向鏈表。前面雖然詳細介紹過雙向鏈表，但是這樣未免太復(fù)雜！
所以我們采用帶頭節(jié)點的單鏈表在頭部插入刪除，把頭部當(dāng)中棧頂，這樣精了很多。插入直接在頭節(jié)點后插入。而刪除也直接刪除頭節(jié)點后第一個元素即可。

結(jié)構(gòu)設(shè)計

長話短說，短話不說。直接上代碼就懂。

鏈表的節(jié)點：

static class node<T>{T data;node next;public node() {}public node(T value){this.data=value;}}

基本結(jié)構(gòu)：

public class lisStack <T>{int length;node<T> head;//頭節(jié)點public lisStack() {head=new node<>();length=0;}//其他方法}

push插入

與單鏈表頭插入一致，如果不太了解請先看筆者隊線性表介紹的。

和數(shù)組形成的棧有個區(qū)別。就是理論上棧沒有大小限制(不突破內(nèi)存系統(tǒng)限制)。不需要考慮是否越界。

節(jié)點team入棧
空鏈表入棧head.next=team;
非空入棧team.next=head.next;head.next=team;

數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解

pop彈出

與單鏈表頭刪除一致，如果不太了解請先看筆者隊線性表介紹的。

和數(shù)組同樣需要判斷是否為空。

節(jié)點team出棧
head指向team后驅(qū)節(jié)點。不需要考慮鏈表是否為1個節(jié)點。如果為1個節(jié)點，team.next=null.執(zhí)行完畢head.next=null。變?yōu)榭?，滿足條件。

數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解

其他操作

其他例如peek操作時返回棧頂不彈出.所以只需判空滿足題意時候return head.next.data即可。而length你可以遍歷鏈表返回長度，也可以動態(tài)設(shè)置(本文采取)跟隨棧長變化。其他操作直接看api。

實現(xiàn)代碼

數(shù)組實現(xiàn)

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;		}	}}

鏈表實現(xiàn)

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;//頭節(jié)點 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; } }}

測試

數(shù)據(jù)結(jié)構(gòu)與算法—棧詳解