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

classSeqStack<T>implementsStack<T>{

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

private

int

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

private

int

top;//棧頂指針

//棧初始化

publicSeqStack(){

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

length=16;

top=-1;//棧初始化，棧中沒有元素 }

publicSeqStack(int

size){

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

length=size;

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

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

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

if(top==length-1){

throw

newRuntimeException("棧已經滿，元素不能再進棧");}else{

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

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

if(this.isEmpty()){

throw

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

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

return

stack[top--];}}時間復雜度為O(1)順序棧的基本操作判棧空?？諛酥臼菞ｍ斨羔榯op值為-1，判斷top值是否為-1即可。取棧頂元素判斷棧不空，則直接返回棧頂元素值，棧頂指針不移動。//獲取棧頂元素@OverridepublicTpeek(){//判斷棧是否為空，若為空，則拋出異常，若不空，則返回棧頂元素 if(this.isEmpty()){

throw

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

return

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

booleanisEmpty(){

//top為-1,代表棧中沒有元素，為空棧

return

top==-1;}棧中的元素是Integer類型,從棧頂?shù)綏５滓来问牵?、2、3、4，定義逆置方法，修改棧中元素的次序從棧頂?shù)綏５鬃優(yōu)?4、3、2、1。注意：只使用順序棧的基本操作方法。課堂實踐Part03鏈式棧鏈式棧的存儲結構采用鏈式存儲結構的棧稱為鏈式棧，簡稱為鏈棧（LinkedStack）鏈棧一般用不帶頭結點單鏈表實現(xiàn)，單鏈表頭部作為棧頂，頭指針即為棧頂指針topantopa2a1^……棧底棧頂鏈式棧的基本操作public

classLinkedNode<T>{

privateTdata;

private

LinkedNodenext;

//構造方法

publicLinkedNode(){ }

publicLinkedNode(Tdata){

this.data=data;

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

this.data=data;

this.next=next; }

//省略相應屬性的setter和getter方法 …...}鏈棧的結點結構鏈棧的結點同樣包含數(shù)據(jù)域和指向下一個結點的指針域next變量用于指向下一個結點data變量用于存放數(shù)據(jù)鏈式棧的基本操作//鏈棧類public

classLinkedStack<T>implementsStack<T>{

privateLinkedNode<T>top;//代表棧頂指針

//棧初始化

publicLinkedStack(){

top=null;//將棧頂指針top置空，構造一個空鏈棧 }

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

……鏈棧類結構鏈棧類LinkedStack實現(xiàn)棧接口Stack，除了實現(xiàn)棧接口的相應方法外，鏈棧中定義一個LinkedNode類型的棧頂指針top，指向棧頂元素。鏈式棧的基本操作初始鏈棧中有3個元素ctopba^新結點入棧(1)先創(chuàng)建新結點noded^node(2)將新結點node指向棧頂指針(3)再移動棧頂指針指向新結點鏈式棧的基本操作//元素入棧@Overridepublic

voidpush(Tt){

//將新結點指向棧頂，再移動棧頂指針指向新結點，新結點成為棧頂元素 LinkedNode<T>node=newLinkedNode<T>(t);//使用傳遞的進棧數(shù)值，先構造新結點

node.setNext(top);//設置新結點指向棧頂指針

top=node;//設置棧頂指針指向新結點}入棧操作實現(xiàn)鏈式棧的基本操作初始鏈棧中有3個元素ctopba^出棧(1)棧頂元素值先保存到變量topData(2)移動棧頂指針指向其下一個結點先保存棧頂元素值(3)返回變量topData的值鏈式棧的基本操作//元素出棧@OverridepublicTpop(){

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

if(this.isEmpty()){

throw

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

top=top.getNext();//修改棧頂指針，指向下一個結點

return

topData;}出棧操作實現(xiàn)鏈式棧的基本操作判斷棧空取棧頂元素//獲取棧頂元素@OverridepublicTpeek(){

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

if(this.isEmpty()){

throw

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

return

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

booleanisEmpty(){

if(top==null)return

true;

else

return

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

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

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

說明：為簡化表達式求值過程，這里只討論操作數(shù)是個位整型，且運算符僅有+、-、*、/，界限符為小括號。Step01Step02將中綴表達式轉換為后綴表達式對后綴表達式求值棧的應用算術表達式求值

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

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

//表達式處理public

classExpression{//中綴表達式轉換為后綴表達式public

staticStringinfixToPostfix(Stringinfix){

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

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

char

ch=infix.charAt(i);

switch(ch){

case

'(‘:

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

case

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

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

postfix.append(str); } break;

case

'+’:

case

'-’:

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

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

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

stack.push(ch+"");//當前運算符入棧

break;

case

'*’:

case

'/’:

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

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

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

stack.push(ch+"");//當前運算符入棧

break;

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

postfix.append(ch); } }

//前綴表達式讀取結束，若棧不空，元素直接出棧，接到串中

while(!stack.isEmpty()){

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

return

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

//計算后綴表達式的值public

static

floatcalculate(Stringpostfix){