本期帶大家一起用C語(yǔ)言實(shí)現(xiàn)隊(duì)列??????
1、隊(duì)列的概念
隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，它按照先進(jìn)先出（FIFO）的原則進(jìn)行操作?？梢园殃?duì)列想象成排隊(duì)買票或者排隊(duì)上公交車的隊(duì)伍。
順序隊(duì)列由一個(gè)連續(xù)的內(nèi)存區(qū)域組成，可以存儲(chǔ)多個(gè)元素。隊(duì)列有兩個(gè)指針，分別指向隊(duì)頭（Front）和隊(duì)尾（Rear）。鏈?zhǔn)疥?duì)列由一系列節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)包含存儲(chǔ)的元素值和指向下一個(gè)節(jié)點(diǎn)的指針
隊(duì)列的基本操作包括：
- 入隊(duì)（Enqueue）：將新元素插入到隊(duì)尾，如果隊(duì)列已滿則無法插入。
- 出隊(duì)（Dequeue）：移除隊(duì)頭元素，并返回該元素，如果隊(duì)列為空則無法執(zhí)行。
- 獲取隊(duì)頭元素（Front）：獲取隊(duì)頭元素的值，但不對(duì)隊(duì)列進(jìn)行修改。
- 判斷隊(duì)列是否為空（isEmpty）：判斷隊(duì)列中是否沒有任何元素。
- 判斷隊(duì)列是否已滿（isFull）：判斷隊(duì)列是否已經(jīng)達(dá)到了最大容量。
隊(duì)列的操作遵循先進(jìn)先出的原則，即先入隊(duì)的元素先出隊(duì)。在隊(duì)列中，新元素被插入到隊(duì)列的末尾，而出隊(duì)操作始終從隊(duì)列的頭部進(jìn)行。
隊(duì)列常用于需要順序處理任務(wù)或數(shù)據(jù)的場(chǎng)景，例如處理請(qǐng)求、消息傳遞、廣度優(yōu)先搜索等算法實(shí)現(xiàn)。此外，隊(duì)列還可以通過循環(huán)隊(duì)列的方式來實(shí)現(xiàn)，使得已經(jīng)出隊(duì)的元素可以再次被插入到隊(duì)列的末尾，有效地利用內(nèi)存空間。
2、隊(duì)列的操作流程
3 、隊(duì)列的結(jié)構(gòu)
隊(duì)列通常使用數(shù)組或鏈表來實(shí)現(xiàn)。以下是兩種常見的隊(duì)列結(jié)構(gòu)：
-
基于數(shù)組的隊(duì)列（
順序隊(duì)列）：- 使用一個(gè)固定大小的數(shù)組來保存隊(duì)列元素。
- 需要維護(hù)隊(duì)頭和隊(duì)尾的索引，分別指向隊(duì)列的第一個(gè)元素和最后一個(gè)元素。
- 入隊(duì)操作將元素添加到隊(duì)尾，并更新隊(duì)尾索引。
- 出隊(duì)操作將隊(duì)頭元素移除，并更新隊(duì)頭索引。
- 注意，入隊(duì)操作可能導(dǎo)致隊(duì)列滿（隊(duì)尾索引達(dá)到數(shù)組末尾）的情況，需要進(jìn)行特殊處理。
-
基于鏈表的隊(duì)列（
鏈?zhǔn)疥?duì)列）：- 使用鏈表來動(dòng)態(tài)存儲(chǔ)隊(duì)列元素。
- 需要維護(hù)隊(duì)頭和隊(duì)尾節(jié)點(diǎn)指針，分別指向隊(duì)列的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)。
- 入隊(duì)操作創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將其鏈接到鏈表末尾，更新隊(duì)尾指針。
- 出隊(duì)操作移除隊(duì)頭節(jié)點(diǎn)，并更新隊(duì)頭指針。
- 注意，鏈?zhǔn)疥?duì)列沒有固定的大小限制，可以根據(jù)需要?jiǎng)討B(tài)調(diào)整。
無論是基于數(shù)組還是鏈表的隊(duì)列，其核心思想都是維護(hù)隊(duì)頭和隊(duì)尾指針，并通過頭部和尾部的插入和刪除操作實(shí)現(xiàn)先進(jìn)先出的特性。根據(jù)具體的應(yīng)用場(chǎng)景和需求，選擇適合的隊(duì)列實(shí)現(xiàn)方式
在這里我們使用鏈表來實(shí)現(xiàn)隊(duì)列，避免了用數(shù)組隊(duì)列更新隊(duì)頭數(shù)據(jù)的遍歷，時(shí)間復(fù)雜度低
4、隊(duì)列的實(shí)現(xiàn)
4.1 隊(duì)列的結(jié)構(gòu)設(shè)計(jì)
Queue結(jié)構(gòu)體，它表示整個(gè)隊(duì)列。該結(jié)構(gòu)體包含兩個(gè)指針成員head和tail，分別指向隊(duì)列的頭部節(jié)點(diǎn)和尾部節(jié)點(diǎn)
QNode的結(jié)構(gòu)體，它表示隊(duì)列中的節(jié)點(diǎn)。該結(jié)構(gòu)體包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針next，以及一個(gè)數(shù)據(jù)data
typedef int QDataTYpe;
typedef struct QueueNode
{
struct QueueNode* next;
QDataTYpe data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
4.2 隊(duì)列的初始化
現(xiàn)在主函數(shù)當(dāng)中創(chuàng)建了一個(gè)Queue q
然后傳入q的地址，進(jìn)行初始化
將隊(duì)列的頭部指針和尾部指針設(shè)為NULL，并將隊(duì)列的大小初始化為0
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
4.3 入隊(duì)
在函數(shù)內(nèi)部，首先進(jìn)行斷言assert(pq)來確保指針pq不為空。
然后，通過動(dòng)態(tài)內(nèi)存分配malloc來創(chuàng)建一個(gè)新的節(jié)點(diǎn)newnode，并將其類型轉(zhuǎn)換為QNode*。
接下來，檢查是否成功分配內(nèi)存，如果分配失敗，則輸出錯(cuò)誤信息并返回。
然后，將新節(jié)點(diǎn)的數(shù)據(jù)成員data賦值為傳入的參數(shù)x，同時(shí)將新節(jié)點(diǎn)的下一個(gè)指針next設(shè)置為NULL，新節(jié)點(diǎn)表示當(dāng)前節(jié)點(diǎn)是隊(duì)列的尾部節(jié)點(diǎn)。
接著，根據(jù)隊(duì)列是否為空，有兩種情況處理：
- 如果隊(duì)列為空，即頭部指針
head為NULL，表示當(dāng)前隊(duì)列沒有任何節(jié)點(diǎn)，此時(shí)將頭部指針和尾部指針都指向新節(jié)點(diǎn)newnode。 - 如果隊(duì)列不為空，即頭部指針
head不為NULL，表示當(dāng)前隊(duì)列已存在節(jié)點(diǎn)，此時(shí)將隊(duì)列尾部節(jié)點(diǎn)的下一個(gè)指針next指向新節(jié)點(diǎn)newnode，然后將尾部指針tail更新為新節(jié)點(diǎn)newnode - 最后，將隊(duì)列的大小
size加1，表示新增了一個(gè)節(jié)點(diǎn)。
void QueuePush(Queue* pq,QDataTYpe x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));;
if (newnode == NULL)
{
perror("malloc:fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
4.4 判斷隊(duì)列是否為空
判斷隊(duì)列是否為空的話，相對(duì)來說是比較簡(jiǎn)單的
有兩種判斷方法
根據(jù)隊(duì)列的頭指針是否為空判斷
根據(jù)隊(duì)列當(dāng)中的數(shù)據(jù)個(gè)數(shù)size判斷
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
//return pq->size==0;
}
4.5 出隊(duì)
出隊(duì)列的話我們需要先判斷當(dāng)前隊(duì)列是否為空
隊(duì)列為空的話那我們就直接返回
隊(duì)列不為空的話又分兩種情況
1、隊(duì)頭指針==隊(duì)尾指針
2、隊(duì)頭指針！=隊(duì)尾指針
void QueuePop(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("隊(duì)列為空\(chéng)n");
return;
}
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
4.6 獲取隊(duì)頭數(shù)據(jù)
獲取隊(duì)頭數(shù)據(jù)的話，需要先判斷隊(duì)列是否為空，為空的話就直接返回
隊(duì)列不為空，返回隊(duì)頭數(shù)據(jù)
QDataTYpe QueueFront(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("隊(duì)列為空\(chéng)n");
return;
}
else
return pq->head->data;
}
4.7 獲取隊(duì)尾數(shù)據(jù)
獲取隊(duì)尾數(shù)據(jù)的話，同樣需要判斷隊(duì)列是否為空，為空的話也就直接返回
隊(duì)列不為空的話，返回隊(duì)尾數(shù)據(jù)
QDataTYpe QueueBack(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("隊(duì)列為空\(chéng)n");
return;
}
else
return pq->tail->data;
}
4.8 獲取隊(duì)列當(dāng)中數(shù)據(jù)的個(gè)數(shù)
獲取隊(duì)列數(shù)據(jù)的個(gè)數(shù)，直接返回pq->size
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
4.9 隊(duì)列的銷毀
使用循環(huán)遍歷隊(duì)列中的所有節(jié)點(diǎn)，直到遍歷到最后一個(gè)節(jié)點(diǎn)，即當(dāng)前節(jié)點(diǎn)為NULL
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
5、棧和隊(duì)列OJ題
5.1 隊(duì)列模擬棧
使用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧的重點(diǎn)在于以下幾點(diǎn)：
- 始終保持一個(gè)隊(duì)列為空，另一個(gè)隊(duì)列非空。
- 入數(shù)據(jù)時(shí)，將元素入隊(duì)到不為空的隊(duì)列中。
- 出數(shù)據(jù)時(shí)，將非空隊(duì)列中的元素轉(zhuǎn)移到空隊(duì)列中，直到隊(duì)列中只剩下一個(gè)元素。
- 出隊(duì)原先非空隊(duì)列的數(shù)據(jù)，原先非空隊(duì)列變?yōu)榭?，即可?shí)現(xiàn)棧的后進(jìn)先出操作。
通過將元素入隊(duì)到非空隊(duì)列、轉(zhuǎn)移到空隊(duì)列以及出隊(duì)的操作，可以模擬棧的后進(jìn)先出特性
typedef int QDataTYpe;
typedef struct QueueNode
{
struct QueueNode* next;
QDataTYpe data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataTYpe x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataTYpe QueueFront(Queue* pq);
QDataTYpe QueueBack(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
//return pq->size==0;
}
void QueuePush(Queue* pq,QDataTYpe x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));;
if (newnode == NULL)
{
perror("malloc:fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("隊(duì)列為空\(chéng)n");
return;
}
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = NULL;
pq->head = next;
}
pq->size--;
}
QDataTYpe QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataTYpe QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
Queue q;
Queue p;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
{
return NULL;
}
QueueInit(&obj->p);
QueueInit(&obj->q);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(QueueEmpty(&obj->p))
{
QueuePush(&obj->q,x);
}
else
{
QueuePush(&obj->p,x);
}
}
int myStackPop(MyStack* obj) {
Queue*Empty=&obj->q;
Queue*NoEmpty=&obj->p;
if(QueueEmpty(&obj->p))
{
Empty=&obj->p;
NoEmpty=&obj->q;
}
while(QueueSize(NoEmpty)>1)
{
QueuePush(Empty,QueueFront(NoEmpty));
QueuePop(NoEmpty);
}
int top=QueueFront(NoEmpty);
QueuePop(NoEmpty);
return top;
}
int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->p))
{
return QueueBack(&obj->q);
}
else
return QueueBack(&obj->p);
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q)&&QueueEmpty(&obj->p);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q);
QueueDestroy(&obj->p);
free(obj);
}
5.2 棧模擬隊(duì)列
棧模擬隊(duì)列
棧模擬隊(duì)列的話，可以想象成一個(gè)連通器
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
//壓棧
void STPush(ST* ps,STDataType x);
//出棧
void STPop(ST* ps);
//判空
bool STEmpty(ST* ps);
//棧頂
STDataType STTop(ST* ps);
//個(gè)數(shù)
int STSize(ST* ps);
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STPush(ST* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc :fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
bool STEmpty(ST* ps)
{
return ps->top == 0;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int ret=myQueuePeek(obj);
STPop(&obj->popst);
return ret;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))
{
while(!(STEmpty(&obj->pushst)))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/
5.3 循環(huán)隊(duì)列
循環(huán)隊(duì)列
解決循環(huán)隊(duì)列問題的話
我們可以先定義固定大小的數(shù)組，用來存儲(chǔ)元素
例如，我們需要一個(gè)可以存儲(chǔ)3個(gè)數(shù)據(jù)的數(shù)組，我們現(xiàn)在就開辟4個(gè)數(shù)據(jù)的空間，以便于我們操作
typedef struct {
int front;
int rear;
int size;
int *a;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->size=k+1;
obj->front=0;
obj->rear=0;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if((obj->rear+1)%(obj->size)==obj->front)
return false;
obj->a[obj->rear]=value;
obj->rear++;
obj->rear%=obj->size;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return false;
(obj->front)++;
obj->front%=obj->size;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return -1;
return obj->a[(obj->rear-1+obj->size)%obj->size];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return true;
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear+1)%(obj->size)==obj->front)
return true;
return false;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a=NULL;
free(obj);
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
6、感謝與交流?
??????如果大家通過本篇博客收獲了,對(duì)隊(duì)列有了新的了解的話
那么希望支持一下哦如果還有不明白的，疑惑的話，或者什么比較好的建議的話，可以發(fā)到評(píng)論區(qū)，
我們一起解決，共同進(jìn)步 ??????
最后謝謝大家????????????文章來源：http://www.zghlxwxcb.cn/news/detail-563596.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-563596.html
到了這里，關(guān)于隊(duì)列--C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
