3.1 棧

3.1.1 棧的定義及其基本運算

棧（Stack）是限制在表的一端進行插入和刪除操作的線性表。允許進行插入、刪除操作的這一端稱為棧頂（Top），另一個固定端稱為棧底。當表中沒有元素時稱為空棧。如圖3.1所示的棧中有三個元素，進棧的順序是a1、a2、a3，當需要出棧時其順序為a3、a2、a1，所以棧又稱為“后進先出”（Last-In First-Out，LIFO）或“先進后出”（First-In Last-Out，FILO）的線性表，簡稱“LIFO表”或“FILO表”。

（注：LIFO規范的寫法有兩種：Last-In First-Out、Last In，First Out。FILO類似。）

在日常生活中，有很多類似棧的例子，讀者可以列舉。在程序設計中，常常需要將數據按其保存時相反的順序來使用，這時就需要用一個棧這樣的數據結構來實現。

對于棧，常見的基本運算有以下幾種。

（1）棧初始化：Init_Stack ( s )。

初始條件：棧s不存在。

操作結果：構造了一個空棧。

（2）判棧空：Empty_Stack ( s )。

初始條件：棧s已存在。

操作結果：若s為空棧，則返回1，否則返回0。

（3）入棧：Push_Stack ( s，x )。

初始條件：棧s已存在。

操作結果：在棧s的頂部插入一個新元素x，x成為新的棧頂元素，棧發生變化。

（4）出棧：Pop_Stack ( s )。

初始條件：棧s存在且非空。

操作結果：棧s的頂部元素從棧中刪除，棧中少了一個元素，棧發生變化。

（5）讀棧頂元素：Top_Stack ( s )。

初始條件：棧s存在且非空。

操作結果：棧頂元素作為結果返回，棧不變化。

3.1.2 棧的存儲結構和基本運算的實現

由于棧是運算受限的線性表，因此線性表的存儲結構對棧也是適用的，只是操作不同而已。

1.順序棧

利用順序存儲方式實現的棧稱為順序棧。類似于順序表的定義，棧中的數據元素用一個預設的足夠長度的一維數組來實現：datatype data[MAXSIZE]，棧底位置可以設置在數組的任意一個端點，而棧頂是隨著插入和刪除而變化的，用int top來作為棧頂的指針，指明當前棧頂的位置，同樣將data和top封裝在一個結構中，順序棧的類型描述如下：

#define MAXSIZE 100
typedef struct
      { datatype data[MAXSIZE];
        int top;
      } SeqStack

定義一個指向順序棧的指針：

SeqStack *s;

通常將0下標端設為棧底，這樣空棧時棧頂指針top=-1；入棧時，棧頂指針加1，即s->top++；出棧時，棧頂指針減1，即s->top--。

棧頂指針top與棧中數據元素的關系如圖3.2所示，其中圖3.2（a）為空棧，圖3.2（c）是A、B、C、D、E 5個元素依次入棧之后棧的狀態及棧頂指針所指位置，圖3.2（d）是在圖3.2（c）之后E、D相繼出棧，此時，棧中還有3個元素，或許最近出棧的元素D、E仍然在原先的單元存儲中，但由于top指針已經指向了新的棧頂，則存儲D、E的單元已經屬于無效數據，意味著元素D、E已不在棧中了，通過這個示意圖要深刻理解棧頂指針的作用。

對上述存儲結構基本操作的實現如下。

（1）置空棧：首先建立棧空間，然后初始化棧頂指針。

SeqStack *Init_SeqStack( )
       { SeqStack *s;
         S=malloc(sizeof(SeqStack));
         s->top= -1; return s;
       }

（2）判空棧。

int Empty_SeqStack(SeqStack *s)
   { if (s->top==-1) return 1;
     else return 0;
}

（3）入棧。

int Push_SeqStack (SeqStack *s, datatype x)
{ if (s->top==MAXSIZE-1) return 0;     /*棧滿不能入棧*/
     else { s->top++;
            s->data[s->top]=x;
            return 1;
           }
}

（4）出棧。

int Pop_SeqStack(SeqStack *s, datatype *x)
{ if (Empty_SeqStack ( s ) ) return 0;    /*棧空不能出棧 */
      else { *x=s->data[s->top];
             s->top--; return 1;
          }                               /*棧頂元素存入*x，返回*/
}

（5）取棧頂元素。

datatype Top_SeqStack(SeqStack *s)
      { if ( Empty_SeqStack ( s ) ) return 0;   /*棧空*/
         else return (s->data[s->top] );
      }

兩點說明：

① 對于順序棧，入棧時，首先判斷棧是否滿了，棧滿的條件為s->top==MAXSIZE-1，棧滿時，不能入棧，否則會出現空間溢出，引起錯誤，這種現象稱為上溢。

② 出棧和讀棧頂元素操作，先判斷棧是否為空，為空時不能操作，否則會產生錯誤。通常棧空時常作為一種控制轉移的條件。

2.鏈棧

用鏈式存儲結構實現的棧稱為鏈棧。通常鏈棧用單鏈表表示，因此其結點結構與單鏈表的結點結構相同，在此用LinkStack表示，即有：

typedef struct node
   { datatype data;
     struct node *next;
   } StackNode * LinkStack;

說明：top為棧頂指針，即LinkStack top。

因為棧中的主要運算是在棧頂插入、刪除的，顯然選鏈表的頭部做棧頂是最方便的，而且沒有必要像單鏈表那樣為了運算方便附加一個頭結點。通常將鏈棧表示為圖3.3所示的形式。鏈棧基本操作的實現如下。

（1）置空棧。

LinkStack Init_LinkStack( )
        { return NULL;
        }

（2）判棧空。

int Empty_LinkStack(LinkStack top)
{ if (top==NULL) return 1;
        else return 0;
}

（3）入棧。

LinkStack Push_LinkStack(LinkStack top, datatype x)
        { StackNode *s;
        s=malloc(sizeof(StackNode));
          s ->data=x;  s ->next=top;  top=s;
          return top;
        }

（4）出棧。

LinkStack Pop_LinkStack (LinkStack top, datatype *x)
       { StackNode *p;
        if (top==NULL) return NULL;
        else { *x=top->data;  p=top;  top=top->next;  free (p);
             return top;
             }
}

3.1.3 棧的應用舉例

由于棧的“后進先出”特點，在很多實際問題中都利用棧做一個輔助的數據結構來進行求解，下面通過幾個例子進行說明。

【例3.1】 數制轉換問題。

將十進制數N轉換為r進制的數，其轉換方法為利用輾轉相除法。以N=3467，r=8為例，轉換方法如下：

按逆序取余數，即得轉換結果：（3467）10=（6613）8。

可以看出，轉換得到的八進制數是按低位到高位的順序產生的，而轉換結果的輸出通常是從高位到低位依次輸出，恰好與產生過程相反，因此，在轉換過程中，每得到一位八進制數就將其進棧保存，轉換完畢后再依次出棧，則正好是轉換結果。

算法思想如下：當N>0時，重復步驟①和步驟②。

① 若N≠0，則將N % r壓入棧s中，執行步驟 ②；若N=0，將棧s的內容依次出棧，算法結束。

② 用N/r代替N，返回步驟 ①。

算法實現如下，分別用兩種不同的方法進行描述。

算法3.1（a） 算法3.1（b）

typedef int datatype;
void conversion( int N, int r)
    { SeqStack s;
      datetype x;
      Init_SeqStack(&s);
      while ( N )
          { Push_SeqStack ( &s ，N % r );
            N=N / r ;
          }
        while (! Empty_SeqStack(& s ) )
          { Pop_SeqStack (&s ，&x ) ;
            printf (" %d"，x ) ;
        }
}
#define L 10
void conversion( int N，int r )
  { int s[L], top;         /*定義一個順序棧*/
    int  x;
    top=-1;                /*初始化棧*/
    while ( N )
       { s [++top]=N % r;  /*將余數入棧 */
         N=N / r ;         /*商作為被除數繼續*/
         }
      while ( top != -1)
         { x=s[top - - ];
           printf( "%d", x );
           }
}

算法3.1（a）是將對棧的操作抽象為模塊調用，使問題的層次更加清楚；而算法3.1（b）中直接用int數組s和int 變量top作為一個棧來使用。兩種描述方法的實現過程其實是相同的，只是前者的可讀性要更清晰。初學者往往將棧視為一個很復雜的東西，不知道如何使用，通過這個例子可以消除棧的“神秘”。當應用程序中需要按數據保存時相反的順序使用數據時，就要想到棧。通常用順序棧較多，因為很便利。

在后面的例子中，為了在算法中表現出問題的層次，有關棧的操作調用了相關函數，像算法3.1（a）那樣，對余數的入棧操作：Push_SeqStack(&s，N % r )；因為是用C語言描述，第一個參數是棧的地址才能對棧進行加工（在后面的例子中，為了算法清楚、易讀，在不至于混淆的情況下，不再加地址運算符，請讀者注意）。

【例3.2】 表達式求值問題。

表達式求值是程序設計語言編譯中一個最基本的問題。它的實現也需要棧的運用。下面介紹的算法是由運算符優先級確定運算順序的對表達式求值算法。

一個表達式是由運算數（operand）、運算符（operator）和界限符（delimiter）組成的有意義的式子。一般地，運算數既可以是常量又可以是被說明的變量或常量標識符。運算符從運算數的個數上分，有單目運算符和雙目運算符；從運算類型上分，有算術運算符、關系運算符和邏輯運算符。界限符主要是指左右括號和表達式結束符。在此僅限于討論只含常量的雙目運算的算術表達式。

假設所討論的算術運算符包括：+、-、*、/、%、^（乘方）和括號（）。

設運算規則為：

（1）運算符的優先級為：（）→ ^ → *、/、%→ +、-；

（2）有括號出現時先算括號內的，后算括號外的，對于多層括號，由內向外進行；

（3）乘方連續出現時先算最右面的。

可以將表達式作為一個滿足表達式語法規則的串來存儲，如3*2^（4+2*2-1*3）-5。

為實現表達式求值，需要設置兩個棧：一個稱為運算符棧OPTR，用以寄存運算符；另一個稱為運算數棧OPND，用以寄存運算數和運算結果。求值的處理過程是：自左至右掃描表達式的每一個字符，當掃描到運算數時，就將其壓入棧OPND；當掃描到運算符時，若這個運算符比OPTR棧頂運算符的優先級高則入棧OPTR，繼續向后處理，若這個運算符比OPTR棧頂運算符的優先級低則從OPND棧中彈出兩個運算數，從OPTR棧中彈出棧頂運算符進行運算，并將運算結果壓入棧OPND，繼續處理當前字符，直到遇到結束符為止。

根據運算規則，左括號“(”在棧外時它的級別最高，而進棧后它的級別則最低了；乘方運算的結合性是自右向左，所以，它的棧外級別高于棧內。也就是說，有的運算符棧內、棧外的優先級別是不同的。當遇到右括號“)”時，一直需要對OPTR棧進行出棧操作，并彈出相應的操作數，做對應的運算，直到遇到棧頂為左括號“(”將其出棧為止。

OPND棧初始化為空，為了使表達式中的第一個運算符入棧，OPTR棧中預設一個最低級的運算符“（”。根據以上分析，每個運算符的棧內、棧外優先級別如下：

以上算法的基本思想是：

（1）首先置OPND棧為空棧，表達式起始符“(”為OPTR棧的棧底元素；

（2）依次讀入表達式中的每個字符，若是運算數則進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優先級后作相應操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素為“(”且當前讀入的字符為“#”)。

算法3.2 表達式求值算法。

OperandType EvaluateExpression( )
   {    /*算術表達式求值的算符優先算法，設OPTR和OPND分別為運算符棧和運算數棧*/
        /*OP為運算符集合*/
      Init_Stack (OPTR)； Push_Stack (OPTR, '(' )；
      Init_Stack (OPND)； c=getchar( )；
      while ( c!='#' )
         { if (!In (c, OP))                           /*不是運算符則進棧*/
                { Push_Stack (OPND,c); c=getchar(); }
      else
                switch (Precede(GetTop(OPTR),c))
                   case '<':                          /*棧頂元素優先權低*/
                            Push_Stack (OPTR,c); c=getchar();
                            break;
              case '=':                               /*脫括號并接受下一字符*/
                            Pop_Stack (OPTR,x); c=getchar();
                            break;
              case '>':                               /*退棧并將運算結果入棧*/
                            Pop_Stack (OPTR, theta);
                            Pop_Stack (OPND, b);
                            Pop_Stack (OPND, a);
                            Push_Stack (OPND, Operate(a, theta, b));
                            break;
                    }                                 /*Switch*/
                }                                     /*while*/
                  return GetTop(OPND);
       }                                              /*EvaluateExpression*/

算法3.2中還調用了兩個函數。其中，Precede是判定OPTR棧的棧頂運算符與讀入的運算符之間優先關系的函數；Operate為進行二元運算a θ b的函數，如果是編譯表達式，則產生這個運算的一組相應指令并返回存放結果的中間變量名；如果是解釋執行表達式，則直接進行該運算，并返回運算的結果。

表達式3*2^(4+2*2-1*3)-5求值過程中兩個棧的狀態情況如表3.1所示。

在實際編譯程序中，為了處理方便，常常首先把表達式轉換成等價的后綴表達式。所謂后綴表達式，是指將運算符放在運算數之后的表達式。在后綴表達式中，不再需要括號，所有的計算按運算符出現的順序嚴格地從左向右進行，而不用再考慮運算符的級別和運算規則。如表達式3*2^(4+2*2-1*3)-5的后綴表達式為：3 2 4 2 2 *+1 3 * - ^ * 5 - 。

表3.1 表達式3*2^(4+2*2-1*3)-5的求值過程

3.1.4 棧與遞歸的實現

棧的另一個非常重要的應用就是在程序設計語言中實現遞歸。遞歸是指在定義自身的同時又出現對自身的引用。如果一個函數在其定義體內直接調用自己，則稱其為直接遞歸函數；如果一個函數經過一系列中間調用語句，通過其他函數間接調用自己，則稱其為間接遞歸函數。

1.具有遞歸特性的問題

現實中，許多問題具有固有的遞歸特性。

（1）遞歸定義的數學函數

很多數學函數是遞歸定義的，如階乘函數可寫成遞歸定義：

以上函數用C語言實現如下：

long Fact ( int n )
    {  long f;                      /*長整數類型可以使數據不容易溢出*/
       if ( n== 0 ) f=1;
         else f=n * Fact( n - 1 );
       return f;
}

（2）遞歸數據結構的處理

在本書的后續章節中將要學習的一些數據結構，如二叉樹、樹等，由于結構本身固有的遞歸特性，因此自然地采用遞歸方法進行處理。

（3）遞歸求解方法

許多問題的求解可以通過遞歸分解的方法實現，雖然有些問題本身沒有明顯的遞歸結構，但用遞歸方法求解比迭代求解更簡單，也更直觀，如八皇后問題、Hanoi塔問題等。

n階Hanoi塔問題：假設有三個分別命名為X、Y、Z的塔座，在塔座X上疊放著n個直徑大小各不相同、小盤壓在大盤之上的圓盤堆。現要求將塔座X上的n個圓盤移至塔座Z上，并仍按同樣的順序疊放。移動圓盤時必須遵循下列規則：

① 每一次只能夠移動一個圓盤；

② 圓盤可以插放在X、Y和Z中任何一個塔座上；

③ 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。

解決以上問題的基本思想如下：

當n=1時，問題簡單，只要將該圓盤從塔座X上移動到塔座Z上即可；

當n>1時，需要利用塔座Y作為輔助塔座，若能設法將除底下最大的圓盤之外的n-1個圓盤從塔座X移動到塔座Y上，就可以將最大的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的其余n-1個圓盤移動到塔座Z上。而如何將n-1個圓盤從一個塔座移至另一個塔座，則與原問題具有相同的特征屬性，只是問題的規模小1，因此可以用同樣的方法求解。

算法3.3 求解n階Hanoi塔問題的遞歸算法。

void Hanoi ( int n, char x, char y, char z )
     /*將塔座x上從上到下編號為1至n，且按直徑由小到大疊放的n個圓盤，按規則移動到塔座
     z上，塔座y用做輔助塔座。*/
     { if ( n==1 )
            move ( x, n, z ) ;         /*將編號為1的圓盤從塔座x移動到塔座z*/
          else
             { Hanoi ( n-1, x, z, y ); /*將x上編號為1至n-1的圓盤移至y，z作為輔助塔座*/
               move ( x, n, z );       /*將編號為n的圓盤從x移動到z */
               Hanoi ( n-1, y, x, z ); /*將y上編號為1至n-1的圓盤移至z，x作為輔助塔座*/
             }
}

掌握遞歸的具體執行過程對于理解遞歸具有重要作用。

下面就以三個圓盤的移動為例來說明以上遞歸函數Hanoi ( 3, A, B, C )的具體遞歸調用過程，如圖3.4所示。

Hanoi ( 3, A, B, C )    /*調用函數hanoi將A上的3個圓盤移至B，C作為輔助塔*/
      Hanoi ( 2, A, C, B );    /*將A上的2個圓盤移至B，C作為輔助塔*/
          Hanoi ( 1, A, B, C ); /*將A上的1個圓盤移至C */
              move ( A, 1, C ); /*將1號圓盤從A搬到C */
          move ( A, 2, C );   /*將2號圓盤從A搬到B */
          Hanoi ( 1, C, A, B ); /*將C上的1個圓盤移至B */
              move ( C, 1, B ); /*將1號圓盤從C搬回到B*/
      move ( A, 3, C );      /*將3號圓盤從A搬到C */
      Hanoi ( 2, B, A, C );   /*將B上的2個圓盤移至C，A作輔助塔*/
          Hanoi ( 1, B, C, A ); /*將B上的1個圓盤移至C */
     move ( B, 2, C );   /*將2號圓盤從B搬到C */
     Hanoi ( 1, A, B, C ); /*將A上的1個圓盤移至C */
         move (A, 1, C ); /*將1號圓盤從A搬到C */

通過上面的例子可以看出，遞歸既是強有力的數學方法，又是程序設計中一個非常有用的工具。其特點是對問題描述簡潔，結構清晰。

2.遞歸算法的設計方法與遞歸過程的實現

所謂遞歸算法，就是在算法中直接或間接調用自身的算法。應用遞歸算法的前提有兩個：

（1）原問題可以層層分解為類似的子問題，且子問題比原問題的規模更小；

（2）規模最小的子問題具有直接解，即不需要再調用自身。

設計遞歸算法的原則就是通過自身的簡單情況來定義自身，設計遞歸算法的方法如下。

（1）尋找分解方法：將原問題轉化為子問題求解（例如n!=n*(n-1)!）。

（2）設計遞歸出口：即根據規模最小的子問題確定遞歸的終止條件（例如求解n！，當n=1時，n!=1）。

為更好地理解遞歸函數的實現過程，有必要回顧函數調用的系統實現過程。在實現函數調用過程時，需要解決兩個問題：一是如何實現函數的調用；二是如何實現函數的返回。

實現函數調用，系統需要做三件事：

（1）保留調用函數本身的參數與返回地址；

（2）為被調用函數的局部變量分配存儲空間，并給對應的參數賦值；

（3）將程序控制轉移到被調用函數的入口。

從被調用函數返回到調用函數之前，系統也應完成三件事：

（1）保存被調用函數的計算結果，即返回結果；

（2）釋放被調用函數的數據區，恢復調用函數原先保存的參數；

（3）依照原先保存的返回地址，將程序控制轉移到調用函數的相應位置。

在實現函數調用時，應按照“先調用的后返回”原則處理調用過程，因此上述函數調用時函數之間的信息傳遞和控制轉移必須通過棧來實現。在實際實現中，系統將整個程序運行所需的數據空間安排在一個棧中，每當調用一個函數時，就為它在棧頂分配一個存儲區（壓棧），而當從一個函數退出時，就釋放它的存儲區（出棧）。顯然，當前正在運行的函數的數據區必然在棧頂。

在一個遞歸函數的運行過程中，調用函數和被調用函數是同一個函數，因此，與每次調用時相關的一個重要概念就是遞歸函數運行的“層次”。假設調用該遞歸函數的主函數為第0層，則從主函數調用遞歸函數為進入第1層，從第1層再次調用遞歸函數為進入第2層，以此類推，從第i層遞歸調用自身則進入“下一層”，即第i+1層。反之，退出第i層則應返回至“上一層”，即i-1層。為了保證遞歸函數正確執行，系統需要設立一個遞歸工作棧作為整個遞歸函數執行期間的數據存儲區。每層遞歸所需信息構成一個工作記錄，其中包括遞歸函數的所有實參和局部變量，以及上一層的返回地址等。每進入一層遞歸，就產生一個新的工作記錄壓棧；每退出一層遞歸，就從棧頂彈出一個工作記錄釋放。因此當前執行層的工作記錄必為棧頂元素，稱該記錄為活動記錄，并稱指示活動記錄的棧頂指針為環境指針。由于遞歸工作棧由系統來管理，不需要用戶操心，所以用遞歸法編程非常方便。

【例3.3】 2階Fibonacci數列的遞歸實現。

算法3.4 求2階Fibonacci數列的遞歸算法。

int Fib ( int n )
{ if ( n== 0 )  return 0;
  else  if  ( n== 1 )  return 1;
         else  return  Fib ( n –1 )+Fib ( n–2 )
}

圖3.5給出了Fib(4)遞歸調用過程的示意圖，圖3.6給出了遞歸調用過程中棧的狀態變化情況。

可以看出，計算Fib( n )的遞歸函數在n>1時的執行過程大致可分為五個階段：

① 調用Fib ( n-1 )，即進棧操作；

② 返回Fib ( n-1 )的值，即出棧操作；

③ 調用Fib(n-2 )，再次進棧；

④ 返回Fib ( n-2 )的值，出棧；

⑤ 計算Fib ( n )的值，然后返回。