c語言資料結構之棧和佇列詳解(Stack&Queue)

2022-08-30 18:01:44

簡介

【知識框架】

棧

一、棧的基本概念

1、棧的定義

棧（Stack）：是隻允許在一端進行插入或刪除的線性表。首先棧是一種線性表，但限定這種線性表只能在某一端進行插入和刪除操作。

棧頂（Top）：線性表允許進行插入刪除的那一端。
棧底（Bottom）：固定的，不允許進行插入和刪除的另一端。
空棧：不含任何元素的空表。

棧又稱為後進先出（Last In First Out）的線性表，簡稱LIFO結構

2、棧的常見基本操作

InitStack(&S)：初始化一個空棧S。

StackEmpty(S)：判斷一個棧是否為空，若棧為空則返回true，否則返回false。

Push(&S, x)：進棧（棧的插入操作），若棧S未滿，則將x加入使之成為新棧頂。

Pop(&S, &x)：出棧（棧的刪除操作），若棧S非空，則彈出棧頂元素，並用x返回。

GetTop(S, &x)：讀棧頂元素，若棧S非空，則用x返回棧頂元素。

DestroyStack(&S)：棧銷燬，並釋放S佔用的儲存空間（“&”表示參照呼叫）。

二、棧的順序儲存結構

1、棧的順序儲存

採用順序儲存的棧稱為順序棧，它利用一組地址連續的儲存單元存放自棧底到棧頂的資料元素，同時附設一個指標（top）指示當前棧頂元素的位置。
若儲存棧的長度為StackSize，則棧頂位置top必須小於StackSize。當棧存在一個元素時，top等於0，因此通常把空棧的判斷條件定位top等於-1。

棧的順序儲存結構可描述為：

#define MAXSIZE 50  //定義棧中元素的最大個數
typedef int ElemType;   //ElemType的型別根據實際情況而定，這裡假定為int
typedef struct{
    ElemType data[MAXSIZE];
    int top;    //用於棧頂指標
}SqStack;

若現在有一個棧，StackSize是5，則棧的普通情況、空棧、滿棧的情況分別如下圖所示：

2、順序棧的基本演演算法

（1）初始化

void InitStack(SqStack *S){
    S->top = -1;    //初始化棧頂指標
}

（2）判棧空

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

（3）進棧

進棧操作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）共用棧概念

利用棧底位置相對不變的特徵，可讓兩個順序棧共用一個一維陣列空間，將兩個棧的棧底分別設定在共用空間的兩端，兩個棧頂向共用空間的中間延伸，

如下圖所示：

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

（2）共用棧的空間結構

程式碼如下：

/*兩棧共用空間結構*/
#define MAXSIZE 50  //定義棧中元素的最大個數
typedef int ElemType;   //ElemType的型別根據實際情況而定，這裡假定為int
/*兩棧共用空間結構*/
typedef struct{
	ElemType data[MAXSIZE];
	int top0;	//棧0棧頂指標
	int top1;	//棧1棧頂指標
}SqDoubleStack;

（3）共用棧進棧

對於兩棧共用空間的push方法，我們除了要插入元素值引數外，還需要有一個判斷是棧0還是棧1的棧號引數stackNumber。

共用棧進棧的程式碼如下：

/*插入元素e為新的棧頂元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){
    if(S->top0+1 == S->top1){   //棧滿
        return ERROR;
    }
    if(stackNumber == 0){   //棧0有元素進棧
        S->data[++S->top0] = e; //若棧0則先top0+1後給陣列元素賦值
    }else if(satckNumber == 1){ //棧1有元素進棧
        S->data[--S->top1] = e; //若棧1則先top1-1後給陣列元素賦值
    }
    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已經是空棧，溢位
        }
        *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;
}

三、棧的鏈式儲存結構

1、鏈棧

採用鏈式儲存的棧稱為鏈棧，鏈棧的優點是便於多個棧共用儲存空間和提高其效率，且不存在棧滿上溢的情況。通常採用單連結串列實現，並規定所有操作都是在單連結串列的表頭進行的。這裡規定鏈棧沒有頭節點，Lhead指向棧頂元素，如下圖所示。

對於空棧來說，連結串列原定義是頭指標指向空，那麼鏈棧的空其實就是top=NULL的時候。

鏈棧的結構程式碼如下：

/*棧的鏈式儲存結構*/
/*構造節點*/
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*構造鏈棧*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

2、鏈棧的基本演演算法

（1）鏈棧的進棧

對於鏈棧的進棧push操作，假設元素值為e的新節點是s，top為棧頂指標，示意圖如下：

程式碼如下：

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

（2）鏈棧的出棧

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

3、效能分析

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

四、棧的應用——遞迴

1、遞迴的定義

遞迴是一種重要的程式設計方法。簡單地說,若在一個函數、過程或資料結構的定義中又應用了它自身,則這個函數、過程或資料結構稱為是遞迴定義的,簡稱遞迴。
它通常把一個大型的複雜問題層層轉化為一個與原問題相似的規模較小的問題來求解,遞迴策略只需少量的程式碼就可以描述岀解題過程所需要的多次重複計算,大大減少了程式的程式碼量但在通常情況下,它的效率並不是太高。

2、斐波那契數列

在解釋斐波那契數列之前，我們想看經典的兔子繁殖的問題：

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

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

我們拿新出生的一對小兔子分析一下:第一個月小兔子沒有繁殖能力,所以還是一對;兩個月後,生下一對小兔子數共有兩對;三個月以後,老兔子又生下一對,因為小兔子還沒有繁殖能力,所以一共是三對…依次類推得出這樣一個圖：

從這個圖可以看出，斐波那契數列數列有一個明顯的特點，即：前面兩項之和，構成了後一項。
如果用數學函數定義斐波那契數列，那就是：

而這個，就是遞迴的一個典型例子，用程式實現時如下：

/*斐波那契數列的實現*/
int Fib(int n){
    if(n == 0){
        return 0;   //邊界條件
    }else if(n == 1){
        return 1;	//邊界條件
    }else{
        return Fib(n-1) + Fib(n-2); //遞迴表示式
    }
}

必須注意遞迴模型不能是迴圈定義的,其必須滿足下面的兩個條件

遞迴表示式(遞迴體)
邊界條件(遞迴出口)

遞迴的精髓在於能否將原始問題轉換為屬性相同但規模較小的問題
在遞迴呼叫的過程中,系統為每一層的返回點、區域性變數、傳入實參等開闢了遞迴工作棧來進行資料儲存,遞迴次數過多容易造成棧溢位等。而其效率不高的原因是遞迴呼叫過程中包含很多重複的計算。下面以n=5為例,列出遞迴呼叫執行過程,如圖所示：

如圖可知，程式每往下遞迴一次，就會把運算結果放到棧中儲存，直到程式執行到臨界條件，然後便會把儲存在棧中的值按照先進後出的順序一個個返回，最終得出結果。

五、棧的應用——四則運算表示式求值

1、字尾表示式計算結果

表示式求值是程式設計語言編譯中一個最基本的問題,它的實現是棧應用的一個典型範例。中綴表示式不僅依賴運運算元的優先順序,而且還要處理括號。字尾表示式的運運算元在運算元后面，在字尾表示式中已考慮了運運算元的優先順序,沒有括號,只有運算元和運運算元。例如中綴表示式 A + B ∗ ( C − D ) − E / F A+B*(C-D)-E/F A+B∗(C−D)−E/F所對應的字尾表示式為 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−。

字尾表示式計算規則：從左到右遍歷表示式的每個數位和符號，遇到是數位就進棧，遇到是符號，就將處於棧頂兩個數位出棧，進項運算，運算結果進棧，一直到最終獲得結果。

字尾表示式 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−求值的過程需要12步，如下表所示：

讀者也可將字尾表示式與原運算式對應的表示式樹(用來表示算術表示式的二元樹)的後序遍歷進行比較,可以發現它們有異曲同工之妙。
如下圖則是 A + B ∗ ( C − D ) − E / F A+B*(C-D)-E/F A+B∗(C−D)−E/F對應的表示式，它的後序遍歷即是表示式 A B C D − ∗ + E F / − ABCD-*+EF/- ABCD−∗+EF/−。

2、中綴表示式轉字尾表示式

我們把平時所用的標準四則運算表示式,即 a + b − a ∗ ( ( c + d ) / e − f ) + g a+b-a*((c+d)/e-f)+g a+b−a∗((c+d)/e−f)+g叫做中綴
表示式。因為所有的運運算元號都在兩數位的中間,現在我們的問題就是中綴到字尾的轉化。

規則:從左到右遍歷中綴表示式的每個數位和符號,若是數位就輸出,即成為後
綴表示式的一部分;若是符號,則判斷其與棧頂符號的優先順序,是右括號或優先順序低於棧頂符號(乘除優先加減)則棧頂元素依次出棧並輸出,並將當前符號進棧,一直到最終輸出字尾表示式為止。

例：將中綴表示式 a + b − a ∗ ( ( c + d ) / e − f ) + g a+b-a*((c+d)/e-f)+g a+b−a∗((c+d)/e−f)+g轉化為相應的字尾表示式。

分析：需要根據操作符

的優先順序來進行棧的變化,我們用icp來表示當前掃描到的運運算元ch的優先順序,該運運算元進棧後的優先順序為isp,則運運算元的優先順序如下表所示[isp是棧內優先( in stack priority)數,icp是棧外優先( in coming priority)數]。

我們在表示式後面加上符號‘#’,表示表示式結束。

具體轉換過程如下：

即相應的字尾表示式為 a b + a c d + e / f − ∗ − g + ab+acd+e/f-*-g+ ab+acd+e/f−∗−g+。

佇列

一、佇列的基本概念

1、佇列的定義

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

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

2、佇列的常見基本操作

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

二、佇列的順序儲存結構

佇列的順序實現是指分配一塊連續的儲存單元存放佇列中的元素，並附設兩個指標：隊頭指標 front指向隊頭元素，隊尾指標 rear 指向隊尾元素的下一個位置。

1、順序佇列

佇列的順序儲存型別可描述為:

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

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

如圖d，佇列出現“上溢位”，然而卻又不是真正的溢位，所以是一種“假溢位”。

2、迴圈佇列

解決假溢位的方法就是後面滿了，就再從頭開始，也就是頭尾相接的迴圈。我們把佇列的這種頭尾相接的順序儲存結構稱為迴圈佇列。
當隊首指標Q->front = MAXSIZE-1後，再前進一個位置就自動到0，這可以利用除法取餘運算（%）來實現。

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

出隊入隊時，指標都按照順時針方向前進1，如下圖所示：

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

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

（2）型別中增設表示元素個數的資料成員。這樣，隊空的條件為 Q->size == O ；隊滿的條件為 Q->size == Maxsize 。這兩種情況都有 Q->front == Q->rear
（3）型別中增設tag 資料成員，以區分是隊滿還是隊空。tag 等於0時，若因刪除導致 Q->front == Q->rear ，則為隊空；tag 等於 1 時，若因插入導致 Q ->front == Q->rear ，則為隊滿。

我們重點討論第一種方法

3、迴圈佇列常見基本演演算法

（1）迴圈佇列的順序儲存結構

typedef int ElemType;   //ElemType的型別根據實際情況而定，這裡假定為int
#define MAXSIZE 50  //定義元素的最大個數
/*迴圈佇列的順序儲存結構*/
typedef struct{
    ElemType data[MAXSIZE];
    int front;  //頭指標
    int rear;   //尾指標,若佇列不空，指向佇列尾元素的下一個位置
}SqQueue;

（2）迴圈佇列的初始化

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

（3）迴圈佇列判隊空

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

（4）求迴圈佇列長度

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

（5）迴圈佇列入隊

/*若佇列未滿，則插入元素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指標向後移一位置，若到最後則轉到陣列頭部
    return OK;
}

（6）迴圈佇列出隊

/*若佇列不空，則刪除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指標向後移一位置，若到最後則轉到陣列頭部
}

三、佇列的鏈式儲存結構

1、鏈佇列

佇列的鏈式儲存結構表示為鏈佇列，它實際上是一個同時帶有隊頭指標和隊尾指標的單連結串列，只不過它只能尾進頭出而已。

空佇列時，front和real都指向頭結點。

2、鏈佇列常見基本演演算法

（1）鏈佇列儲存型別

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

當Q->front == NULL 並且 Q->rear == NULL 時，鏈佇列為空。

（2）鏈佇列初始化

void InitQueue(LinkQueue *Q){
	Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode));	//建立頭結點
	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新結點s賦值給原隊尾結點的後繼
	Q->rear = s;	//把當前的s設定為新的隊尾結點
	return OK;
}

（4）鏈佇列出隊

出隊操作時，就是頭結點的後繼結點出隊，將頭結點的後繼改為它後面的結點，若連結串列除頭結點外只剩一個元素時，則需將rear指向頭結點。

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