前言
這兩天不知道有點咋了，心里亂糟糟的，今天正好整理一下棧的知識，然后順順心，主要就是理解一下棧這個數(shù)據(jù)結(jié)構(gòu)
一、什么是棧？
棧是一種特殊的線性表，它只允許在一端進(jìn)行操作，所以它具有 先進(jìn)后出或者叫后進(jìn)先出的特性，這就是棧
那么同樣都是數(shù)據(jù)結(jié)構(gòu)，我們?yōu)槭裁匆褂眠@種，操作受限，因為在特定的環(huán)境下需要使用特定的數(shù)據(jù)結(jié)構(gòu)，在一些先進(jìn)后出的場合，理所應(yīng)當(dāng)?shù)氖褂脳＿@種結(jié)構(gòu)
二、棧的實現(xiàn)
棧的實現(xiàn)有兩種，一種是基于數(shù)組事項的棧叫順序棧，另一種是基于鏈表實現(xiàn)的棧鏈?zhǔn)綏?/strong>
- 順序棧(java實現(xiàn))
public class ArrayStack{
private String [ ] items;//數(shù)組變量
private int count;//棧中元素變量
private int n; //棧的大小
//初始化數(shù)組，定義一個為n的空間
public ArrayStack（int n）{
this.items=new String [n];
this.n=n;
this.count=0;
}
//入棧，傳入一個數(shù)組
public boolean push （String item）{
if（count==n）
return false；//數(shù)組空間不夠，入棧失敗
//將item放入到count的位置，并起count+1，返回成功
item[count]=item;
count++;
return true;
}
//出棧
public String pop( ){
//如果棧為空，返回null
if(count==o)
return null;
//放回下標(biāo)為count-1位置的數(shù)，并起count-1
String temp= item[count-1];
count--；
return temp；
}
}
- 鏈?zhǔn)綏?br> 和數(shù)組類似，具體可參看 鏈?zhǔn)綏?java實現(xiàn)
三、棧的應(yīng)用
1.函數(shù)調(diào)用棧
有這么一個棧的內(nèi)存，用來存儲棧的數(shù)據(jù)結(jié)構(gòu)，每進(jìn)入一個函數(shù)，就會將臨時變量當(dāng)做一個棧幀入棧，當(dāng)函數(shù)使用完成以后，這個函數(shù)對應(yīng)的棧幀出棧
有這么一段代碼
int main（）{
int a =1;
int ret=0;
int res=0;
ret=add(1,9)
res=a+ret;
return 0;
}
int add(int x,int y){
int sum=0;
sum=x+y;
return sum;
}
入棧和出棧的順序為
a=1
res=0 main棧幀
ret=0
.....
y=1
x=9 add棧幀
sum=0
...
2.棧在表達(dá)式求值中的應(yīng)用
利用棧來實現(xiàn)表達(dá)式求值
編譯器通過兩個棧來實現(xiàn)，分別是保存操作數(shù)的棧和保存運算符的棧
實現(xiàn)過程是這樣的
1.遍歷表達(dá)式，如果遇到操作數(shù)，則存入操作數(shù)棧，如果遇到運算符，則和存在運算符棧的棧頂?shù)倪\算符比較（已經(jīng)預(yù)先存了 + - * /）
2.如果優(yōu)先級大于運算符棧 棧頂?shù)膬?yōu)先級，則將當(dāng)前運算符壓入棧，如果低于棧頂運算符的優(yōu)先級，則返回
3.從操作數(shù)棧中取數(shù)，從運算符棧中取運算符--》計算
3.棧在匹配中的應(yīng)用
我們還可以使用棧來檢查表達(dá)式中是否匹配
- 我們先假定一個條件只有匹配到 “[ ]”{ }“( )”，兩個括號都有才算正確，否則都算匹配不正確
- 接下來從左向右依次掃描字符串，如果遇到“[”{““(””就存入棧中，如果遇到另一半的右括號，就從棧頂取出左括號進(jìn)行匹配，只有左右是同一中括號才匹配成功，如果匹配成功，就繼續(xù)進(jìn)行掃描，如果匹配不成功，就說明字符串格式不正確
- 當(dāng)然還有一種情況就是，當(dāng)棧為空的時候，也是匹配成功，因為棧里所有的都已經(jīng)完成匹配
