C語言編程數據結構棧與隊列的全面講解示例教程
一、棧的表示和實現
1棧的概念和結構
棧：一種特殊的線性表（邏輯上數據是連著放的），其隻允許在固定的一端進行插入和刪除操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵循後進先出的原則。
壓棧：棧的插入操作叫作進棧/壓線/入線，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。
（圖片來自比特就業課）
先入後出就類似與你裝手槍彈夾，你先放入的子彈會在彈夾底部，最後放入的子彈是在彈夾頂部，你開手槍是先打出彈夾頂端的子彈。
我們這裡先定義一個棧的類型：
typedef int STDataType;//方便將來如果需要其他類型的數據，可以直接修改int的類型
typedef struct Stack
{
STDataType*a;//棧底指針
int top;//棧頂標號
int capacity;//容量
}ST;
本文介紹以順序表（數組）實現棧，由此，所謂的入棧壓棧也不過是順序表的尾插尾刪，如果讀者想以鏈表實現也是可以的，方法不唯一。
2棧的初始化
關於棧的初始化：我們這裡以容量大小4的棧為例，剛開始因為棧裡沒有數據我們用top=0標記，需要註意的是：傳過來的棧底指針不能為空，開辟空間時萬一沒有開辟成功返回一個空指針也要丟棄。
#include<assert.h>
#include<stdlib.h>//malloc函數頭文件
void StackInit(ST*ps)//棧初始化
{
assert(ps);//防止傳過來的指針是空指針
ps->a = (STDataType)malloc(sizeof(STDataType) * 4);//malloc開辟一塊空間出來，由STDataType類型進行管理
//malloc，及後文出現的realloc、free函數詳情見筆者動態內存管理文章
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);//終止程序
}
ps->capacity=4;
//這裡以開辟4個數據容量大小的棧為例，你也可以寫其他數字
//如果壓棧的時候內存不夠，可以在後面提到的壓棧函數裡面進行擴容
ps->top = 0;//剛開始棧裡沒有值時，用top=0標記，後續每放入一個top++
//關於top詳細用法請往下看1.3壓棧部分
}
3壓棧(棧頂插入一個數據)
如上圖，我們現在開辟瞭一塊空間，a和top都在棧頂，我們往裡面入一個數據1
1進入棧之後，1就是棧頂元素瞭，那如果我想繼續入棧，就是要在top的位置放入一個數據讓新放入的數據成為新的棧頂元素，然後以此類推，每次入一個元素，top++，top不是表示棧頂元素位置，而是棧頂元素下一個位置。
#include<assert.h>//assert函數頭文件
#include<stdlib.h>//realloc函數頭文件
void StackPush(ST*ps, STDataType x)//棧頂插入數據（入棧）
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType*tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
//realloc是在原先開辟的空間上繼續往後開辟一塊空間，詳細見筆者動態內存文章
//擴容一般擴2倍
if (tmp == NULL)//擴容失敗（比如內存已經不夠你再開辟空間瞭）會返回空指針
{
printf("realloc fail\n");
exit(-1);//終止程序
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;//a是一個指針，a[x]==*(a+x)
ps->top++;
}
4出棧(棧頂刪除一個數據)
出棧非常簡單，我們以下圖為例：
圖中我們棧裡已經存放瞭4個數據1、2、3、4，那我們現在要進行出棧操作,也就是刪除4怎麼辦？直接top–即可
到這裡肯定會有小夥伴有疑問，憑什麼你top–一下就是出棧瞭，你4都沒刪除啊？解釋如下：我們在1.3壓棧部分就說過“top不是表示棧頂元素位置，而是棧頂元素下一個位置”，那現在我top在4這裡，說明3才是真正的棧頂元素，4已經不在棧的管轄范圍內瞭。
void StackPop(ST*ps)//棧頂刪除數據（出棧）
{
assert(ps);
assert(ps->top > 0);//棧空瞭，調用Pop，直接中止程序報錯
ps->top--;
}
關於ps->top > 0，是這樣的：假設你原先棧裡沒有有一個元素
你top–就是往下訪問未知的領域瞭，這是非常嚴重的問題，所以我們這裡用assert斷言一下，防止棧裡什麼元素也沒有讓top標記到瞭未知領域。（再次強調一下：top不是表示棧頂元素位置，而是棧頂元素下一個位置）
5取棧頂元素
STDataType StackTop(ST*ps)//取棧頂數據
{
assert(ps);
assert(ps->top > 0);//棧空瞭，調StackTop，直接中止程序報錯
return ps->a[ps->top - 1];//top是棧頂元素下一個位置,top-1是棧頂元素
//a[m]==*(a+m)
}
這裡的思路和1.4幾乎一樣，也要防止棧裡什麼也沒有的情況，然後正常返回棧頂元素即可，因為top是棧頂元素下一個位置,top-1是棧頂元素，然後你正常寫就行，這裡的
a[ps->top – 1]你也可以寫成*(a+(ps->top – 1)),這個寫法讀者可參加筆者以前的指針文章，這裡不再贅述。
6取棧頂元素
int StackSize(ST*ps)//棧的數據個數
{
assert(ps);
return ps->top;
}
這個就更簡單瞭，直接返回top的值就可以瞭，為什麼呢，我們看兩張圖即可
圖一：
圖二：
圖一是壓棧前，沒有一個元素，top=0，圖二是壓棧後，top++，top=1。同樣的以此類推，我們每加入1個元素，top++，每減去一個元素，top–。元素個數永遠=top值，所以我們這裡的函數直接返回top值即可。
7判斷棧是否為空
int StackEmpty(ST*ps)//判斷棧是不是空
{
assert(ps);
return ps->top == 0;
}
由1.6知，我們的top值是和棧裡元素個數一樣的，所以我們直接return ps->top == 0；即可，如果ps->top == 0這個表達式成立表達式值為1，反之為0。
二、隊列的表示和實現
1隊列的概念及結構
隊列：隻允許在一端插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出的性質
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
（圖片來自比特就業課）
類似你走人工通道那樣，你排在前面的，你先出去
2隊列的實現
由於隊列的隊頭出，隊尾入，非常類似單鏈表的頭刪和尾插，我們這裡介紹以單鏈表實現隊列，如下圖，現有3個節點的單鏈表：
比如現在，我要隊頭出一個，也就是把單鏈表節點第一個節點刪掉（頭刪）
或者隊尾入一個，也就是單鏈表的尾插
代碼如下（示例）：
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode*next;
QDataType data;
}QNode;//這裡和單鏈表定義一樣，有需要的可以看一下筆者之前的單鏈表文章
typedef struct Queue//定義一個結構體存儲頭節點地址和尾節點地址，方便後面頭刪和尾插
{
QNode*head;
QNode*tail;
}Queue;
3隊列初始化
代碼如下（示例）：
void QueueInit(Queue*pq)隊列初始化,pq是一個結構體指針
{
assert(pq);//判斷pq是否是空指針
pq->head = NULL;
pq->tail = NULL;
}
4入隊（隊尾插入一個數據）
void QueuePush(Queue*pq, QDataType x)//入隊（隊尾入）
{
assert(pq);
QNode*newnode = (QNode*)malloc(sizeof(QNode));//開辟出一塊空間給newnode
if (newnode == NULL)//有可能剩餘內存不夠開辟空間，malloc開辟失敗會返回空指針
{
printf("開辟空間失敗\n");
exit(-1);//退出程序
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)//原先隊列裡沒有任何數據，頭和尾指針都指向NULL
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
關於下面if這段代碼解釋如下：
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
原先隊列裡沒有任何數據，頭和尾指針都指向NULL
當你往隊列裡面放瞭一個數據，頭和尾指針是指向新的數據（頭和尾指針仍指向一個）
如果你想再加1個節點，你首先得把兩節點連上，也就是pq->tail->next = newnode;（沒接上之前tail還指向第一個節點），接上之後tail指針指向第二節點
5出隊（隊頭刪除一個數據）
void QueuePop(Queue*pq)//出隊（隊頭出）
{
assert(pq);
assert(pq->head);//要出隊，隊裡也要有數據可以出
//原隊列隻有1個數據
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//原隊列有多個數據
else
{
QNode*next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
關於出隊，這裡要分2種情況討論：
1.原隊列隻有1個數據
隻有一個數據的時候，頭和尾指針都指向1節點，他們的next是空指針，所以我們以這個條件為判斷。又因為要出隊（隊頭刪除一個數據），因為隻有一個節點，也就是把這個節點給刪掉，我們用free函數釋放掉head指向的空間。釋放完，那塊空間已經還給內存瞭，這時你的頭和尾指針就不能指向那塊空間瞭，我們用空指針賦值。
2.原隊列有多個數據
我們現在要出隊（隊頭刪除一個數據），也就是把1節點刪掉，我們先創建一個變量next找到2節點位置，然後free掉1節點的空間
1節點空間free掉之後，把next（指向2節點）賦給head，讓頭指針指向2節點。
6取隊頭數據
QDataType QueueFront(Queue*pq)//取隊頭數據
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
7取隊尾數據
QDataType QueueBack(Queue*pq)//取隊尾數據
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
8計算隊列中數據個數
int QueueSize(Queue*pq)//隊內數據個數
{
assert(pq);
int size = 0;
QNode*cur = pq->head;
while (cur)//cur!=NULL進行循環,NULL是遍歷完tail之後出現的
{
size++;
cur = cur->next;
}
return size;
}
9判斷隊列是否為空
bool QueueEmpty(Queue*pq)
{
assert(pq);
return pq->head == NULL;
}
這一般是作為一個輔助函數來使用，bool 就是用來判斷真假的數據類型，如果表達式：pq->head == NULL成立返回true,反之返回false
10銷毀隊列
void QueueDestory(Queue*pq)//隊列銷毀
{
assert(pq);
QNode*cur = pq->head;
while (cur)//cur!=NULL進行循環,NULL是遍歷完tail之後出現的
{
QNode*next = cur->next;
free(cur);//free是釋放指向的空間，指針還是在的
cur = next;
}
pq->head = pq->tail = NULL;
}
如上圖，我們創建一個變量cur並用head指針賦值。然後找到第二個節點，用cur->next標記,標記完我們釋放掉cur（釋放的第一個節點空間,指針還是在的），釋放完，cur開始遍歷第二個節點，也就是我們先前用next標記的空間。。。剩下的以此類推。cur!=NULL進行循環,NULL是遍歷完tail之後出現的，當循環不進行說明已經遍歷完瞭尾指針指向的節點，頭和尾節點已經不需要瞭，我們用空指針賦值。
總結
本文介紹瞭棧和隊列的相關原理及各個接口函數，內容較多，知識點量大，希望讀者耐心學習，相信你一定會有所收獲，祝讀者學習愉快~更多關於C語言數據結構棧與隊列的資料請關註WalkonNet其它相關文章！