bool StackEmpty(SqStack S){
    if(S.top == -1){
        return true;    //?？?
    }else{
        return false;   //不空
    }
}

（3）進(jìn)棧

進(jìn)棧操作push，代碼如下：

/*插入元素e為新的棧頂元素*/
Status Push(SqStack *S, ElemType e){
    //滿棧
    if(S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;   //棧頂指針增加一
    S->data[S->top] = e;    //將新插入元素賦值給棧頂空間
    return OK;
}

（4）出棧

出棧操作pop，代碼如下：

/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/
Status Pop(SqStack *S, ElemType *e){
    if(S->top == -1){
        return ERROR;
    }
    *e = S->data[S->top];   //將要刪除的棧頂元素賦值給e
    S->top--;   //棧頂指針減一
    return OK;
}

（5）讀棧頂元素

/*讀棧頂元素*/
Status GetTop(SqStack S, ElemType *e){
    if(S->top == -1){   //?？?
        return ERROR;
    }
    *e = S->data[S->top];   //記錄棧頂元素
    return OK;
}

3、共享棧（兩棧共享空間）

（1）共享棧概念

利用棧底位置相對不變的特征，可讓兩個順序棧共享一個一維數(shù)組空間，將兩個棧的棧底分別設(shè)置在共享空間的兩端，兩個棧頂向共享空間的中間延伸，

如下圖所示：

兩個棧的棧頂指針都指向棧頂元素，top0=-1時0號棧為空，top1=MaxSize時1號棧為空；僅當(dāng)兩個棧頂指針相鄰（top0+1=top1）時，判斷為棧滿。當(dāng)0號棧進(jìn)棧時top0先加1再賦值，1號棧進(jìn)棧時top1先減一再賦值出棧時則剛好相反。

（2）共享棧的空間結(jié)構(gòu)

代碼如下：

/*兩棧共享空間結(jié)構(gòu)*/
#define MAXSIZE 50  //定義棧中元素的最大個數(shù)
typedef int ElemType;   //ElemType的類型根據(jù)實際情況而定，這里假定為int
/*兩棧共享空間結(jié)構(gòu)*/
typedef struct{
	ElemType data[MAXSIZE];
	int top0;	//棧0棧頂指針
	int top1;	//棧1棧頂指針
}SqDoubleStack;

（3）共享棧進(jìn)棧

對于兩棧共享空間的push方法，我們除了要插入元素值參數(shù)外，還需要有一個判斷是棧0還是棧1的棧號參數(shù)stackNumber。

共享棧進(jìn)棧的代碼如下：

/*插入元素e為新的棧頂元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){
    if(S->top0+1 == S->top1){   //棧滿
        return ERROR;
    }
    if(stackNumber == 0){   //棧0有元素進(jìn)棧
        S->data[++S->top0] = e; //若棧0則先top0+1后給數(shù)組元素賦值
    }else if(satckNumber == 1){ //棧1有元素進(jìn)棧
        S->data[--S->top1] = e; //若棧1則先top1-1后給數(shù)組元素賦值
    }
    return OK;
}

（4）共享棧出棧

代碼如下：

/*若棧不空，則刪除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)點是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的。這里規(guī)定鏈棧沒有頭節(jié)點，Lhead指向棧頂元素，如下圖所示。

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

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

/*棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)*/
/*構(gòu)造節(jié)點*/
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é)點是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é)點的直接后繼
    S->top = p; //將新的結(jié)點S賦值給棧頂指針
    S->count++;
    return OK;
}

（2）鏈棧的出棧

鏈棧的出棧pop操作，也是很簡單的三句操作。假設(shè)變量p用來存儲要刪除的棧頂結(jié)點，將棧頂指針下移以為，最后釋放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é)點賦值給p
    S->top = S->top->next;  //使得棧頂指針下移一位，指向后一結(jié)點
    free(p);    //釋放結(jié)點p
    S->count--;
    return OK;
}

3、性能分析

鏈棧的進(jìn)棧push和出棧pop操作都很簡單，時間復(fù)雜度均為O(1)。
對比一下順序棧與鏈棧,它們在時間復(fù)雜度上是一樣的,均為O(1)。對于空間性能,順序棧需要事先確定一個固定的長度,可能會存在內(nè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ù)共有兩對;三個月以后,老兔子又生下一對,因為小兔子還沒有繁殖能力,所以一共是三對…依次類推得出這樣一個圖：

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

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

/*斐波那契數(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)為每一層的返回點、局部變量、傳入實參等開辟了遞歸工作棧來進(jìn)行數(shù)據(jù)存儲,遞歸次數(shù)過多容易造成棧溢出等。而其效率不高的原因是遞歸調(diào)用過程中包含很多重復(fù)的計算。下面以n=5為例,列出遞歸調(diào)用執(zhí)行過程,如圖所示：

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

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

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

表達(dá)式求值是程序設(shè)計語言編譯中一個最基本的問題,它的實現(xiàn)是棧應(yīng)用的一個典型范例。中綴表達(dá)式不僅依賴運算符的優(yōu)先級,而且還要處理括號。后綴表達(dá)式的運算符在操作數(shù)后面，在后綴表達(dá)式中已考慮了運算符的優(yōu)先級,沒有括號,只有操作數(shù)和運算符。例如中綴表達(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)項運算，運算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。

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

讀者也可將后綴表達(dá)式與原運算式對應(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)四則運算表達(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á)式。因為所有的運算符號都在兩數(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)前掃描到的運算符ch的優(yōu)先級,該運算符進(jìn)棧后的優(yōu)先級為isp,則運算符的優(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+。

隊列

一、隊列的基本概念

1、隊列的定義

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

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

2、隊列的常見基本操作

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

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

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

1、順序隊列

隊列的順序存儲類型可描述為:

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

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

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

2、循環(huán)隊列

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

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

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

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

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

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

我們重點討論第一種方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1、鏈隊列

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

空隊列時，front和real都指向頭結(jié)點。

2、鏈隊列常見基本算法

（1）鏈隊列存儲類型

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

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

（2）鏈隊列初始化

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

（3）鏈隊列入隊

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

（4）鏈隊列出隊

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

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

四、雙端隊列

1、定義

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

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

2、特殊的雙端隊列

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

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

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

到此這篇關(guān)于c語言數(shù)據(jù)結(jié)構(gòu)之棧和隊列詳解(Stack & Queue)的文章就介紹到這了,更多相關(guān)c語言據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！