C語言數據結構基礎學習筆記——棧和隊列

之前我們學過了普通的線性表，接下來我們來瞭解一下兩種特殊的線性表——棧和隊列。

棧是只允許在一端進行插入或刪除的線性表。

棧的順序存儲結構也叫作順序棧，對於棧頂指針top，當棧為空棧時，top=-1；當棧為滿棧時，top=MaxSize-1。順序棧的定義為：

#define MaxSize 50                            //定義棧中元素的最大個數 
typedef struct{                                
    Elemtype data[MaxSize];                   //存放棧中元素 
    int top;                                  //棧頂指針 
}SqStack;                                     //順序棧的簡寫

順序棧的入棧操作為：

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1) return false;
    S.data[++S.top]=x; return true;
} 

順序棧的出棧操作為：

bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1) return false;
    x=S.data[S.top--];　　　　　　
    return true;
} 

順序棧讀取棧頂元素為：

bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1) return false;
    x=S.data[S.top];
    return true;
} 

順序棧讀取棧頂元素與出棧操作對比，註意讀取棧頂元素時棧頂指針沒有自減。

對於一個數組，如果只從數組頭部開始入棧，並沒有達到很高的空間利用率，因此我們引入共用棧的概念。共用棧是兩個棧共用同一個數組，分別從數組頭部和數組尾部開始開始入棧。其定義為：

#define MaxSize 100                            //定義棧中元素的最大個數 
typedef struct{                                
    Elemtype data[MaxSize];                    //存放棧中元素 
    int top1;                                  //棧1頂指針 
    int top2;                                  //棧2頂指針 
}SqDoubleStack;                                //共用棧的簡寫
bool Push(SqStack &S,ElemType x,int stackNum){
    if(S.top1+1==S.top2) return false;
    if(stackNum==1) S.data[++S.top1]=x; 
    else if(stackNum==2) S.data[--S.top2]=x;
    return true;
} 

共用棧的滿棧條件是top1+1=top2。

同時，棧也有鏈式存儲結構，叫作鏈棧，它空棧時top=NULL，一般不會滿棧。鏈棧的定義為：

typedef struct SNode{                
    ElemType data;                     //數據域
    struct SNode *next;                //指針域 
}SNode,*SLink;                         //鏈式棧的結點
typedef struct LinkStack{
    SLink top;                         //棧頂指針 
    int count;                         //鏈式棧結點數 
}LinkStack; 

棧有著豐富的應用場景，比較經典的題目有括弧的匹配以及尾碼表達式的求值。

①括弧的匹配：給你一串雜亂的大，中，小括弧的序列，讓你判斷這裡的括弧序列滿不滿足數學計算的規律（括弧套括弧）。主要思路是將所有的左括弧依次入棧，碰到右括弧出棧匹配，若是不同種的括弧返回false，若是同一種括弧則繼續以上操作，直到空棧並且數組中的字元串遍歷完成，返回true。

②尾碼表達式的計算：尾碼表達式是電腦最喜歡的一種表達式方式，例如（5+10+1*13）/14這個中綴表達式，它的尾碼表達式為5 10 + 1 13 * + 14 /，其將每一步計算的運算符號置後。利用棧計算尾碼表達式的主要思路是：①將數字5入棧，再將數字10入棧；②當指針碰到運算符+時，將棧中的前兩個元素出棧進行計算（後出棧的數在前位），結果入棧，如本例值15入棧；③同上一步，計算1*13得13入棧，此時棧底值15，棧頂值13；④同上一步，指針碰到運算符+，將15與13求和，得值28入棧；⑤再同上一步，計算28/14=2入棧；⑥此時字元串數組遍歷完畢，棧中的唯一值2則為表達式的結果。

棧思想的最重要的一個應用便是遞歸，遞歸是指在一個函數、過程或數據結構中的定義中又應用了它自身的編程思想。理解遞歸的一個基礎方法便是找到遞歸式和遞歸邊界，我們來看兩個例子：

①用遞歸求n的階乘：

int F(int n){
    if(n==0) return 1;                //遞歸邊界 
    else return n*F(n-1);             //遞歸式 
} 

②求斐波那契數列的第n項：

int Fib(int n){
    if(n==0) return 0;                 //遞歸邊界
    else if(n==1) return 1;            //遞歸邊界
    else return Fib(n-1)+Fib(n-2);     //遞歸式 
}

遞歸式是每一次遞歸過程的計算核心，而遞歸邊界就是每一次遞歸的結束標誌。

另一種特殊的線性表是隊列，隊列的定義是只允許在一端進行插入，而在另一端進行刪除的線性表。

隊列的順序存儲結構是順序隊列，其定義為：

#define MaxSize 50                             //定義隊列中元素的最大個數 
typedef struct{                                
    Elemtype data[MaxSize];                    //存放隊列中元素 
    int front,rear;                            //隊頭指針和隊尾指針 
}SqQueue;         

但對於一個數組隊列來說，每一次入隊和出隊都會浪費一個數組位置，於是我們引入迴圈隊列的概念，隊尾指針rear在指到隊尾後會回到下標為0的位置（利用取餘來實現），即每一次rear和front的更新基於以下操作：rear=(rear+1)%MaxSize,front=(front+1)%MaxSize。

但是這樣又產生了新的問題，rear=front到底是隊空還是隊滿無法判斷。這樣的問題有以下兩種解決辦法：①設一個frag，作為標誌位，當隊滿時frag=1；②犧牲一個數組位置，保留一個空餘單元，此時隊滿的判斷標準變成了(rear+1)%MaxSize=front，隊列中的元素數計算方法為：(rear-front+MaxSize)%MaxSize。

迴圈隊列的入隊操作為：

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front) return false;    //隊滿
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true; 
} 

迴圈隊列的出隊操作為：

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front) return false;     //隊空
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
} 

隊列鏈式存儲的定義為：

typedef struct{                
    ElemType data;                    //數據域
    struct LinkNode *next;            //指針域 
}LinkNode;                            //鏈式隊列的結點
typedef struct{
    LinkNode *front,*rear;            //隊頭和隊尾指針 
}LinkQueue;

鏈式隊列的入隊和出隊類似於鏈表的相應操作。