C語言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例
更新時(shí)間：2022年03月29日 14:43:51 作者：許同學(xué)。。
棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯壿嬯P(guān)系為?"一對一"?的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解
1.思考-1
為什么棧用數(shù)組來模擬比用鏈表來模擬更優(yōu)一些？
隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會比較低，時(shí)間復(fù)雜度為O(n)。
2.?；静僮鞯膶?shí)現(xiàn)
2.1 初始化棧
void StackInit(stack*ps)
{
assert(ps);
ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4);
ps->_top = 0;
ps->_capacity = 4;
}
2.2 入棧
void StackPush(stack*ps, StackDate x)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
stack*tmp = (StackDate*)realloc(ps, sizeof(StackDate)*(ps->_capacity) * 2);
if (NULL == tmp)
{
printf("realloc failed\n");
exit(-1);
}
ps = tmp;
ps->_capacity *= 2;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
2.3 出棧
void StackPop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
--ps->_top;
}
注意： 出棧并不是真正意義上的刪除數(shù)據(jù)，而是將_top向后挪動了一個(gè)位置。
2.4 獲取棧頂數(shù)據(jù)
StackDate StackTop(stack*ps)
{
assert(ps);
assert(!StackIsEmpty(ps));
return ps->_a[ps->_top - 1];
}
2.5 獲取棧中有效元素個(gè)數(shù)
int StackSize(stack*ps)
{
assert(ps);
return ps->_top;
}
2.6 判斷棧是否為空
bool StackIsEmpty(stack*ps)
{
assert(ps);
return ps->_top == 0;
}
2.7 銷毀棧
void StackDestory(stack*ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}
3.測試
3.1 測試
void test()
{
//插入數(shù)據(jù)
stack st;
StackInit(&st);
StackPush(&st,1);
StackPush(&st,2);
StackPush(&st,3);
StackPush(&st,4);
while (!StackIsEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
//獲取棧頂數(shù)據(jù)
StackPush(&st, 1);
StackPush(&st, 2);
printf("%d ", StackTop(&st));
printf("\n");
//棧中有效數(shù)據(jù)個(gè)數(shù)
printf("%d ", StackSize(&st));
//銷毀棧
StackDestory(&st);
}
3.2 測試結(jié)果
4.思考-2
為什么隊(duì)列用鏈表模擬比數(shù)組模擬更加合適？
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)小。
5.隊(duì)列的基本操作實(shí)現(xiàn)
5.1 初始化隊(duì)列
void QueueInit(Queue*pq)
{
assert(pq);
pq->_head = pq->_tail = NULL;
}5.2 隊(duì)尾入隊(duì)列
void QueuePush(Queue*pq, QueueDate x)
{
assert(pq);
QueueNode*newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (NULL == newnode)
{
printf("malloc failed\n");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (NULL == pq->_tail)
{
pq->_head = pq->_tail = newnode;
}
else
{
pq->_tail->next = newnode;
pq->_tail = newnode;
}
}5.3 隊(duì)頭出隊(duì)列
void QueuePop(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
if (NULL == pq->_head->next)
{
free(pq->_head);
pq->_head = pq->_tail = NULL;
}
else
{
QueueNode*next = pq->_head->next;
free(pq->_head);
pq->_head = next;
}
}代碼分析：
5.4 隊(duì)列中有效元素的個(gè)數(shù)
int QueueSize(Queue*pq)
{
assert(pq);
int count = 0;
QueueNode*cur = pq->_head;
while (cur)
{
++count;
cur = cur->next;
}
return count;
}
5.5 判斷隊(duì)列是否為空
bool QueueIsEmpty(Queue*pq)
{
assert(pq);
return pq->_head == NULL;
}
5.6 獲取隊(duì)頭數(shù)據(jù)
QueueDate QueueFront(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_head->val;
}
5.7 獲取隊(duì)尾的數(shù)據(jù)
QueueDate QueueBack(Queue*pq)
{
assert(pq);
assert(!QueueIsEmpty(pq));
return pq->_tail->val;
}
5.8 銷毀隊(duì)列
void QueueDestory(Queue*pq)
{
assert(pq);
while (pq->_head)
{
if (pq->_head == pq->_tail)
{
free(pq->_head);
pq->_head = pq->_tail = NULL;
}
else
{
QueueNode*next = pq->_head->next;
free(pq->_head);
pq->_head = next;
}
}
}
注意： 和隊(duì)頭出隊(duì)列一樣分析。
6.測試
6.1 測試
void test1()
{
//插入數(shù)據(jù)
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//有效數(shù)據(jù)的個(gè)數(shù)
printf("%d ", QueueSize(&q));
printf("\n");
//獲取隊(duì)頭數(shù)據(jù)
printf("%d",QueueFront(&q));
printf("\n");
//獲取隊(duì)尾數(shù)據(jù)
printf("%d",QueueBack(&q));
printf("\n");
//出隊(duì)
QueuePop(&q);
while (!QueueIsEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
//銷毀
QueueDestory(&q);
printf("\n");
}
6.2 測試結(jié)果
今天數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的相關(guān)知識點(diǎn)就分享到這里了，感謝你的瀏覽，如果對你有幫助的話，可以給個(gè)關(guān)注，順便來個(gè)贊。
到此這篇關(guān)于C語言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例的文章就介紹到這了,更多相關(guān)C語言 棧與隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Cocos2d-x學(xué)習(xí)筆記之開發(fā)環(huán)境搭建
這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之開發(fā)環(huán)境搭建,本文使用Visual Studio作為開發(fā)IDE,是不同于其它教程的,需要的朋友可以參考下2014-09-09
C++?TCP網(wǎng)絡(luò)編程詳細(xì)講解
TCP/IP是一種面向連接的、可靠的、基于字節(jié)流的傳輸層通信協(xié)議，它會保證數(shù)據(jù)不丟包、不亂序。TCP全名是Transmission?Control?Protocol，它是位于網(wǎng)絡(luò)OSI模型中的第四層2022-09-09
三子棋(井字棋)我們的童年或多或少都體驗(yàn)過這個(gè)游戲的樂趣,本子隨手一畫就是一局游戲的開始,下面這篇文章主要給大家介紹了關(guān)于200行C語言代碼實(shí)現(xiàn)簡易三子棋游戲的相關(guān)資料,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了c語言沒有try catch的替代方案，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06
帶頭結(jié)點(diǎn)的鏈表的基本操作(超詳細(xì)）
鏈表是一種動態(tài)分配空間的存儲結(jié)構(gòu)，能更有效地利用存儲空間，通過對單鏈表基本操作的代碼實(shí)現(xiàn)，我深刻領(lǐng)悟到以“指針”指示元素的后繼，在插入或刪除元素時(shí)不需要移動元素2023-07-07
這篇文章主要為大家介紹了C語言教程之?dāng)?shù)組，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
C和MFC巧妙獲取外網(wǎng)IP的兩種實(shí)現(xiàn)方法
這篇文章主要介紹了C和MFC巧妙獲取外網(wǎng)IP的兩種實(shí)現(xiàn)方法,功能非常的實(shí)用,需要的朋友可以參考下2014-07-07
C語言實(shí)現(xiàn)BMP圖像處理(哈夫曼編碼)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)BMP圖像哈夫曼編碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
Qt使用SQLite數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)增刪改查
這篇文章主要為大家詳細(xì)介紹了Qt如何使用SQLite數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)增刪改查功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-06-06
多態(tài)是面向?qū)ο缶幊蹋∣OP）的核心概念之一,它允許對象在相同操作下表現(xiàn)出不同的行為,本文主要為大家介紹了C++中多態(tài)與文件操作的相關(guān)知識,希望對大家有所幫助2024-04-04