C語言分別實現(xiàn)棧和隊列詳解流程
什么是棧
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素的操作。進(jìn)行數(shù)據(jù)插入和刪除的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守先進(jìn)后出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
棧的結(jié)構(gòu)圖示
棧的實現(xiàn)
棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的代價比較小。
創(chuàng)建棧的結(jié)構(gòu)體
我們用棧來存儲數(shù)據(jù)，首先需要實現(xiàn)一個動態(tài)增長的棧。所以我們先創(chuàng)建一個棧的結(jié)構(gòu)體。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //棧頂
int capacity; //容量
}Stack;
初始化棧
初始化棧的方式有很多種，我們可以根據(jù)不同的需求來選擇。這里寫一種常規(guī)的。
void StackInit(Stack* ps)
{
assert(ps);//檢測傳過來的ps是否為空
ps->a = NULL;//把a(bǔ)標(biāo)識的這塊空間先置為空
ps->top = ps->capacity = 0;
}
入棧
一開始top為0標(biāo)識棧頂?shù)奈恢?，所以我們要先將?shù)據(jù)放入棧頂，在讓top向后走一位。
void StackPush(Stack* ps, STDataType x)
{
assert(ps);//檢測ps是否為空
//如果空間滿了，我們需要擴(kuò)容
if (ps->capacity == ps->top)//判斷空間是否滿了的條件
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//指定新空間的大小
ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));//進(jìn)行擴(kuò)容
if (ps->a == NULL)//擴(kuò)容失敗
{
printf("realloc fail\n");
exit(-1);//終止程序
}
ps->capacity = newCapacity;//讓其標(biāo)識新的空間的大小
}
ps->a[ps->top] = x;//將數(shù)據(jù)放入棧
ps->top++;//top向后走一步
}
出棧
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)//避免棧里面數(shù)據(jù)已經(jīng)刪除完了，top依舊向下減為負(fù)數(shù)
{
--ps->top;
}
}
獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//保證下標(biāo)為正
return ps->a[ps->top - 1];//返回棧頂元素
}
獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
檢測棧是否為空
檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空則返回0.
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//如果條件成立就返回真，否則就為假（不為空）
}
棧的銷毀
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);//釋放開辟的這一塊空間
ps->a = NULL;
ps->top = ps->capacity = 0;
}
什么是隊列？
隊列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進(jìn)先出FIFO（First In First Out）入隊列：進(jìn)行插入操作的一端稱為隊尾 出隊列：進(jìn)行刪除操作的一端稱為對頭。
隊列的實現(xiàn)
隊列也可以用數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。
創(chuàng)建隊列結(jié)構(gòu)體
我們使用鏈表來實現(xiàn)隊列，我們需要創(chuàng)建一個存儲隊列信息的結(jié)構(gòu)體。
typedef int QDataType;
//鏈?zhǔn)浇Y(jié)構(gòu)：表示隊列
typedef struct QueueNode
{
QDataType data; //存儲數(shù)據(jù)
struct QueueNode* next; //指針域
}QNode;
//隊列的結(jié)構(gòu)
typedef struct Queue
{
QNode* head;//標(biāo)識隊頭的位置
QNode* tail;//標(biāo)識隊尾的位置
}Queue;
初始化隊列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;//將兩個指針置為空
}
隊尾入隊列
讓一個數(shù)據(jù)進(jìn)入隊列，我們只需要用鏈表結(jié)構(gòu)來實現(xiàn)隊列，在隊尾進(jìn)行尾插數(shù)據(jù)就可以了。
如果隊列為空，需要單獨處理一下。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));//申請一個新的結(jié)點
assert(newnode);//檢測結(jié)點是否申請成功
newnode->data = x;//
newnode->next = NULL;
if (pq->tail == NULL)//如果隊列為空的情況
{
assert(pq->head==NULL);
pq->tail = pq->head = newnode;
}
else//隊列不為空的情況
{
pq->tail->next = newnode;//尾插一個新結(jié)點
pq->tail = newnode;//更新尾的位置
}
}隊頭出隊列
當(dāng)隊列為空，沒有存儲數(shù)據(jù)時，我們就不能夠出數(shù)據(jù)。如果隊列中只有一個結(jié)點，那么我們需要對其單獨處理，否則就會出現(xiàn)錯誤。
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);//保證隊列中有數(shù)據(jù)在往下走
if (pq->head->next == NULL)//如果隊列里面只有一個數(shù)據(jù)的情況
{
free(pq->head);//釋放隊頭數(shù)據(jù)
pq->head = pq->tail = NULL;//將隊列的頭指針和尾指針均置為空
}
else
{
QNode* next = pq->head->next;//讓next指向隊頭結(jié)點的下一個結(jié)點
free(pq->head);//釋放隊頭結(jié)點
pq->head = next;//讓head指向next結(jié)點
}
}
獲取隊列頭部元素
檢測隊列是否為空，如果不為空則直接返回隊列頭指針指向的元素。
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);//檢測隊列是否為空
return pq->head->data;//返回隊列頭部元素
}
獲取隊列尾部元素
檢測隊列是否為空，如果不為空則直接返回隊列尾指針指向的元素。
//獲取隊列隊尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);//檢測隊列是否為空
return pq->tail->data;//返回隊列尾部元素
}
獲取隊列中元素個數(shù)
可以對隊列進(jìn)行遍歷，統(tǒng)計元素個數(shù)，如果隊列比較長那么這個方法效率就比較低。如果想要效率比較高，那么我們可以在定義隊列結(jié)構(gòu)體的時候加上一個size變量，每往隊列里面入一個數(shù)據(jù)就統(tǒng)計一下，那么我們需要隊列中元素個數(shù)的時候就可以直接返回。
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;//讓cur指向隊頭的元素
size_t size = 0;//定義一個無符號的size變量用來計數(shù)
while (cur)//cur不為空則進(jìn)入循環(huán)繼續(xù)執(zhí)行
{
size++;//size=size+1
cur = cur->next;//繼續(xù)向后遍歷
}
return size;//返回有效元素個數(shù)
}
檢測隊列是否為空
檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->head == NULL) && (pq->tail == NULL);
}
銷毀隊列
在使用完隊列之后，我們應(yīng)該對其進(jìn)行銷毀，防止造成內(nèi)存泄漏。
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;//定義一個next指向cur的下一個結(jié)點
free(cur);//釋放cur
cur = next;
}
pq->head = pq->tail = NULL;//將頭尾指針均置為空
}
到此這篇關(guān)于C語言分別實現(xiàn)棧和隊列詳解流程的文章就介紹到這了,更多相關(guān)C語言棧和隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++11中，線程我們可以理解為對應(yīng)一個thread對象，任務(wù)可以理解為要執(zhí)行的函數(shù)，通常是耗時的函數(shù)。線程過多或者頻繁創(chuàng)建和銷毀線程會帶來調(diào)度開銷，進(jìn)而影響緩存局部性和整體性能2021-12-12
這篇文章主要為大家介紹了初識C++?Vector模板與實例化原理，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇文章主要介紹了C++ 處理中文符號實例詳解的相關(guān)資料,需要的朋友可以參考下2017-01-01
這篇文章主要介紹了C++實現(xiàn)LeetCode(75.顏色排序),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++中std::construct()與std::destroy()的使用
std::construct()和std::destroy()是C++ STL中的函數(shù)模板,用于在已分配的存儲區(qū)域中構(gòu)造或銷毀對象,本文主要介紹了C++中std::construct()與std::destroy()的使用,感興趣的可以了解一下2024-02-02
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)詞法分析器，一個簡單的詞法分析程序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了C++發(fā)送HTTP請求的實現(xiàn)代碼,需要的朋友可以參考下2014-06-06
C語言實現(xiàn)班級學(xué)生管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)班級學(xué)生管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
在C語言中,rand()函數(shù)可以用來產(chǎn)生隨機(jī)數(shù)，但是這不是真真意義上的隨機(jī)數(shù)，是一個偽隨機(jī)數(shù)，這篇文章主要介紹了使用c語言生成隨機(jī)數(shù)的示例,需要的朋友可以參考下2014-03-03
C++函數(shù)指針+對象指針+this指針+指向類靜態(tài)和非靜態(tài)成員的指針
這篇文章主要介紹了C++函數(shù)指針+對象指針+this指針+指向類靜態(tài)和非靜態(tài)成員的指針，函數(shù)指針定義和賦值的語法指其中數(shù)據(jù)類型代表指向函數(shù)的返回類型，形參表為指向函數(shù)的形參表，更多相關(guān)資料需要的朋友可以參考一下下面文章內(nèi)容2022-03-03