C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用
棧和隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu),只規(guī)定了性質(zhì),并沒有規(guī)定實(shí)現(xiàn)方式。
本文以順序結(jié)構(gòu)實(shí)現(xiàn)棧,鏈表方式實(shí)現(xiàn)隊(duì)列。
一、棧的概念
棧:是一種特殊的線性表,其只允許在棧頂進(jìn)行插入和刪除元素操作。
棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO(Last In First Out)的原則。
壓棧:棧的插入操作叫做進(jìn)棧\壓棧\入棧,入數(shù)據(jù)在棧頂。
出棧:棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
二、Stack.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct stack { STDataType* arr; int top;//數(shù)組元素個(gè)數(shù)(top-1為最后一個(gè)元素的下標(biāo))就是順序表的size int capacity;//總?cè)萘? }ST; void StackInit(ST* ps);//初始化 void StackDestroy(ST* ps);//銷毀 void StackPush(ST* ps, STDataType x);//壓棧 void StackPop(ST* ps);//出棧 bool StackEmpty(ST* ps);//判斷棧是不是為空 STDataType StackTop(ST* ps);//訪問棧頂元素 int StackSize(ST* ps);//數(shù)組元素個(gè)數(shù)
以順序結(jié)構(gòu)實(shí)現(xiàn)棧,本質(zhì)上仍是一個(gè)順序表,只是這個(gè)順序表加上了棧先進(jìn)后出的規(guī)則。
數(shù)組的頭是棧底,數(shù)組尾是棧頂。棧主要的壓棧、出棧、訪問棧頂?shù)冉涌诜浅F鹾享樞虮淼奈膊濉⑽矂h、隨機(jī)訪問的特點(diǎn)。
三、Stack.c
1、棧的初始化和銷毀
void StackInit(ST* ps)//初始化 { assert(ps); ps->arr = NULL; ps->top = ps->capacity = 0; } void StackDestroy(ST* ps)//銷毀 { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; }
和順序表的初始化、銷毀方式一樣
2、棧的進(jìn)棧、出棧
void StackPush(ST* ps, STDataType x)//進(jìn)棧 { assert(ps); //判斷擴(kuò)容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail:\n"); exit(-1); } ps->arr = tmp; ps->capacity = newCapacity; } ps->arr[ps->top] = x; ps->top++; } void StackPop(ST* ps)//出棧 { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
進(jìn)棧需要判斷棧的空間,空間不夠則需要擴(kuò)容
出棧時(shí),先判空,再將top--即可
3、棧的判空、訪問棧頂元素、棧內(nèi)元素個(gè)數(shù)
bool StackEmpty(ST* ps)//判斷棧是不是為空 { assert(ps); return ps->top == 0; } STDataType StackTop(ST* ps)//訪問棧頂元素 { assert(ps); assert(!StackEmpty(ps)); return ps->arr[ps->top - 1]; } int StackSize(ST* ps)//數(shù)組元素個(gè)數(shù) { assert(ps); return ps->top; }
注意訪問棧頂元素這個(gè)接口,要先判斷棧是不是空。
四、隊(duì)列的概念
隊(duì)列:一端進(jìn)行插入數(shù)據(jù)操作,另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表,隊(duì)列具有先進(jìn)先出FIFO(First In First Out)的特點(diǎn)。
入隊(duì)列:進(jìn)行插入操作的一端稱為隊(duì)尾
出隊(duì)列:進(jìn)行刪除操作的一端稱為隊(duì)頭
隊(duì)列參照現(xiàn)實(shí)生活中的排隊(duì)
五、Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size;//加個(gè)size,方便統(tǒng)計(jì)長度 }Queue; void QueueInit(Queue* pq);//初始化 void QueueDestroy(Queue* pq);//銷毀 void QueuePush(Queue* pq,QDataType x);//入隊(duì)(尾插) bool QueueEmpty(Queue* pq);//判斷隊(duì)列是否為空 void QueuePop(Queue* pq);//出隊(duì)(頭刪) int QueueSize(Queue* pq);//統(tǒng)計(jì)隊(duì)列長度 QDataType QueueFront(Queue* pq);//訪問隊(duì)頭數(shù)據(jù) QDataType QueueBack(Queue* pq);//訪問隊(duì)尾數(shù)據(jù)
因?yàn)轫樞蚪Y(jié)構(gòu)不適合頭刪,這里使用單鏈表來實(shí)現(xiàn)隊(duì)列。
結(jié)構(gòu)體QNode用于模擬單鏈表,結(jié)構(gòu)體Queue中存放了單鏈表的頭、尾指針、鏈表節(jié)點(diǎn)個(gè)數(shù)。使用Queue來操縱單鏈表。
單鏈表的頭head是隊(duì)頭(頭刪出數(shù)據(jù)),tail是隊(duì)尾(尾插錄數(shù)據(jù))
六、Queue.c
1、隊(duì)列的初始化和銷毀
void QueueInit(Queue* pq)//初始化 { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq)//銷毀 { assert(pq); QNode* cur = pq->head; //逐個(gè)銷毀釋放空間 while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; }
和單鏈表的銷毀方式一樣,注意銷毀時(shí)需要逐個(gè)節(jié)點(diǎn)銷毀。
2、隊(duì)列的入隊(duì)、出隊(duì)
void QueuePush(Queue* pq, QDataType x)//入隊(duì),尾插 { assert(pq); //創(chuàng)建一個(gè)新節(jié)點(diǎn) QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail:\n"); exit(-1); } newnode->data = x; newnode->next = NULL; //隊(duì)列為空時(shí)的尾插和不為空的尾插 if (QueueEmpty(pq)) pq->head=pq->tail = newnode; else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Queue* pq)//出隊(duì)(頭刪) { assert(pq); assert(!QueueEmpty(pq)); QNode* next = pq->head->next; free(pq->head); pq->head = next; pq->size--; }
入隊(duì):尾插一個(gè)節(jié)點(diǎn)
出隊(duì):頭刪一個(gè)節(jié)點(diǎn)
3、隊(duì)列的判空
bool QueueEmpty(Queue* pq)//判斷隊(duì)列是否為空 { assert(pq); return pq->head == NULL; }
4、訪問隊(duì)頭、隊(duì)尾數(shù)據(jù)、統(tǒng)計(jì)隊(duì)列長度
int QueueSize(Queue* pq)//統(tǒng)計(jì)隊(duì)列長度 { assert(pq); return pq->size; } QDataType QueueFront(Queue* pq)//訪問隊(duì)頭數(shù)據(jù) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq)//訪問隊(duì)尾數(shù)據(jù) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
訪問接口,注意先判空。
七、力扣中棧和隊(duì)列OJ題
1、有效的括號
使用隊(duì)列來解決,創(chuàng)建一個(gè)棧,碰到左括號將其進(jìn)棧,碰到右括號則訪問棧頂元素,不相符則為false,迭代比較相符則為true
bool isValid(char * s){ ST st; StackInit(&st); while(*s) { if(*s=='('||*s=='{'||*s=='[') { StackPush(&st,*s);//壓棧 } else//比較時(shí)的情況 { if(StackEmpty(&st)) return false; else if(StackTop(&st)=='('&&*s!=')')//訪問棧頂元素 { return false; } else if(StackTop(&st)=='{'&&*s!='}') { return false; } else if(StackTop(&st)=='['&&*s!=']') { return false; } StackPop(&st); } ++s; } if(!StackEmpty(&st)) return false; StackDestroy(&st); return true; }
注:上述代碼還需要將棧的實(shí)現(xiàn)的代碼拷貝一份上去。
2、用隊(duì)列實(shí)現(xiàn)棧
入棧:選擇非空隊(duì)列進(jìn)行入棧
出棧:隊(duì)列中只留一個(gè)元素,將其他元素Pop至另一個(gè)隊(duì)列,再對那個(gè)遺留的元素執(zhí)行出隊(duì)列操作即可模擬出棧動(dòng)作
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x);//入隊(duì),尾插 } else { QueuePush(&obj->q2,x);//入隊(duì),尾插 } } int myStackPop(MyStack* obj) { Queue* empty=&obj->q1; Queue* unEmpty=&obj->q2; if(QueueEmpty(&obj->q2)) { empty=&obj->q2; unEmpty=&obj->q1; } while(QueueSize(unEmpty)>1)//將非空元素導(dǎo)入到空隊(duì)列,留下最后一個(gè) { QueuePush(empty,QueueFront(unEmpty));//入隊(duì),尾插 QueuePop(unEmpty);//出隊(duì)(頭刪) } int top=QueueFront(unEmpty); QueuePop(unEmpty);//出隊(duì)(頭刪) return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1);//訪問隊(duì)尾數(shù)據(jù) } else { return QueueBack(&obj->q2);//訪問隊(duì)尾數(shù)據(jù) } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1);//銷毀 QueueDestroy(&obj->q2);//銷毀 free(obj); }
注:上述代碼還需要將隊(duì)列的實(shí)現(xiàn)的代碼拷貝一份上去。
3、用棧實(shí)現(xiàn)隊(duì)列
現(xiàn)在有兩個(gè)棧,第一個(gè)棧用于入棧、出棧至第二個(gè)棧的操作,第二個(gè)棧僅用于出棧操作。
入棧:在第一個(gè)棧中壓入數(shù)據(jù)
出棧:如果第二個(gè)棧為空,則第一個(gè)棧中 數(shù)據(jù)全部出棧至第二個(gè)棧,由第二個(gè)棧專門執(zhí)行出棧操作。等第二個(gè)棧再次為空,再次執(zhí)行上述動(dòng)作
MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->st1); StackInit(&obj->st2); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->st1, x);//壓棧 } int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->st2)) { while(!StackEmpty(&obj->st1)) { StackPush(&obj->st2, StackTop(&obj->st1));//壓棧 StackPop(&obj->st1); } } int val=StackTop(&obj->st2); StackPop(&obj->st2); return val; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->st2)) { while(!StackEmpty(&obj->st1)) { StackPush(&obj->st2, StackTop(&obj->st1));//壓棧 StackPop(&obj->st1); } } return StackTop(&obj->st2); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->st1); StackDestroy(&obj->st2); free(obj); }
注:上述代碼還需要將棧的實(shí)現(xiàn)的代碼拷貝一份上去。
4、設(shè)計(jì)循環(huán)隊(duì)列
typedef struct { int* arr; int front;//記錄首 int tail;//記錄尾的下一個(gè) int capacity;//用于處理邊界問題的一個(gè)變量 } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->arr=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->tail=0; obj->capacity=k+1;//這里一定要寫成k+1,寫成k的話,后續(xù)處理邊界問題要額外考慮分支情況 return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1)%(obj->capacity)==obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->arr[obj->tail]=value; obj->tail++; obj->tail%=obj->capacity; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front%=obj->capacity; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); obj->arr=NULL; free(obj); }
因?yàn)檠h(huán)隊(duì)列無法區(qū)分隊(duì)列為空和為滿的情況,因?yàn)闉榭蘸臀礉M,首位下標(biāo)是一樣的。
所以這道題有兩種解法,計(jì)數(shù)確定??諚M,或者多開辟一個(gè)空間。本題采用后者。
可選的數(shù)據(jù)結(jié)構(gòu)也有兩種,順序和鏈表。本題采用順序。
上表為隊(duì)列滿的情況,無法再執(zhí)行插入。運(yùn)用順序表,本題的難點(diǎn)在于如何處理tail和front在數(shù)組尾部的情況。
強(qiáng)烈建議在初始化的接口中將capacity定義為k+1,因?yàn)槿腙?duì)出隊(duì)接口中%capacity后,可以同時(shí)滿足正常和極端位置下的情況。(詳見代碼,一讀就懂,后續(xù)讀者可以逝一下將capacity定義為k,感受下區(qū)別)
capacity定義為k時(shí)的代碼如下:
typedef struct { int* arr; int front;//記錄首 int tail;//記錄尾的下一個(gè) int capacity;//總?cè)萘? } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->arr=(int*)malloc(sizeof(int)*(k+1)); obj->front=obj->tail=0; obj->capacity=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail+1)%(obj->capacity+1)==obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->arr[obj->tail]=value; obj->tail++; if(obj->tail>obj->capacity) obj->tail=obj->tail%obj->capacity-1; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; if(obj->front>obj->capacity) obj->front=obj->front%obj->capacity-1; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; if(obj->tail!=0) return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity]; return obj->arr[obj->capacity]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); obj->arr=NULL; free(obj); }
主要區(qū)別就是入隊(duì)出隊(duì)代碼,常規(guī)情況和邊界情況不能統(tǒng)一。
以上就是C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列的實(shí)現(xiàn)及應(yīng)用的詳細(xì)內(nèi)容,更多關(guān)于C語言 棧 隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
淺析C/C++中的可變參數(shù)與默認(rèn)參數(shù)
C支持可變參數(shù)的函數(shù),這里的意思是C支持函數(shù)帶有可變數(shù)量的參數(shù),最常見的例子就是我們十分熟悉的printf()系列函數(shù)。我們還知道在函數(shù)調(diào)用時(shí)參數(shù)是自右向左壓棧的2013-09-09Java?C++?算法題解拓展leetcode670最大交換示例
這篇文章主要介紹了Java?C++算法題解拓展leetcode670最大交換示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-09-09C++實(shí)現(xiàn)模擬shell命令行(代碼解析)
這篇文章主要介紹了C++實(shí)現(xiàn)模擬shell命令行,本文通過實(shí)例代碼進(jìn)行命令行解析,代碼簡單易懂,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-12-12Qt 鼠標(biāo)/觸屏繪制平滑曲線(支持矢量/非矢量方式)
這篇文章主要介紹了Qt 鼠標(biāo)/觸屏繪制平滑曲線(支持矢量/非矢量方式),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析
鏈表可以說是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了,而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的,不同元素之間在邏輯上相鄰,但是在物理上并不一定相鄰。在維護(hù)一組數(shù)據(jù)集合時(shí),就可以使用鏈表,這一點(diǎn)和數(shù)組很相似2021-11-11Qt實(shí)現(xiàn)數(shù)據(jù)導(dǎo)出到xls的示例代碼
導(dǎo)入導(dǎo)出數(shù)據(jù)到csv由于語法簡單,適用場景有限,于是本文將為大家介紹Qt如何實(shí)現(xiàn)導(dǎo)出數(shù)據(jù)到xls,感興趣的小伙伴可以跟隨小編一起試一試2022-01-01