強(qiáng)烈推薦,零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)第4章棧

1、第第4 4 棧也是一種重要的線性結(jié)構(gòu)。棧具有線性表的特點(diǎn)：棧也是一種重要的線性結(jié)構(gòu)。棧具有線性表的特點(diǎn)： 每一個(gè)元素只有一個(gè)前驅(qū)元素和后繼元素（除了第一個(gè)元素每一個(gè)元素只有一個(gè)前驅(qū)元素和后繼元素（除了第一個(gè)元素 和最后一個(gè)元素外），但是在操作上與線性表不同，棧是一和最后一個(gè)元素外），但是在操作上與線性表不同，棧是一 種操作受限的線性表，只允許在棧的一端進(jìn)行插入和刪除操種操作受限的線性表，只允許在棧的一端進(jìn)行插入和刪除操 作。作。 4.1 4.1 棧的表示與實(shí)現(xiàn)棧的表示與實(shí)現(xiàn) 棧是作為一種限定性線性表，只允許在表的一端進(jìn)行棧是作為一種限定性線性表，只允許在表的一端進(jìn)行 插入和刪除操作。本節(jié)主要介

2、紹棧的定義和棧的抽象數(shù)據(jù)類插入和刪除操作。本節(jié)主要介紹棧的定義和棧的抽象數(shù)據(jù)類 型。型。 4.1.1 4.1.1 棧的定義棧的定義 棧，也稱為堆棧，它是一種特殊的線性表，只允許在棧，也稱為堆棧，它是一種特殊的線性表，只允許在 表的一端進(jìn)行插入和刪除操作。棧頂是動(dòng)態(tài)變化的，它由一表的一端進(jìn)行插入和刪除操作。棧頂是動(dòng)態(tài)變化的，它由一 個(gè)稱為棧頂指針（個(gè)稱為棧頂指針（top）的變量指示。當(dāng)表中沒有元素時(shí)，）的變量指示。當(dāng)表中沒有元素時(shí)， 稱為空棧。稱為空棧。 棧的插入操作稱為入?；蜻M(jìn)棧，刪除操作稱為出?；驐５牟迦氩僮鞣Q為入?；蜻M(jìn)棧，刪除操作稱為出?；?退棧。退棧。 4.1.1 4.1.1 棧的定義棧

3、的定義 4.1.2 4.1.2 棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型 1數(shù)據(jù)對(duì)象集合數(shù)據(jù)對(duì)象集合 2基本操作集合基本操作集合 4.2 4.2 棧的順序表示與實(shí)現(xiàn)棧的順序表示與實(shí)現(xiàn) 與線性表一樣，棧也有兩種存儲(chǔ)表示：順序存儲(chǔ)和鏈與線性表一樣，棧也有兩種存儲(chǔ)表示：順序存儲(chǔ)和鏈 式存儲(chǔ)。本節(jié)的主要學(xué)習(xí)內(nèi)容包括棧的順序存儲(chǔ)結(jié)構(gòu)及順序式存儲(chǔ)。本節(jié)的主要學(xué)習(xí)內(nèi)容包括棧的順序存儲(chǔ)結(jié)構(gòu)及順序 存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)。存儲(chǔ)結(jié)構(gòu)下的操作實(shí)現(xiàn)。 4.2.1 4.2.1 棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu) 采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧。順序棧利用一組采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧。順序棧利用一組 連續(xù)的存儲(chǔ)單元存放棧中的元

4、素，存放順序依次從棧底到棧連續(xù)的存儲(chǔ)單元存放棧中的元素，存放順序依次從棧底到棧 頂。由于棧中元素之間的存放地址的連續(xù)性，在頂。由于棧中元素之間的存放地址的連續(xù)性，在C語言中，語言中， 同樣采用數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)。同樣采用數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)。 #define StackSize 100 typedef struct DataType stackStackSize; int top; SeqStack; 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 在順序存儲(chǔ)結(jié)構(gòu)中，棧的基本運(yùn)算如下。以下算法的在順序存儲(chǔ)結(jié)構(gòu)中，棧的基本運(yùn)算如下。以下算法的 實(shí)現(xiàn)保存在文件實(shí)現(xiàn)保存在文件“SeqSt

5、ack.h”中。中。 （1）棧的初始化操作。）棧的初始化操作。 void InitStack(SeqStack *S) /*將棧初始化為空棧只需要把棧頂指針將棧初始化為空棧只需要把棧頂指針top置為置為0*/ S-top=0; /*把棧頂指針置為把棧頂指針置為0*/ 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 （2）判斷棧是否為空。）判斷棧是否為空。 int StackEmpty(SeqStack S) /*判斷棧是否為空，棧為空返回判斷棧是否為空，棧為空返回1，否則返回，否則返回0*/ if(S.top=0)/*判斷棧頂指針判斷棧頂指針top是否為是否為0*/ return 1

6、;/*當(dāng)棧為空時(shí)，返回當(dāng)棧為空時(shí)，返回1；否則返回；否則返回0*/ else return 0; 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 （3）取棧頂元素操作。）取棧頂元素操作。 int GetTop(SeqStack S, DataType *e) if(S.toptop=StackSize) printf(“棧已滿，不能進(jìn)棧！棧已滿，不能進(jìn)棧！n”); return 0; else S-stackS-top=e; S-top+; return 1; 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 （5）出棧操作。）出棧操作。 int PopStack(SeqSt

7、ack *S,DataType *e) if(S-top=0) printf(“棧已經(jīng)沒有元素，不能出棧棧已經(jīng)沒有元素，不能出棧!n”); return 0; else S-top-; *e=S-stackS-top; return 1; 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 （6）返回棧的長度操作。）返回棧的長度操作。 int StackLength(SeqStack S) return S.top; 4.2.2 4.2.2 順序棧的基本運(yùn)算順序棧的基本運(yùn)算 （7）清空棧的操作。）清空棧的操作。 void ClearStack(SeqStack *S) S-top=0;

8、4.2.3 4.2.3 共享?xiàng)５膯栴}共享?xiàng)５膯栴} 棧的應(yīng)用非常廣泛，經(jīng)常會(huì)出現(xiàn)一個(gè)程序需要同時(shí)使棧的應(yīng)用非常廣泛，經(jīng)常會(huì)出現(xiàn)一個(gè)程序需要同時(shí)使 用多個(gè)棧的情況。使用順序棧會(huì)因?yàn)闂？臻g的大小難以準(zhǔn)確用多個(gè)棧的情況。使用順序棧會(huì)因?yàn)闂？臻g的大小難以準(zhǔn)確 估計(jì)，從而造成有的棧溢出，有的?？臻g還有空閑。為了解估計(jì)，從而造成有的棧溢出，有的?？臻g還有空閑。為了解 決這個(gè)問題，可以讓多個(gè)棧共享一個(gè)足夠大的連續(xù)存儲(chǔ)空間決這個(gè)問題，可以讓多個(gè)棧共享一個(gè)足夠大的連續(xù)存儲(chǔ)空間 ，通過利用棧的動(dòng)態(tài)特性使多個(gè)棧存儲(chǔ)空間能夠互相補(bǔ)充，通過利用棧的動(dòng)態(tài)特性使多個(gè)棧存儲(chǔ)空間能夠互相補(bǔ)充， 存儲(chǔ)空間得到有效利用，這就是棧的共

9、享存儲(chǔ)空間得到有效利用，這就是棧的共享 . 4.2.3 4.2.3 共享?xiàng)５膯栴}共享?xiàng)５膯栴} 兩個(gè)共享?xiàng)５臄?shù)據(jù)結(jié)構(gòu)類型定義兩個(gè)共享?xiàng)５臄?shù)據(jù)結(jié)構(gòu)類型定義 typedef struct DataType stackStackSize; int top2; SSeqStack; 4.2.3 4.2.3 共享?xiàng)５膯栴}共享?xiàng)５膯栴} （1）初始化操作。）初始化操作。 void InitStack(SSeqStack *S) S-top0=0; S-top1=StackSize-1; 4.2.3 4.2.3 共享?xiàng)５膯栴}共享?xiàng)５膯栴} （2）進(jìn)棧操作。）進(jìn)棧操作。 int PushStack(SSeqStac

10、k *S,DataType e,int flag) if(S-top0=S-top1) return 0; switch(flag) case 0: S-stackS-top0=e; S-top0+; break; case 1: S-stackS-top1=e; S-top1-; break; default: return 0; return 1; 4.2.3 4.2.3 共享?xiàng)５膯栴}共享?xiàng)５膯栴} （3）出棧操作。）出棧操作。 int PopStack(SSeqStack *S,DataType *e,int flag) switch(flag) case 0: if(S-top0=0)

11、return 0; S-top0-; *e=S-stackS-top0; break; case 1: if(S-top1=StackSize-1) return 0; S-top1+; *e=S-stackS-top1; break; default: return 0; return 1; 4.3 4.3 棧的應(yīng)用舉例棧的應(yīng)用舉例 上一節(jié)已經(jīng)學(xué)習(xí)了棧的順序存儲(chǔ)結(jié)構(gòu)及棧的實(shí)現(xiàn)。本上一節(jié)已經(jīng)學(xué)習(xí)了棧的順序存儲(chǔ)結(jié)構(gòu)及棧的實(shí)現(xiàn)。本 節(jié)通過實(shí)例來學(xué)習(xí)棧的基本操作的用法。節(jié)通過實(shí)例來學(xué)習(xí)棧的基本操作的用法。 例例4_1 將元素將元素a、b、c、d、e依次進(jìn)棧，然后將依次進(jìn)棧，然后將d和和e 出棧，再將

12、出棧，再將f和和g進(jìn)棧，最后將元素全部出棧，并將元素按照進(jìn)棧，最后將元素全部出棧，并將元素按照 出棧次序輸出。出棧次序輸出。 4.3 4.3 棧的應(yīng)用舉例棧的應(yīng)用舉例 例例4_2 設(shè)有兩個(gè)棧設(shè)有兩個(gè)棧S1和和S2都采用順序棧的方式存儲(chǔ)，都采用順序棧的方式存儲(chǔ)， 并且共享一個(gè)存儲(chǔ)區(qū)。為了盡可能利用存儲(chǔ)空間，減少溢出并且共享一個(gè)存儲(chǔ)區(qū)。為了盡可能利用存儲(chǔ)空間，減少溢出 的可能，采用棧頂相向，迎面增長的方式，試設(shè)計(jì)的可能，采用棧頂相向，迎面增長的方式，試設(shè)計(jì)S1和和S2 有關(guān)入棧和出棧算法。有關(guān)入棧和出棧算法。 4.4 4.4 棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn)棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 在順序棧中，由于順序存儲(chǔ)結(jié)構(gòu)需要事

13、先靜態(tài)分配，在順序棧中，由于順序存儲(chǔ)結(jié)構(gòu)需要事先靜態(tài)分配， 而存儲(chǔ)規(guī)模往往又難以確定，如果?？臻g分配過小，可能會(huì)而存儲(chǔ)規(guī)模往往又難以確定，如果?？臻g分配過小，可能會(huì) 造成溢出；如果?？臻g分配過大，又造成存儲(chǔ)空間浪費(fèi)。因造成溢出；如果?？臻g分配過大，又造成存儲(chǔ)空間浪費(fèi)。因 此，為了克服順序存儲(chǔ)的缺點(diǎn)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示棧。此，為了克服順序存儲(chǔ)的缺點(diǎn)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示棧。 本節(jié)主要學(xué)習(xí)內(nèi)容包括棧的存儲(chǔ)結(jié)構(gòu)及鏈棧的基本運(yùn)算。本節(jié)主要學(xué)習(xí)內(nèi)容包括棧的存儲(chǔ)結(jié)構(gòu)及鏈棧的基本運(yùn)算。 4.4.1 4.4.1 棧的存儲(chǔ)結(jié)構(gòu)棧的存儲(chǔ)結(jié)構(gòu) 采用鏈?zhǔn)酱鎯?chǔ)方式的棧稱為鏈?；蜴?zhǔn)綏?。鏈棧由一個(gè)個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)方式

14、的棧稱為鏈棧或鏈?zhǔn)綏?。鏈棧由一個(gè)個(gè)結(jié)點(diǎn) 構(gòu)成，結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩部分。在鏈棧中，利用每一個(gè)結(jié)構(gòu)成，結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩部分。在鏈棧中，利用每一個(gè)結(jié) 點(diǎn)的數(shù)據(jù)域存儲(chǔ)棧中的每一個(gè)元素，利用指針域表示元素之間的關(guān)點(diǎn)的數(shù)據(jù)域存儲(chǔ)棧中的每一個(gè)元素，利用指針域表示元素之間的關(guān) 系。插入和刪除元素的一端稱為棧頂，棧頂由棧頂指針系。插入和刪除元素的一端稱為棧頂，棧頂由棧頂指針top指示。指示。 鏈棧結(jié)點(diǎn)的類型定義如下：鏈棧結(jié)點(diǎn)的類型定義如下： typedef struct node DataType data; struct node *next; LStackNode,*LinkStack; 4.

15、4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 鏈棧的基本運(yùn)算包括鏈棧的初始化、進(jìn)棧、出棧、取鏈棧的基本運(yùn)算包括鏈棧的初始化、進(jìn)棧、出棧、取 棧頂元素等。帶頭結(jié)點(diǎn)的鏈棧的基本運(yùn)算具體實(shí)現(xiàn)如下。棧頂元素等。帶頭結(jié)點(diǎn)的鏈棧的基本運(yùn)算具體實(shí)現(xiàn)如下。 4.4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 （1）鏈棧的初始化操作。）鏈棧的初始化操作。 void InitStack(LinkStack *top) if(*top=(LinkStack)malloc(sizeof(LStackNode) =NULL) exit(-1); (*top)-next=NULL; 4.4.2 4.4.2 棧的基本運(yùn)算棧的

16、基本運(yùn)算 （2）判斷鏈棧是否為空。）判斷鏈棧是否為空。 int StackEmpty(LinkStack top) if(top-next=NULL) return 1; else return 0; 4.4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 （3）進(jìn)棧操作。）進(jìn)棧操作。 int PushStack(LinkStack top, DataType e) LStackNode *p; p=(LStackNode*)malloc(sizeof(LStackNode) p-data=e; p-next=top-next; top-next=p; return 1; 4.4.2 4.4.2 棧

17、的基本運(yùn)算棧的基本運(yùn)算 （4）出棧操作。）出棧操作。 int PopStack(LinkStack top,DataType *e) LStackNode *p; p=top-next; if(!p) printf(“棧已空棧已空”); return 0; top-next=p-next; *e=p-data; free(p); return 1; 4.4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 （5）取棧頂元素操作。）取棧頂元素操作。 void GetTop(LinkStack top,DataType *e) LStackNode *p; p=top-next; if(!p) print

18、f(“棧已空棧已空”); return 0; *e=p-data; return 1; 4.4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 （6）求表長操作。）求表長操作。 int StackLength(LinkStack top) LStackNode *p; int count=0; p=top; while(p-next!=NULL) p=p-next; count+; return count; 4.4.2 4.4.2 棧的基本運(yùn)算棧的基本運(yùn)算 （7）銷毀鏈棧操作。）銷毀鏈棧操作。 void DestroyStack(LinkStack top) LStackNode *p,*q; p

19、=top; while(!p) q=p; p=p-next; free(q); 4.4.3 4.4.3 鏈棧的應(yīng)用鏈棧的應(yīng)用 下面通過一個(gè)實(shí)例說明鏈棧基本算法的應(yīng)用。下面通過一個(gè)實(shí)例說明鏈棧基本算法的應(yīng)用。 例例4_3 利用鏈棧的基本運(yùn)算，通過輸入將字符進(jìn)棧，利用鏈棧的基本運(yùn)算，通過輸入將字符進(jìn)棧， 然后輸出其出棧序列。然后輸出其出棧序列。 4.5 4.5 棧的應(yīng)用舉例棧的應(yīng)用舉例 由于棧結(jié)構(gòu)后進(jìn)先出的特性，使它成為一種重要的數(shù)由于棧結(jié)構(gòu)后進(jìn)先出的特性，使它成為一種重要的數(shù) 據(jù)結(jié)構(gòu)，它在計(jì)算機(jī)中的應(yīng)用也非常廣泛。在程序的編譯和據(jù)結(jié)構(gòu)，它在計(jì)算機(jī)中的應(yīng)用也非常廣泛。在程序的編譯和 運(yùn)行過程中，需

20、要利用棧對(duì)程序的語法進(jìn)行檢查，如括號(hào)的運(yùn)行過程中，需要利用棧對(duì)程序的語法進(jìn)行檢查，如括號(hào)的 配對(duì)、表達(dá)式求值和函數(shù)的遞歸調(diào)用。本節(jié)通過幾個(gè)例子來配對(duì)、表達(dá)式求值和函數(shù)的遞歸調(diào)用。本節(jié)通過幾個(gè)例子來 學(xué)習(xí)棧的具體應(yīng)用。學(xué)習(xí)棧的具體應(yīng)用。 4.5.1 4.5.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 如果將十進(jìn)制數(shù)如果將十進(jìn)制數(shù)N轉(zhuǎn)換為轉(zhuǎn)換為x進(jìn)制數(shù)，需要用輾轉(zhuǎn)相除法進(jìn)制數(shù)，需要用輾轉(zhuǎn)相除法 執(zhí)行以下步驟：執(zhí)行以下步驟： （1）將）將N除以除以x，取其余數(shù)；，取其余數(shù)； （2）判斷商是否為零，如果為零，結(jié)束程序；否則，）判斷商是否為零，如果為零，結(jié)束程序；否則， 將商送將商送N，轉(zhuǎn)（，轉(zhuǎn)（1）繼續(xù)執(zhí)行。）繼續(xù)執(zhí)行。

21、4.5.2 4.5.2 括號(hào)配對(duì)括號(hào)配對(duì) 假設(shè)表達(dá)式中允許包含三種類型的括號(hào)：花括號(hào)假設(shè)表達(dá)式中允許包含三種類型的括號(hào)：花括號(hào) 、方括號(hào)、方括號(hào)和圓括號(hào)和圓括號(hào)()。其嵌套的順序任意，即。其嵌套的順序任意，即()和和 ()均為正確的格式，均為正確的格式，()、()和和()均為不正確的格式均為不正確的格式 。 4.5.3 4.5.3 行編輯程序行編輯程序 一個(gè)簡單的行編輯程序的功能是：將用戶輸入的字符一個(gè)簡單的行編輯程序的功能是：將用戶輸入的字符 序列存入數(shù)據(jù)區(qū)，由于用戶進(jìn)行輸入時(shí)，有可能會(huì)出現(xiàn)錯(cuò)誤序列存入數(shù)據(jù)區(qū)，由于用戶進(jìn)行輸入時(shí)，有可能會(huì)出現(xiàn)錯(cuò)誤 。因此，如果在編輯程序中，每接受一個(gè)字符，即

22、存入數(shù)據(jù)。因此，如果在編輯程序中，每接受一個(gè)字符，即存入數(shù)據(jù) 區(qū)的做法顯然是不合適的。一個(gè)比較好的做法是，設(shè)立一個(gè)區(qū)的做法顯然是不合適的。一個(gè)比較好的做法是，設(shè)立一個(gè) 輸入緩沖區(qū)，用來接受用戶輸入的一行字符，然后輸入緩沖區(qū)，用來接受用戶輸入的一行字符，然后逐行存入逐行存入 數(shù)據(jù)區(qū)。如果用戶輸入出現(xiàn)錯(cuò)誤，在發(fā)現(xiàn)輸入有誤時(shí)及時(shí)更數(shù)據(jù)區(qū)。如果用戶輸入出現(xiàn)錯(cuò)誤，在發(fā)現(xiàn)輸入有誤時(shí)及時(shí)更 正。正。 4.6 4.6 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) 棧的后進(jìn)先出的思想還應(yīng)用在函數(shù)的遞歸調(diào)用中。本棧的后進(jìn)先出的思想還應(yīng)用在函數(shù)的遞歸調(diào)用中。本 節(jié)主要說明棧與遞歸調(diào)用的關(guān)系、遞歸利用棧的實(shí)現(xiàn)過程、節(jié)主要說明棧與遞歸

23、調(diào)用的關(guān)系、遞歸利用棧的實(shí)現(xiàn)過程、 遞歸與非遞歸的轉(zhuǎn)換。遞歸與非遞歸的轉(zhuǎn)換。 4.6.1 4.6.1 遞歸遞歸 1遞歸函數(shù)遞歸函數(shù) 2遞歸調(diào)用過程遞歸調(diào)用過程 4.6.1 4.6.1 遞歸遞歸 int fact(int n) if(n=0) return 1; else return n*fact(n-1); 4.6.1 4.6.1 遞歸遞歸 int Ack(int m,int n) if(m=0) return n+1; else if(n=0) return Ack(m-1,1); else return Ack(m-1,Ack(m,n-1); 4.6.1 4.6.1 遞歸遞歸 4.6.1

24、 4.6.1 遞歸遞歸 4.6.1 4.6.1 遞歸遞歸 4.6.1 4.6.1 遞歸遞歸 void Hanoi(int n,char x,char y,char z) /*將塔座將塔座X上按照從小到大自上而下編號(hào)為上按照從小到大自上而下編號(hào)為1到到n的那個(gè)圓盤的那個(gè)圓盤 按照規(guī)則搬到塔座按照規(guī)則搬到塔座Z上，上，Y可以作為輔助塔座可以作為輔助塔座*/ if(n=1) Move(x,1,z); /*將編號(hào)為將編號(hào)為1的圓盤從的圓盤從X移動(dòng)到移動(dòng)到Z*/ else Hanoi(n-1,x,z,y); /*將編號(hào)為將編號(hào)為1到到n-1的圓盤從的圓盤從X移動(dòng)移動(dòng) 到到Y(jié)，Z作為輔助塔座作為輔助塔座*

25、/ Move(x,n,z); /*將編號(hào)為將編號(hào)為n的圓盤從的圓盤從X移動(dòng)到移動(dòng)到Z*/ Hanoi(n-1,y,x,z); /*將編號(hào)為將編號(hào)為1到到n-1的圓盤從的圓盤從Y移動(dòng)移動(dòng) 到到Z，X作為輔助塔座作為輔助塔座*/ 4.6.2 4.6.2 消除遞歸消除遞歸 用遞歸編制的算法結(jié)構(gòu)清晰、易讀，容易實(shí)現(xiàn)并且遞用遞歸編制的算法結(jié)構(gòu)清晰、易讀，容易實(shí)現(xiàn)并且遞 歸算法的正確性很容易得到證明。但是，遞歸算法的執(zhí)行效歸算法的正確性很容易得到證明。但是，遞歸算法的執(zhí)行效 率比較低，因?yàn)檫f歸需要反復(fù)入棧，時(shí)間和空間開銷比較大率比較低，因?yàn)檫f歸需要反復(fù)入棧，時(shí)間和空間開銷比較大 。 遞歸的算法也完全可以轉(zhuǎn)換為非遞歸實(shí)現(xiàn)，這就是遞遞歸的算法也完全可以轉(zhuǎn)換為非遞歸實(shí)現(xiàn)，這就是遞 歸的消除。消除遞歸方法有兩種，一