C語言編程數據結構棧與隊列的全面講解示例教程
一、棧的表示和實現(xiàn)
1棧的概念和結構
棧：一種特殊的線性表（邏輯上數據是連著放的），其只允許在固定的一端進行插入和刪除操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵循后進先出的原則。
壓棧：棧的插入操作叫作進棧/壓線/入線，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。
（圖片來自比特就業(yè)課）
先入后出就類似與你裝手槍彈夾，你先放入的子彈會在彈夾底部，最后放入的子彈是在彈夾頂部，你開手槍是先打出彈夾頂端的子彈。
我們這里先定義一個棧的類型：
typedef int STDataType;//方便將來如果需要其他類型的數據，可以直接修改int的類型
typedef struct Stack
{
STDataType*a;//棧底指針
int top;//棧頂標號
int capacity;//容量
}ST;
本文介紹以順序表（數組）實現(xiàn)棧，由此，所謂的入棧壓棧也不過是順序表的尾插尾刪，如果讀者想以鏈表實現(xiàn)也是可以的，方法不唯一。
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，及后文出現(xiàn)的realloc、free函數詳情見筆者動態(tài)內存管理文章
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);//終止程序
}
ps->capacity=4;
//這里以開辟4個數據容量大小的棧為例，你也可以寫其他數字
//如果壓棧的時候內存不夠，可以在后面提到的壓棧函數里面進行擴容
ps->top = 0;//剛開始棧里沒有值時，用top=0標記，后續(xù)每放入一個top++
//關于top詳細用法請往下看1.3壓棧部分
}
3壓棧(棧頂插入一個數據)
如上圖，我們現(xiàn)在開辟了一塊空間，a和top都在棧頂，我們往里面入一個數據1
1進入棧之后，1就是棧頂元素了，那如果我想繼續(xù)入棧，就是要在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是在原先開辟的空間上繼續(xù)往后開辟一塊空間，詳細見筆者動態(tài)內存文章
//擴容一般擴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，那我們現(xiàn)在要進行出棧操作,也就是刪除4怎么辦？直接top–即可
到這里肯定會有小伙伴有疑問，憑什么你top–一下就是出棧了，你4都沒刪除??？解釋如下：我們在1.3壓棧部分就說過“top不是表示棧頂元素位置，而是棧頂元素下一個位置”，那現(xiàn)在我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。
二、隊列的表示和實現(xiàn)
1隊列的概念及結構
隊列：只允許在一端插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出的性質
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
（圖片來自比特就業(yè)課）
類似你走人工通道那樣，你排在前面的，你先出去
2隊列的實現(xiàn)
由于隊列的隊頭出，隊尾入，非常類似單鏈表的頭刪和尾插，我們這里介紹以單鏈表實現(xiàn)隊列，如下圖，現(xiàn)有3個節(jié)點的單鏈表：
比如現(xiàn)在，我要隊頭出一個，也就是把單鏈表節(jié)點第一個節(jié)點刪掉（頭刪）
或者隊尾入一個，也就是單鏈表的尾插
代碼如下（示例）：
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode*next;
QDataType data;
}QNode;//這里和單鏈表定義一樣，有需要的可以看一下筆者之前的單鏈表文章
typedef struct Queue//定義一個結構體存儲頭節(jié)點地址和尾節(jié)點地址，方便后面頭刪和尾插
{
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個節(jié)點，你首先得把兩節(jié)點連上，也就是pq->tail->next = newnode;（沒接上之前tail還指向第一個節(jié)點），接上之后tail指針指向第二節(jié)點
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節(jié)點，他們的next是空指針，所以我們以這個條件為判斷。又因為要出隊（隊頭刪除一個數據），因為只有一個節(jié)點，也就是把這個節(jié)點給刪掉，我們用free函數釋放掉head指向的空間。釋放完，那塊空間已經還給內存了，這時你的頭和尾指針就不能指向那塊空間了，我們用空指針賦值。
2.原隊列有多個數據
我們現(xiàn)在要出隊（隊頭刪除一個數據），也就是把1節(jié)點刪掉，我們先創(chuàng)建一個變量next找到2節(jié)點位置，然后free掉1節(jié)點的空間
1節(jié)點空間free掉之后，把next（指向2節(jié)點）賦給head，讓頭指針指向2節(jié)點。
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進行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
{
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進行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
{
QNode*next = cur->next;
free(cur);//free是釋放指向的空間，指針還是在的
cur = next;
}
pq->head = pq->tail = NULL;
}
如上圖，我們創(chuàng)建一個變量cur并用head指針賦值。然后找到第二個節(jié)點，用cur->next標記,標記完我們釋放掉cur（釋放的第一個節(jié)點空間,指針還是在的），釋放完，cur開始遍歷第二個節(jié)點，也就是我們先前用next標記的空間。。。剩下的以此類推。cur!=NULL進行循環(huán),NULL是遍歷完tail之后出現(xiàn)的，當循環(huán)不進行說明已經遍歷完了尾指針指向的節(jié)點，頭和尾節(jié)點已經不需要了，我們用空指針賦值。
總結
本文介紹了棧和隊列的相關原理及各個接口函數，內容較多，知識點量大，希望讀者耐心學習，相信你一定會有所收獲，祝讀者學習愉快~更多關于C語言數據結構棧與隊列的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)高精度加法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
線程是操作系統(tǒng)中的一個概念，線程對象可以關聯(lián)一個線程，用來控制線程以及獲取線程的狀態(tài)，這篇文章主要介紹了C++11中的線程庫的相關知識,需要的朋友可以參考下2022-01-01
C語言標準庫＜math.h＞和＜setjmp.h＞的實現(xiàn)
本文主要介紹了C語言標準庫＜math.h＞和＜setjmp.h＞的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-11-11![深入解析int(*p)[]和int(**p)[]](http://img.jbzj.com/images/xgimg/bcimg3.png)
以下是對int(*p)[]和int(**p)[]的使用進行了詳細的分析介紹，需要的朋友可以參考下2013-07-07
這篇文章主要介紹了C++ 實現(xiàn)多數的最大公約數的實例的相關資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了關于C語言位運算的簡單示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-08-08
在上一章中我們正式開啟了對數據結構中樹的講解，介紹了樹的基礎。本章我們將學習二叉樹的概念，介紹滿二叉樹和完全二叉樹的定義，并對二叉樹的基本性質進行一個簡單的介紹。本章附帶課后練習2022-02-02
這篇文章主要介紹了C++ vector擴容解析noexcept應用場景,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09
本文主要介紹了C++封裝成DLL并調用的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
今天小編就為大家分享一篇關于樹存儲結構的幾種表示方法，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03