c語言數據結構之棧和隊列詳解(Stack&Queue)
簡介
【知識框架】
棧
一、棧的基本概念
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;
}
四、雙端隊列
1、定義
雙端隊列是指允許兩端都可以進行入隊和出隊操作的隊列，如下圖所示。其元素的邏輯結構仍是線性結構。將隊列的兩端分別稱為前端和後端，兩端都可以入隊和出隊。
在雙端隊列進隊時，前端進的元素排列在隊列中後端進的元素的前面，後端進的元素排列在隊列中前端進的元素的後面。在雙端隊列出隊時，無論是前端還是後端出隊，先出的元素排列在後出的元素的前面。
2、特殊的雙端隊列
在實際使用中，根據使用場景的不同，存在某些特殊的雙端隊列。
輸出受限的雙端隊列：允許在一端進行插入和刪除， 但在另一端隻允許插入的雙端隊列稱為輸出受限的雙端隊列，如下圖所示。
輸入受限的雙端隊列：允許在一端進行插入和刪除，但在另一端隻允許刪除的雙端隊列稱為輸入受限的雙端隊列，如下圖所示。若限定雙端隊列從某個端點插入的元素隻能從該端點刪除，則該雙端隊列就蛻變為兩個棧底相鄰接的棧。
到此這篇關於c語言數據結構之棧和隊列詳解(Stack & Queue)的文章就介紹到這瞭,更多相關c語言據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！