代碼如下：

/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){
    if(stackNumber == 0){
        if(S->top0 == -1){
            return ERROR;   //說明棧0已經(jīng)是空棧，溢出
        }
        *e = S->data[S->top0--]; //將棧0的棧頂元素出棧，隨后棧頂指針減1
    }else if(stackNumber == 1){
        if(S->top1 == MAXSIZE){
            return ERROR;   //說明棧1是空棧，溢出
        }
        *e = S->data[S->top1++];    //將棧1的棧頂元素出棧，隨后棧頂指針加1
    }
    return OK;
}

三、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1、鏈棧

采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧，鏈棧的優(yōu)點(diǎn)是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實(shí)現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的。這里規(guī)定鏈棧沒有頭節(jié)點(diǎn)，Lhead指向棧頂元素，如下圖所示。

對于空棧來說，鏈表原定義是頭指針指向空，那么鏈棧的空其實(shí)就是top=NULL的時候。

鏈棧的結(jié)構(gòu)代碼如下：

/*棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)*/
/*構(gòu)造節(jié)點(diǎn)*/
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*構(gòu)造鏈棧*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

2、鏈棧的基本算法

（1）鏈棧的進(jìn)棧

對于鏈棧的進(jìn)棧push操作，假設(shè)元素值為e的新節(jié)點(diǎn)是s，top為棧頂指針，示意圖如下：

代碼如下：

/*插入元素e為新的棧頂元素*/
Status Push(LinkStack *S, ElemType e){
    LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;    //把當(dāng)前的棧頂元素賦值給新節(jié)點(diǎn)的直接后繼
    S->top = p; //將新的結(jié)點(diǎn)S賦值給棧頂指針
    S->count++;
    return OK;
}

（2）鏈棧的出棧

鏈棧的出棧pop操作，也是很簡單的三句操作。假設(shè)變量p用來存儲要刪除的棧頂結(jié)點(diǎn)，將棧頂指針下移以為，最后釋放p即可，

如下圖所示：

代碼如下：

/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S)){
        return ERROR;
    }
    *e = S->top->data;
    p = S->top; //將棧頂結(jié)點(diǎn)賦值給p
    S->top = S->top->next;  //使得棧頂指針下移一位，指向后一結(jié)點(diǎn)
    free(p);    //釋放結(jié)點(diǎn)p
    S->count--;
    return OK;
}

3、性能分析

鏈棧的進(jìn)棧push和出棧pop操作都很簡單，時間復(fù)雜度均為O(1)。
對比一下順序棧與鏈棧,它們在時間復(fù)雜度上是一樣的,均為O(1)。對于空間性能,順序棧需要事先確定一個固定的長度,可能會存在內(nèi)存空間浪費(fèi)的問題,但它的優(yōu)勢是存取時定位很方便,而鏈棧則要求每個元素都有指針域,這同時也增加了一些內(nèi)存開銷,但對于棧的長度無限制。所以它們的區(qū)別和線性表中討論的一樣,如果棧的使用過程中元素變化不可預(yù)料,有時很小,有時非常大,那么最好是用鏈棧,反之,如果它的變化在可控范圍內(nèi),建議使用順序棧會更好一些。

四、棧的應(yīng)用——遞歸

1、遞歸的定義

遞歸是一種重要的程序設(shè)計方法。簡單地說,若在一個函數(shù)、過程或數(shù)據(jù)結(jié)構(gòu)的定義中又應(yīng)用了它自身,則這個函數(shù)、過程或數(shù)據(jù)結(jié)構(gòu)稱為是遞歸定義的,簡稱遞歸。
它通常把一個大型的復(fù)雜問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解,遞歸策略只需少量的代碼就可以描述岀解題過程所需要的多次重復(fù)計算,大大減少了程序的代碼量但在通常情況下,它的效率并不是太高。

2、斐波那契數(shù)列

在解釋斐波那契數(shù)列之前，我們想看經(jīng)典的兔子繁殖的問題：

說如果兔子在出生兩個月后,就有繁殖能力,一對兔子每個月能生出一對小兔子 來。假設(shè)所有兔都不死,那么一年以后可以繁殖多少對兔子呢?

• 第一個月初有一對剛誕生的兔子第
• 二個月之后（第三個月初）它們可以生育
• 每月每對可生育的兔子會誕生下一對新兔子
• 兔子永不死去

我們拿新出生的一對小兔子分析一下:第一個月小兔子沒有繁殖能力,所以還是一對;兩個月后,生下一對小兔子數(shù)共有兩對;三個月以后,老兔子又生下一對,因?yàn)樾⊥米舆€沒有繁殖能力,所以一共是三對…依次類推得出這樣一個圖：

從這個圖可以看出，斐波那契數(shù)列數(shù)列有一個明顯的特點(diǎn)，即：前面兩項(xiàng)之和，構(gòu)成了后一項(xiàng)。
如果用數(shù)學(xué)函數(shù)定義斐波那契數(shù)列，那就是：

而這個，就是遞歸的一個典型例子，用程序?qū)崿F(xiàn)時如下：

/*斐波那契數(shù)列的實(shí)現(xiàn)*/
int Fib(int n){
    if(n == 0){
        return 0;   //邊界條件
    }else if(n == 1){
        return 1;	//邊界條件
    }else{
        return Fib(n-1) + Fib(n-2); //遞歸表達(dá)式
    }
}

必須注意遞歸模型不能是循環(huán)定義的,其必須滿足下面的兩個條件

• 遞歸表達(dá)式(遞歸體)
• 邊界條件(遞歸出口)

遞歸的精髓在于能否將原始問題轉(zhuǎn)換為屬性相同但規(guī)模較小的問題
在遞歸調(diào)用的過程中,系統(tǒng)為每一層的返回點(diǎn)、局部變量、傳入實(shí)參等開辟了遞歸工作棧來進(jìn)行數(shù)據(jù)存儲,遞歸次數(shù)過多容易造成棧溢出等。而其效率不高的原因是遞歸調(diào)用過程中包含很多重復(fù)的計算。下面以n=5為例,列出遞歸調(diào)用執(zhí)行過程,如圖所示：

如圖可知，程序每往下遞歸一次，就會把運(yùn)算結(jié)果放到棧中保存，直到程序執(zhí)行到臨界條件，然后便會把保存在棧中的值按照先進(jìn)后出的順序一個個返回，最終得出結(jié)果。

五、棧的應(yīng)用——四則運(yùn)算表達(dá)式求值

1、后綴表達(dá)式計算結(jié)果

表達(dá)式求值是程序設(shè)計語言編譯中一個最基本的問題,它的實(shí)現(xiàn)是棧應(yīng)用的一個典型范例。中綴表達(dá)式不僅依賴運(yùn)算符的優(yōu)先級,而且還要處理括號。后綴表達(dá)式的運(yùn)算符在操作數(shù)后面，在后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級,沒有括號,只有操作數(shù)和運(yùn)算符。例如中綴表達(dá)式 A + B ? ( C ? D ) ? E / F A+B*(C-D)-E/F A+B?(C?D)?E/F所對應(yīng)的后綴表達(dá)式為 A B C D ? ? + E F / ? ABCD-*+EF/- ABCD??+EF/?。

后綴表達(dá)式計算規(guī)則：從左到右遍歷表達(dá)式的每個數(shù)字和符號，遇到是數(shù)字就進(jìn)棧，遇到是符號，就將處于棧頂兩個數(shù)字出棧，進(jìn)項(xiàng)運(yùn)算，運(yùn)算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。

后綴表達(dá)式 A B C D ? ? + E F / ? ABCD-*+EF/- ABCD??+EF/?求值的過程需要12步，如下表所示：

讀者也可將后綴表達(dá)式與原運(yùn)算式對應(yīng)的表達(dá)式樹(用來表示算術(shù)表達(dá)式的二元樹)的后序遍歷進(jìn)行比較,可以發(fā)現(xiàn)它們有異曲同工之妙。
如下圖則是 A + B ? ( C ? D ) ? E / F A+B*(C-D)-E/F A+B?(C?D)?E/F對應(yīng)的表達(dá)式，它的后序遍歷即是表達(dá)式 A B C D ? ? + E F / ? ABCD-*+EF/- ABCD??+EF/?。

2、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

我們把平時所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式,即 a + b ? a ? ( ( c + d ) / e ? f ) + g a+b-a*((c+d)/e-f)+g a+b?a?((c+d)/e?f)+g叫做中綴
表達(dá)式。因?yàn)樗械倪\(yùn)算符號都在兩數(shù)字的中間,現(xiàn)在我們的問題就是中綴到后綴的轉(zhuǎn)化。

規(guī)則:從左到右遍歷中綴表達(dá)式的每個數(shù)字和符號,若是數(shù)字就輸出,即成為后
綴表達(dá)式的一部分;若是符號,則判斷其與棧頂符號的優(yōu)先級,是右括號或優(yōu)先級低于棧頂符號(乘除優(yōu)先加減)則棧頂元素依次出棧并輸出,并將當(dāng)前符號進(jìn)棧,一直到最終輸出后綴表達(dá)式為止。

例：將中綴表達(dá)式 a + b ? a ? ( ( c + d ) / e ? f ) + g a+b-a*((c+d)/e-f)+g a+b?a?((c+d)/e?f)+g轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式。

分析：需要根據(jù)操作符

的優(yōu)先級來進(jìn)行棧的變化,我們用icp來表示當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級,該運(yùn)算符進(jìn)棧后的優(yōu)先級為isp,則運(yùn)算符的優(yōu)先級如下表所示[isp是棧內(nèi)優(yōu)先( in stack priority)數(shù),icp是棧外優(yōu)先( in coming priority)數(shù)]。

我們在表達(dá)式后面加上符號‘#’,表示表達(dá)式結(jié)束。

具體轉(zhuǎn)換過程如下：

即相應(yīng)的后綴表達(dá)式為 a b + a c d + e / f ? ? ? g + ab+acd+e/f-*-g+ ab+acd+e/f???g+。

隊(duì)列

一、隊(duì)列的基本概念

1、隊(duì)列的定義

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡稱FIFO。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。

隊(duì)頭（Front）：允許刪除的一端，又稱隊(duì)首。
隊(duì)尾（Rear）：允許插入的一端。
空隊(duì)列：不包含任何元素的空表。

2、隊(duì)列的常見基本操作

• InitQueue(&Q)：初始化隊(duì)列，構(gòu)造一個空隊(duì)列Q。
• QueueEmpty(Q)：判隊(duì)列空，若隊(duì)列Q為空返回true，否則返回
• false。EnQueue(&Q, x)：入隊(duì)，若隊(duì)列Q未滿，將x加入，使之成為新的隊(duì)尾。
• DeQueue(&Q, &x)：出隊(duì)，若隊(duì)列Q非空，刪除隊(duì)頭元素，并用x返回。
• GetHead(Q, &x)：讀隊(duì)頭元素，若隊(duì)列Q非空，則將隊(duì)頭元素賦值給x

二、隊(duì)列的順序存儲結(jié)構(gòu)

隊(duì)列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲單元存放隊(duì)列中的元素，并附設(shè)兩個指針：隊(duì)頭指針 front指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)尾元素的下一個位置。

1、順序隊(duì)列

隊(duì)列的順序存儲類型可描述為:

#define MAXSIZE 50	//定義隊(duì)列中元素的最大個數(shù)
typedef struct{
	ElemType data[MAXSIZE];	//存放隊(duì)列元素
	int front,rear;
}SqQueue;

初始狀態(tài)（隊(duì)空條件）：Q->front == Q->rear == 0。
進(jìn)隊(duì)操作：隊(duì)不滿時，先送值到隊(duì)尾元素，再將隊(duì)尾指針加1。
出隊(duì)操作：隊(duì)不空時，先取隊(duì)頭元素值，再將隊(duì)頭指針加1。

如圖d，隊(duì)列出現(xiàn)“上溢出”，然而卻又不是真正的溢出，所以是一種“假溢出”。

2、循環(huán)隊(duì)列

解決假溢出的方法就是后面滿了，就再從頭開始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊(duì)列。
當(dāng)隊(duì)首指針Q->front = MAXSIZE-1后，再前進(jìn)一個位置就自動到0，這可以利用除法取余運(yùn)算（%）來實(shí)現(xiàn)。

初始時：Q->front = Q->rear=0。隊(duì)首指針進(jìn)1：Q->front = (Q->front + 1) % MAXSIZE。隊(duì)尾指針進(jìn)1：Q->rear = (Q->rear + 1) % MAXSIZE。隊(duì)列長度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

出隊(duì)入隊(duì)時，指針都按照順時針方向前進(jìn)1，如下圖所示：

那么，循環(huán)隊(duì)列隊(duì)空和隊(duì)滿的判斷條件是什么呢？
顯然，隊(duì)空的條件是 Q->front == Q->rear 。若入隊(duì)元素的速度快于出隊(duì)元素的速度，則隊(duì)尾指針很快就會趕上隊(duì)首指針，如圖( d1 ）所示，此時可以看出隊(duì)滿時也有 Q ->front == Q -> rear 。
為了區(qū)分隊(duì)空還是隊(duì)滿的情況，有三種處理方式：
（1）犧牲一個單元來區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)時少用一個隊(duì)列單元，這是種較為普遍的做法，約定以“隊(duì)頭指針在隊(duì)尾指針的下一位置作為隊(duì)滿的標(biāo)志”，如圖 ( d2 ）所示。

• 隊(duì)滿條件： (Q->rear + 1)%Maxsize == Q->front
• 隊(duì)空條件仍： Q->front == Q->rear
• 隊(duì)列中元素的個數(shù)： (Q->rear - Q ->front + Maxsize)% Maxsize

（2）類型中增設(shè)表示元素個數(shù)的數(shù)據(jù)成員。這樣，隊(duì)空的條件為 Q->size == O ；隊(duì)滿的條件為 Q->size == Maxsize 。這兩種情況都有 Q->front == Q->rear
（3）類型中增設(shè)tag 數(shù)據(jù)成員，以區(qū)分是隊(duì)滿還是隊(duì)空。tag 等于0時，若因刪除導(dǎo)致 Q->front == Q->rear ，則為隊(duì)空；tag 等于 1 時，若因插入導(dǎo)致 Q ->front == Q->rear ，則為隊(duì)滿。

我們重點(diǎn)討論第一種方法

3、循環(huán)隊(duì)列常見基本算法

（1）循環(huán)隊(duì)列的順序存儲結(jié)構(gòu)

typedef int ElemType;   //ElemType的類型根據(jù)實(shí)際情況而定，這里假定為int
#define MAXSIZE 50  //定義元素的最大個數(shù)
/*循環(huán)隊(duì)列的順序存儲結(jié)構(gòu)*/
typedef struct{
    ElemType data[MAXSIZE];
    int front;  //頭指針
    int rear;   //尾指針,若隊(duì)列不空，指向隊(duì)列尾元素的下一個位置
}SqQueue;

（2）循環(huán)隊(duì)列的初始化

/*初始化一個空隊(duì)列Q*/
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

（3）循環(huán)隊(duì)列判隊(duì)空

/*判隊(duì)空*/
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        return true;
    }else{
        return false;
    }
}

（4）求循環(huán)隊(duì)列長度

/*返回Q的元素個數(shù)，也就是隊(duì)列的當(dāng)前長度*/
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

（5）循環(huán)隊(duì)列入隊(duì)

/*若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素*/
Status EnQueue(SqQueue *Q, ElemType e){
    if((Q->real + 1) % MAXSIZE == Q->front){
        return ERROR;   //隊(duì)滿
    }
    Q->data[Q->rear] = e;   //將元素e賦值給隊(duì)尾
    Q->rear = (Q->rear + 1) % MAXSIZE;  //rear指針向后移一位置，若到最后則轉(zhuǎn)到數(shù)組頭部
    return OK;
}

（6）循環(huán)隊(duì)列出隊(duì)

/*若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值*/
Status DeQueue(SqQueue *Q, ElemType *e){
    if(isEmpty(Q)){
        return REEOR;   //隊(duì)列空的判斷
    }
    *e = Q->data[Q->front]; //將隊(duì)頭元素賦值給e
    Q->front = (Q->front + 1) % MAXSIZE;    //front指針向后移一位置，若到最后則轉(zhuǎn)到數(shù)組頭部
}

三、隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1、鏈隊(duì)列

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)表示為鏈隊(duì)列，它實(shí)際上是一個同時帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表，只不過它只能尾進(jìn)頭出而已。

空隊(duì)列時，front和real都指向頭結(jié)點(diǎn)。

2、鏈隊(duì)列常見基本算法

（1）鏈隊(duì)列存儲類型

/*鏈?zhǔn)疥?duì)列結(jié)點(diǎn)*/
typedef struct {
	ElemType data;
	struct LinkNode *next;
}LinkNode;
/*鏈?zhǔn)疥?duì)列*/
typedef struct{
	LinkNode *front, *rear;	//隊(duì)列的隊(duì)頭和隊(duì)尾指針
}LinkQueue;

當(dāng)Q->front == NULL 并且 Q->rear == NULL 時，鏈隊(duì)列為空。

（2）鏈隊(duì)列初始化

void InitQueue(LinkQueue *Q){
	Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode));	//建立頭結(jié)點(diǎn)
	Q->front->next = NULL;	//初始為空
}

（3）鏈隊(duì)列入隊(duì)

Status EnQueue(LinkQueue *Q, ElemType e){
	LinkNode s = (LinkNode)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;	//把擁有元素e新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼
	Q->rear = s;	//把當(dāng)前的s設(shè)置為新的隊(duì)尾結(jié)點(diǎn)
	return OK;
}

（4）鏈隊(duì)列出隊(duì)

出隊(duì)操作時，就是頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改為它后面的結(jié)點(diǎn)，若鏈表除頭結(jié)點(diǎn)外只剩一個元素時，則需將rear指向頭結(jié)點(diǎn)。

/*若隊(duì)列不空，刪除Q的隊(duì)頭元素，用e返回其值，并返回OK，否則返回ERROR*/
Status DeQueue(LinkQueue *Q, Elemtype *e){
	LinkNode p;
	if(Q->front == Q->rear){
		return ERROR;
	}
	p = Q->front->next;	//將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p
	*e = p->data;	//將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給e
	Q->front->next = p->next;	//將原隊(duì)頭結(jié)點(diǎn)的后繼賦值給頭結(jié)點(diǎn)后繼
	//若刪除的隊(duì)頭是隊(duì)尾，則刪除后將rear指向頭結(jié)點(diǎn)
	if(Q->rear == p){
		Q->rear = Q->front;
	}
	free(p);
	return OK;
}

四、雙端隊(duì)列

1、定義

雙端隊(duì)列是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列，如下圖所示。其元素的邏輯結(jié)構(gòu)仍是線性結(jié)構(gòu)。將隊(duì)列的兩端分別稱為前端和后端，兩端都可以入隊(duì)和出隊(duì)。

在雙端隊(duì)列進(jìn)隊(duì)時，前端進(jìn)的元素排列在隊(duì)列中后端進(jìn)的元素的前面，后端進(jìn)的元素排列在隊(duì)列中前端進(jìn)的元素的后面。在雙端隊(duì)列出隊(duì)時，無論是前端還是后端出隊(duì)，先出的元素排列在后出的元素的前面。

2、特殊的雙端隊(duì)列

在實(shí)際使用中，根據(jù)使用場景的不同，存在某些特殊的雙端隊(duì)列。

輸出受限的雙端隊(duì)列：允許在一端進(jìn)行插入和刪除， 但在另一端只允許插入的雙端隊(duì)列稱為輸出受限的雙端隊(duì)列，如下圖所示。

輸入受限的雙端隊(duì)列：允許在一端進(jìn)行插入和刪除，但在另一端只允許刪除的雙端隊(duì)列稱為輸入受限的雙端隊(duì)列，如下圖所示。若限定雙端隊(duì)列從某個端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則該雙端隊(duì)列就蛻變?yōu)閮蓚€棧底相鄰接的棧。