數(shù)據(jù)結(jié)構(gòu)主講人：閭楓常州信息職業(yè)技術(shù)學(xué)院3.1棧棧（Stack）是一種操作受限的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。引言IntroductionPart01棧的抽象數(shù)據(jù)類型棧的插入和刪除操作只允許在線性表的一端進(jìn)行。允許進(jìn)行操作的一端稱為棧頂（top），不允許操作的一端則稱為棧底（bottom）。棧的插入操作通常稱為入棧（push），棧的刪除操作則稱為出棧（pop）。如果棧中無(wú)數(shù)據(jù)元素，則稱為空棧。棧頂元素是最后入棧，最先出棧，棧底元素是最先入棧，最后出棧，棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特征。棧（Stack）說(shuō)明棧的定義棧的定義棧操作限定的是元素插入和刪除的位置，元素插入和刪除操作進(jìn)行的時(shí)間并未限定。即出?？梢噪S時(shí)進(jìn)行，只要出棧的是棧頂元素即可。a有三個(gè)元素a，b，c依次進(jìn)棧并且每個(gè)元素只進(jìn)一次棧，則出棧的次序可以有：abc、acb、bac、bca、cba五種。示例若進(jìn)出棧操作為：a進(jìn)棧然后出棧，b、c進(jìn)棧，然后c出棧，b出棧，則最終的出棧次序?yàn)椋篴cbbcbb初始a進(jìn)棧a出棧c進(jìn)棧c出棧b出棧b進(jìn)棧雖然棧的操作受限降低了棧操作的靈活性，但也使棧的操作更有效和更容易實(shí)現(xiàn)。棧的基本操作主要有創(chuàng)建棧、入棧、出棧、取棧頂元素、判斷棧是否為空等。棧的抽象數(shù)據(jù)類型描述及定義Part02順序棧順序棧的存儲(chǔ)結(jié)構(gòu)棧作為一種特殊的線性表，可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧（SequentialStack）。順序棧的存儲(chǔ)結(jié)構(gòu)棧滿設(shè)數(shù)組的長(zhǎng)度為length，當(dāng)top=length-1時(shí)，表示棧滿?？諚Ｖ杏幸粋€(gè)元素時(shí)，top值為0，因此一般用top=-1，表示?？諚５讛?shù)組下標(biāo)為0的一端表示棧底棧頂用變量top表示棧頂元素在數(shù)組中的位置，也把top稱為棧頂指針一維數(shù)組順序棧一維數(shù)組順序棧的基本操作定義順序棧類SeqStack實(shí)現(xiàn)順序棧接口Stack，類中實(shí)現(xiàn)接口中相應(yīng)操作方法，定義泛型數(shù)組stack用于存儲(chǔ)數(shù)據(jù)元素，定義變量length表示棧的初始容量，定義整型變量top表示棧頂指針，指向棧頂元素位置。構(gòu)造方法用來(lái)對(duì)棧進(jìn)行初始化，創(chuàng)建一維的泛型數(shù)組，并指定棧的容量大小，設(shè)置棧頂指針為-1，代表是一個(gè)空棧。//順序棧類public

classSeqStack<T>implementsStack<T>{

privateT[]stack=null;//聲明一維數(shù)組，表示順序棧

private

int

length;//表示順序棧的容量

private

int

top;//棧頂指針

//棧初始化

publicSeqStack(){

stack=(T[])newObject[16];//構(gòu)造一維的泛型數(shù)組，默認(rèn)大小為16

length=16;

top=-1;//棧初始化，棧中沒(méi)有元素 }

publicSeqStack(int

size){

stack=(T[])newObject[size];//構(gòu)造一維的泛型數(shù)組，大小由參數(shù)決定

length=size;

top=-1;//棧初始化，棧中沒(méi)有元素 }……}順序棧的基本操作出棧時(shí)，先取出棧頂元素，然后top減1。出棧操作入棧時(shí)，top加1，指向新的棧頂位置，新元素放置到棧頂入棧操作atop03120312初始?？?top=-1

元素a,b,c入棧0312元素c,b出棧abctoptopcb順序棧的基本操作元素入棧先判斷棧是否滿，若棧已滿，則拋出異常；若棧未滿，則先將棧頂指針加1，再將元素放入棧頂位置。元素出棧需要判斷棧是否空，若棧空，則拋出異常；若棧不空，則先獲取頂元素，再將棧頂指針減1。//元素入棧@Overridepublic

voidpush(Tt){//判斷棧是否已滿，如果已滿，則拋出異常，如果未滿，則元素入棧

if(top==length-1){

throw

newRuntimeException("棧已經(jīng)滿，元素不能再進(jìn)棧");}else{

stack[++top]=t;//棧頂指針先加1，再將元素放入棧頂位置}}

//元素出棧@OverridepublicTpop(){//判斷棧是否為空，若為空，則拋出異常，若不空，則元素出棧

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素出棧");}else{

//先將棧頂元素值獲取返回，并將棧頂指針減1

return

stack[top--];}}時(shí)間復(fù)雜度為O(1)順序棧的基本操作判棧空棧空標(biāo)志是棧頂指針top值為-1，判斷top值是否為-1即可。取棧頂元素判斷棧不空，則直接返回棧頂元素值，棧頂指針不移動(dòng)。//獲取棧頂元素@OverridepublicTpeek(){//判斷棧是否為空，若為空，則拋出異常，若不空，則返回棧頂元素 if(this.isEmpty()){

throw

newRuntimeException("棧為空"); }else{

return

stack[top];//直接將棧頂元素值返回 }}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

//top為-1,代表?xiàng)Ｖ袥](méi)有元素，為空棧

return

top==-1;}棧中的元素是Integer類型,從棧頂?shù)綏５滓来问牵?、2、3、4，定義逆置方法，修改棧中元素的次序從棧頂?shù)綏５鬃優(yōu)?4、3、2、1。注意：只使用順序棧的基本操作方法。課堂實(shí)踐Part03鏈?zhǔn)綏ｆ準(zhǔn)綏５拇鎯?chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)綏＃?jiǎn)稱為鏈棧（LinkedStack）鏈棧一般用不帶頭結(jié)點(diǎn)單鏈表實(shí)現(xiàn)，單鏈表頭部作為棧頂，頭指針即為棧頂指針topantopa2a1^……棧底棧頂鏈?zhǔn)綏５幕静僮鱬ublic

classLinkedNode<T>{

privateTdata;

private

LinkedNodenext;

//構(gòu)造方法

publicLinkedNode(){ }

publicLinkedNode(Tdata){

this.data=data;

this.next=null; } publicLinkedNode(Tdata,LinkedNode<T>next){

this.data=data;

this.next=next; }

//省略相應(yīng)屬性的setter和getter方法 …...}鏈棧的結(jié)點(diǎn)結(jié)構(gòu)鏈棧的結(jié)點(diǎn)同樣包含數(shù)據(jù)域和指向下一個(gè)結(jié)點(diǎn)的指針域next變量用于指向下一個(gè)結(jié)點(diǎn)data變量用于存放數(shù)據(jù)鏈?zhǔn)綏５幕静僮?/鏈棧類public

classLinkedStack<T>implementsStack<T>{

privateLinkedNode<T>top;//代表?xiàng)ｍ斨羔?/p>

//棧初始化

publicLinkedStack(){

top=null;//將棧頂指針top置空，構(gòu)造一個(gè)空鏈棧 }

//實(shí)現(xiàn)棧接口的相關(guān)方法

……鏈棧類結(jié)構(gòu)鏈棧類LinkedStack實(shí)現(xiàn)棧接口Stack，除了實(shí)現(xiàn)棧接口的相應(yīng)方法外，鏈棧中定義一個(gè)LinkedNode類型的棧頂指針top，指向棧頂元素。鏈?zhǔn)綏５幕静僮鞒跏兼湕Ｖ杏?個(gè)元素ctopba^新結(jié)點(diǎn)入棧(1)先創(chuàng)建新結(jié)點(diǎn)noded^node(2)將新結(jié)點(diǎn)node指向棧頂指針(3)再移動(dòng)棧頂指針指向新結(jié)點(diǎn)鏈?zhǔn)綏５幕静僮?/元素入棧@Overridepublic

voidpush(Tt){

//將新結(jié)點(diǎn)指向棧頂，再移動(dòng)棧頂指針指向新結(jié)點(diǎn)，新結(jié)點(diǎn)成為棧頂元素 LinkedNode<T>node=newLinkedNode<T>(t);//使用傳遞的進(jìn)棧數(shù)值，先構(gòu)造新結(jié)點(diǎn)

node.setNext(top);//設(shè)置新結(jié)點(diǎn)指向棧頂指針

top=node;//設(shè)置棧頂指針指向新結(jié)點(diǎn)}入棧操作實(shí)現(xiàn)鏈?zhǔn)綏５幕静僮鞒跏兼湕Ｖ杏?個(gè)元素ctopba^出棧(1)棧頂元素值先保存到變量topData(2)移動(dòng)棧頂指針指向其下一個(gè)結(jié)點(diǎn)先保存棧頂元素值(3)返回變量topData的值鏈?zhǔn)綏５幕静僮?/元素出棧@OverridepublicTpop(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回，修改棧頂指針指向下一個(gè)結(jié)點(diǎn)

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素可出棧"); } TtopData=top.getData();//獲取棧頂元素值

top=top.getNext();//修改棧頂指針，指向下一個(gè)結(jié)點(diǎn)

return

topData;}出棧操作實(shí)現(xiàn)鏈?zhǔn)綏５幕静僮髋袛鄺？杖ｍ斣?/獲取棧頂元素@OverridepublicTpeek(){

//判斷鏈棧是否為空，若為空，拋出異常，若不為空，則取棧頂元素的值并返回

if(this.isEmpty()){

throw

newRuntimeException("棧為空，沒(méi)有元素可出棧"); }

return

top.getData();//返回棧頂元素的值}//判斷棧是否為空@Overridepublic

booleanisEmpty(){

if(top==null)return

true;

else

return

false;}時(shí)間復(fù)雜度為O(1)順序棧和鏈?zhǔn)綏５膶?duì)比順序棧鏈?zhǔn)綏２僮鞯臅r(shí)間復(fù)雜度為O(1)操作的時(shí)間復(fù)雜度為O(1)存在空間浪費(fèi)和棧滿問(wèn)題沒(méi)有棧滿問(wèn)題，但每個(gè)結(jié)點(diǎn)有數(shù)據(jù)域和引用域，增加內(nèi)存開銷元素個(gè)數(shù)變化不大，可使用順序棧若個(gè)數(shù)變化較大，不可預(yù)料，可使用鏈棧編寫代碼實(shí)現(xiàn)，將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)（使用除2倒取余法）課堂實(shí)踐Part04棧的應(yīng)用棧在計(jì)算機(jī)領(lǐng)域的應(yīng)用非常廣泛，如CPU的中斷處理、函數(shù)的嵌套調(diào)用或遞歸調(diào)用、圖的深度優(yōu)先遍歷、網(wǎng)頁(yè)瀏覽的后退操作、算術(shù)表達(dá)式的轉(zhuǎn)換和求值等實(shí)現(xiàn)中，都有棧的身影。棧的應(yīng)用棧的應(yīng)用函數(shù)嵌套調(diào)用函數(shù)的嵌套調(diào)用是在一個(gè)函數(shù)中調(diào)用另一個(gè)函數(shù)f1(){……f2();……}f2(){……f3();……}f3(){………………}main(){……f1();……}main調(diào)用f1f1調(diào)用f2f2調(diào)用f3f3函數(shù)此時(shí)4個(gè)函數(shù)都在執(zhí)行中，均占用系統(tǒng)資源。函數(shù)調(diào)用的系統(tǒng)棧mainf1f2f3后調(diào)用先返回設(shè)立函數(shù)調(diào)用的系統(tǒng)棧用于記錄函數(shù)調(diào)用位置及執(zhí)行環(huán)境等相關(guān)信息。函數(shù)被調(diào)用時(shí)，將被調(diào)用函數(shù)的相關(guān)信息入棧；函數(shù)執(zhí)行結(jié)束返回時(shí)，棧頂元素出棧，獲得調(diào)用函數(shù)的相關(guān)信息，返回到主調(diào)用函數(shù)繼續(xù)執(zhí)行。棧是系統(tǒng)實(shí)現(xiàn)函數(shù)嵌套調(diào)用的基礎(chǔ)。棧的應(yīng)用算術(shù)表達(dá)式求值

界限符（小括號(hào)等）運(yùn)算符（+，-，*……）操作數(shù)（1，2，3……）中綴表達(dá)式：(1+2*3)-4算術(shù)表達(dá)式四則運(yùn)算的規(guī)則有：先乘除、后加減同級(jí)運(yùn)算時(shí)先左后右先括號(hào)內(nèi)，后括號(hào)外等后綴表達(dá)式：

123*+4-后綴表達(dá)式是將運(yùn)算符放在操作數(shù)后面的寫法，如1+2的后綴表達(dá)式為：12+后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級(jí)，沒(méi)有括號(hào)，只有操作數(shù)和運(yùn)算符，運(yùn)算時(shí)能按從左到右的順序進(jìn)行，便于系統(tǒng)實(shí)現(xiàn)。棧的應(yīng)用算術(shù)表達(dá)式求值

說(shuō)明：為簡(jiǎn)化表達(dá)式求值過(guò)程，這里只討論操作數(shù)是個(gè)位整型，且運(yùn)算符僅有+、-、*、/，界限符為小括號(hào)。Step01Step02將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式對(duì)后綴表達(dá)式求值棧的應(yīng)用算術(shù)表達(dá)式求值

Step01中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式若字符ch是操作數(shù)，則直接將ch添加到postfix中；

從左至右讀取中綴表達(dá)式字符串中的字符ch，判斷字符類型進(jìn)行不同的處理，字符串postfix表示后綴表達(dá)式若字符ch是運(yùn)算符，若棧為空，則直接進(jìn)棧，若棧不空，則先與棧頂元素比較優(yōu)先級(jí)，若ch優(yōu)先級(jí)高于棧頂元素，ch入棧，否則棧頂元素出棧，添加到postfix中，一直到發(fā)現(xiàn)優(yōu)先級(jí)更低的元素為止；若字符ch是左括號(hào)(，則直接入棧；若字符ch是右括號(hào))，則棧中的運(yùn)算符出棧，直到彈出一個(gè)左括號(hào)為止反復(fù)讀取判斷，直到中綴表達(dá)式字符串讀取結(jié)束，將棧中的運(yùn)算符全部出棧，添加到postfix中。中綴表達(dá)式棧后綴表達(dá)式postfix(1+2*3)-4123*+4-棧的應(yīng)用算術(shù)表達(dá)式求值

//表達(dá)式處理public

classExpression{//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式public

staticStringinfixToPostfix(Stringinfix){

//棧初始化，存放運(yùn)算符SeqStack<String>stack=newSeqStack<String>(infix.length());StringBufferpostfix=newStringBuffer();//存放后綴表達(dá)式//循環(huán)讀取前綴表達(dá)式的字符for(int

i=0;i<infix.length();i++){

char

ch=infix.charAt(i);

switch(ch){

case

'(‘:

stack.push(ch+""); break;//若是左括號(hào)，直接入棧

case

')'://棧元素出棧 Stringstr=null;

while(!(str=stack.pop()).equals("(")){//棧項(xiàng)元素不為左括號(hào),則元素一直出棧添加到串中，直到遇到左括號(hào)

postfix.append(str); } break;

case

'+’:

case

'-’:

//先與棧頂元素比較優(yōu)先級(jí)，運(yùn)算符是+或-時(shí)，只有棧頂元素是（，才會(huì)直接進(jìn)棧，其他情況都是出棧

while(!stack.isEmpty()&&!stack.peek().equals("(")){

postfix.append(stack.pop()); }

stack.push(ch+"");//當(dāng)前運(yùn)算符入棧

break;

case

'*’:

case

'/’:

//先與棧頂元素比較優(yōu)先級(jí)，運(yùn)算符是*或/時(shí)，棧頂元素是（或+或-，才會(huì)直接進(jìn)棧，若是*或/，因是同級(jí)，則是出棧

while(!stack.isEmpty()&&(stack.peek().equals("*")||stack.peek().equals("/"))){

postfix.append(stack.pop()); }

stack.push(ch+"");//當(dāng)前運(yùn)算符入棧

break;

default://表示讀取的不是運(yùn)算符，是數(shù)值

postfix.append(ch); } }

//前綴表達(dá)式讀取結(jié)束，若棧不空，元素直接出棧，接到串中

while(!stack.isEmpty()){

postfix.append(stack.pop()); }

return

postfix.toString();}}【注意】在中綴表達(dá)式中，運(yùn)算符的優(yōu)先級(jí)括號(hào)最高，其次為*、/，最后是+、-，而一旦進(jìn)入運(yùn)算符棧中后，“(”優(yōu)先級(jí)變成最低。棧的應(yīng)用算術(shù)表達(dá)式求值

//計(jì)算后綴表達(dá)式的值public

static

floatcalculate(Stringpostfix){