C語言近萬字為你講透棧和隊(duì)列
一、棧與隊(duì)列以及雙端隊(duì)列的概念
1.1 棧的概念及結(jié)構(gòu)
棧:一種特殊的線性表,其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端 稱為棧頂,另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO(Last In First Out)的原則。
壓棧:棧的插入操作叫做進(jìn)棧/壓棧/入棧,入數(shù)據(jù)在棧頂。
出棧:棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
1.2 隊(duì)列的概念及結(jié)構(gòu)
隊(duì)列:只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表,隊(duì)列具有先進(jìn)先出 FIFO(First In First Out)
入隊(duì)列:進(jìn)行插入操作的一端稱為隊(duì)尾
出隊(duì)列:進(jìn)行刪除操作的一端稱為隊(duì)頭
1.3 雙端隊(duì)列的概念及結(jié)構(gòu)
雙端隊(duì)列:是一種線性表,又稱為雙向隊(duì)列,所有的插入和刪除(通常還有所有的訪問)都在表的兩端進(jìn)行。
二、棧的實(shí)現(xiàn)和模擬棧
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn),相對而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的 代價比較小。、
2.1 實(shí)現(xiàn)一個支持動態(tài)增長的棧
頭文件:
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct Stack//動態(tài)棧 { int *a; int top;//棧頂?shù)奈恢? int capacity;//容量 }ST; STDataType StackTop(ST* ps);//返回棧頂?shù)闹? void StackInit(ST* ps);//初始化棧 void StackDestory(ST* ps);//銷毀棧 void StackPop(ST* ps);//彈出 void StackPush(ST* ps, STDataType x);//插入 bool StackEmpty(ST* ps);//判斷棧是否為空。
源文件:
#include"Stack.h" void StackInit(ST* ps)//棧的初始化 { assert(ps); ps->a = NULL;//a點(diǎn)的值指向空 ps->top = 0;//棧底為0 ps->capacity = 0;//空間為0 } void StackDestory(ST* ps) { assert(ps); free(ps->a);//把a(bǔ)釋放掉 ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x)//入數(shù)據(jù) { assert(ps); //滿了就擴(kuò)容 if (ps->top == ps->capacity)//如果棧的棧頂恰好和容量相等就擴(kuò)容 { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newCapacity;//新的空間賦給舊的 } ps->a[ps->top] = x;//棧頂插入x; ps->top++;//top++ } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top;//top--就相當(dāng)于刪除操作 } bool StackEmpty(ST* ps) { assert(ps); //兩種寫法 //if (ps->top > 0) //{ // return false; //} //else //{ // return true; //} return ps->top == 0; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1];//訪問棧頂元素(這里因?yàn)閠op我們設(shè)為0,所以訪問棧頂元素相當(dāng)于top-1 } int StackSize(ST* ps) { assert(ps); return ps->top; }
2.2 數(shù)組模擬靜態(tài)棧
#include<iostream> using namespace std; const int N = 1e6 + 10; int n; int stk[N]; int top = - 1; int main () { cin >> n; while(n --) { string s; cin >> s; if(s == "push") { int a; cin >> a; stk[++top] = a; } if(s == "pop") { top--; } if(s == "empty") { if(top >= 0) printf("NO\n"); else printf("YES\n"); } if(s == "query") { printf("%d\n", stk[top]); } } return 0; }
三、 隊(duì)列的實(shí)現(xiàn)(動態(tài))和模擬靜態(tài)隊(duì)列
隊(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ù),效率會比較低。
3.1 實(shí)現(xiàn)一個支持動態(tài)增長的棧
頭文件:
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDataType;//方便改類型 typedef struct QueueNode//保存每個節(jié)點(diǎn)的數(shù)據(jù) { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; //上面的寫法等價于: //typedef struct Queue //{ // QNode* head; // QNode* tail; //}; // //typedef struct Queue Queue;// //一般實(shí)際情況哨兵位的頭節(jié)點(diǎn)不存儲值,不放數(shù)據(jù) void QueueInit(Queue* pq);//隊(duì)列初始化 void QueueDestory(Queue* pq);//隊(duì)列銷毀 void QueuePush(Queue* pq, QDataType x);//隊(duì)尾插入 void QueuePop(Queue* pq);//彈出隊(duì)頭 bool QueueEmpty(Queue* pq);//判斷是否為空 size_t QueueSize(Queue* pq);//size_t相當(dāng)于Unsinged int QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq);
源文件:
#include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next;//先記錄下一個位置 free(cur);//free掉cur指針 cur = next;//cur賦值到下一個位置 } pq->head = pq->tail = NULL;//置空 } void QueuePush(Queue* pq, QDataType x)//隊(duì)尾插入//插入int類型的參數(shù) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x;//新的節(jié)點(diǎn)的值被賦與x newnode->next = NULL;//新的節(jié)點(diǎn)是在隊(duì)尾,所以指向的下一個位置是空 if (pq->tail == NULL)//如果鏈表的第一個值為空,則head = tail = NULL { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else//尾插 { pq->tail->next = newnode;//先改指向 pq->tail = newnode;//再改地址 } } void QueuePop(Queue* pq)//彈出隊(duì)首 { assert(pq); assert(pq->head && pq->tail); if (pq->head->next == NULL)//只有一個節(jié)點(diǎn) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next;//QNode* next相當(dāng)于是QDataType的頭指針的下一個位置 free(pq->head); pq->head = next;//頭往后走 } } bool QueueEmpty(Queue* pq) { assert(pq); //return pq->head == NULL && pq->tail == NULL; return pq->head == NULL;//程序調(diào)試了快一個小時就是因?yàn)閜q->head沒加后面的== NULL } size_t QueueSize(Queue* pq)//size_t相當(dāng)于Unsinged int { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } QDataType QueueFront(Queue* pq)//返回隊(duì)頭第一個位的值 { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq)//返回隊(duì)尾的值 { assert(pq); assert(pq->tail); return pq->tail->data; }
3.2 數(shù)組模擬靜態(tài)隊(duì)列
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; int q[N]; int n; int hh ,tt = -1;//hh表示頭,tt表示尾 int main () { cin >> n; while(n --) { string s; cin >> s; if(s == "push") { int x; cin >> x; q[++tt] = x; } else if(s == "pop") { hh ++; } else if(s == "empty") { if(hh <= tt) printf("NO\n");//尾在邏輯上要比頭更前面 else printf("YES\n"); } else cout << q[hh] << endl; } return 0; }
四、leetcode-棧實(shí)現(xiàn)隊(duì)列和用隊(duì)列實(shí)現(xiàn)棧
225. 用隊(duì)列實(shí)現(xiàn)棧 - 力扣(LeetCode)
代碼:
typedef int QDataType; typedef struct QueueNode//保存每個節(jié)點(diǎn)的數(shù)據(jù) { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x);//隊(duì)尾插入 void QueuePop(Queue* pq); bool QueueEmpty(Queue* pq); size_t QueueSize(Queue* pq);//size_t相當(dāng)于Unsinged int QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next;//先記錄下一個位置 free(cur);//free掉cur指針 cur = next;//cur賦值到下一個位置 } pq->head = pq->tail = NULL;//置空 } void QueuePush(Queue* pq, QDataType x)//隊(duì)尾插入 { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL)//如果鏈表的第一個值為空,則head = tail = NULL { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else//尾插 { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq)//彈出隊(duì)首 { assert(pq); assert(pq->head && pq->tail); if (pq->head->next == NULL)//只有一個節(jié)點(diǎn) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next;//QNode* next相當(dāng)于是QDataType的頭指針的下一個位置 free(pq->head); pq->head = next;//頭往后走 } } bool QueueEmpty(Queue* pq) { assert(pq); //return pq->head == NULL && pq->tail == NULL; return pq->head == NULL;//程序調(diào)試了快一個小時就是因?yàn)閜q->head沒加后面的== NULL } size_t QueueSize(Queue* pq)//size_t相當(dāng)于Unsinged int { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } QDataType QueueFront(Queue* pq)//返回隊(duì)頭第一個位的值 { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); assert(pst); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { assert(obj); if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } } int myStackPop(MyStack* obj) { Queue* emptyQ = &obj->q1;//假設(shè)q1為空,q2不為空 Queue* nonEmptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; nonEmptyQ = &obj->q1; } //把非空隊(duì)列的前N個數(shù)據(jù)導(dǎo)入空隊(duì)列,剩下一個刪掉 //就實(shí)現(xiàn)了后進(jìn)先出 while(QueueSize(nonEmptyQ) > 1) { QueuePush(emptyQ, QueueFront(nonEmptyQ)); QueuePop(nonEmptyQ); } int top = QueueFront(nonEmptyQ);//此時那個非空的隊(duì)列只剩下一個數(shù)據(jù) QueuePop(nonEmptyQ); return top; } int myStackTop(MyStack* obj) { assert(obj); if(!QueueEmpty(&obj->q1))//如果q1不為空 { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { assert(obj); QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); }
232. 用棧實(shí)現(xiàn)隊(duì)列 - 力扣(LeetCode)棧是后進(jìn)先出
思路:設(shè)計(jì)兩個棧,一個棧專門用來入數(shù)據(jù),一個棧專門用來出數(shù)據(jù)。
typedef int STDataType; typedef struct Stack//動態(tài)鏈表 { int *a; int top;//棧頂?shù)奈恢? int capacity;//容量 }ST; STDataType StackTop(ST* ps); void StackInit(ST* ps);//初始化棧 void StackDestory(ST* ps); void StackPop(ST* ps); void StackPush(ST* ps, STDataType x); bool StackEmpty(ST* ps); void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x)//入數(shù)據(jù) { assert(ps); //滿了就擴(kuò)容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; } bool StackEmpty(ST* ps) { assert(ps); //兩種寫法 //if (ps->top > 0) //{ // return false; //} //else //{ // return true; //} return ps->top == 0; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1];//訪問棧頂元素 } int StackSize(ST* ps) { assert(ps); return ps->top; } typedef struct { ST pushST; ST popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); assert(obj); StackInit(&obj->pushST);//&符要加,要改變結(jié)構(gòu)體里面的內(nèi)容 StackInit(&obj->popST); return obj; } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->pushST, x); } int myQueuePop(MyQueue* obj) { assert(obj); //如果popST為空, 把pushST的數(shù)據(jù)拿過來,就符合先進(jìn)先出的順序了 if(StackEmpty(&obj->popST))//如果ST Pop為空就執(zhí)行 { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST, StackTop(&obj->pushST)); StackPop(&obj->pushST);//把pushST里的數(shù)據(jù)刪掉 } } int front = StackTop(&obj->popST);//記錄棧頂?shù)臄?shù)據(jù) StackPop(&obj->popST); return front; } int myQueuePeek(MyQueue* obj) { assert(obj); //如果popST為空, 把pushST的數(shù)據(jù)拿過來,就符合先進(jìn)先出的順序了 if(StackEmpty(&obj->popST))//如果ST Pop為空就執(zhí)行 { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST, StackTop(&obj->pushST)); StackPop(&obj->pushST);//把pushST里的數(shù)據(jù)刪掉 } } return StackTop(&obj->popST); } bool myQueueEmpty(MyQueue* obj) { assert(obj); return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST); } void myQueueFree(MyQueue* obj) { assert(obj); StackDestory(&obj->pushST); StackDestory(&obj->popST); free(obj); }
總結(jié)
本文分別從(1)棧、隊(duì)列以及雙端隊(duì)列的概念、(2)棧的實(shí)現(xiàn)(動態(tài))和模擬靜態(tài)棧、(3)隊(duì)列的實(shí)現(xiàn)(動態(tài))和模擬靜態(tài)隊(duì)列、(4)leetcode-棧實(shí)現(xiàn)隊(duì)列和用隊(duì)列實(shí)現(xiàn)棧四個方面對棧和隊(duì)列這兩個數(shù)據(jù)結(jié)構(gòu)進(jìn)行了分析,希望大家讀后能夠有所收獲,也希望大家多多支持。
到此這篇關(guān)于C語言近萬字為你講透棧和隊(duì)列的文章就介紹到這了,更多相關(guān)C語言棧和隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
解析C++中的虛擬函數(shù)及其靜態(tài)類型和動態(tài)類型
虛擬函數(shù)(Visual Function)亦常被成為虛函數(shù),是C++中的一個重要特性,本文我們就來解析C++中的虛擬函數(shù)及其靜態(tài)類型和動態(tài)類型2016-06-06C++數(shù)位DP復(fù)雜度統(tǒng)計(jì)數(shù)字問題示例詳解
這篇文章主要為大家介紹了利用C++數(shù)位DP的復(fù)雜度來統(tǒng)計(jì)數(shù)字問題的示例實(shí)現(xiàn)過程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升值加薪2021-11-11