一、隊(duì)列的概念及結(jié)構(gòu)
1、概念
隊(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ì)頭。
2、結(jié)構(gòu)
（1）隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
- 入隊(duì)，不需要移動(dòng)任何元素，時(shí)間復(fù)雜度為?O(1) 。
- 出隊(duì)，所有元素需要往前移動(dòng)，時(shí)間復(fù)雜度為?O(N) 。
（2）隊(duì)列的鏈表存儲(chǔ)結(jié)構(gòu)
首先我們定義兩個(gè)指針，隊(duì)頭指針指向第一個(gè)節(jié)點(diǎn)，隊(duì)尾指針指向尾節(jié)點(diǎn)。
- 入隊(duì)（尾插），時(shí)間復(fù)雜度為 O(1) 。
- 出隊(duì)（頭刪），時(shí)間復(fù)雜度為 O(1) 。
?二、隊(duì)列的實(shí)現(xiàn)
如果使用數(shù)組刪除隊(duì)頭數(shù)據(jù)，再挪動(dòng)數(shù)據(jù)效率為 O(N)，不適合。?選擇用單向鏈表來(lái)完成隊(duì)列的實(shí)現(xiàn)更好，可以發(fā)現(xiàn)頭刪和尾插效率都很高，而雙向鏈表在這里發(fā)揮不出很大的作用。
1、創(chuàng)建文件
- test.c（主函數(shù)、測(cè)試隊(duì)列各個(gè)接口功能）
- Queue.c（隊(duì)列接口函數(shù)的實(shí)現(xiàn)）
- Queue.h（隊(duì)列的類型定義、接口函數(shù)聲明、引用的頭文件）
2、Queue.h 頭文件代碼
// Queue.h
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
#pragma once
#include<stdio.h>
#include<stdbool.h> //bool
#include<assert.h> // assert
#include<stdlib.h> // malloc
typedef int QDataType;
typedef struct QueueNode // 隊(duì)列節(jié)點(diǎn)結(jié)構(gòu)
{
struct QueueNode* next; // 節(jié)點(diǎn)指針
QDataType data; // 節(jié)點(diǎn)數(shù)據(jù)
}QueueNode;
typedef struct Queue // 隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)
{
QueueNode* head; //隊(duì)頭指針
QueueNode* tail; //隊(duì)尾指針
}Queue;
// 初始化隊(duì)列
void QueueInit(Queue* pq);
// 銷毀隊(duì)列
void QueueDestroy(Queue* pq);
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType data);
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* pq);
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq);
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* pq);
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq);
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq); 三、Queue.c 中各個(gè)接口函數(shù)的實(shí)現(xiàn)
1、初始化隊(duì)列
// 初始化隊(duì)列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}2、隊(duì)列的銷毀
// 銷毀隊(duì)列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
cur = NULL;
pq->head = pq->tail = NULL;
}3、隊(duì)尾入隊(duì)列（尾插）
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
newnode->data = x;
newnode->next = NULL; // 尾節(jié)點(diǎn)next指針置空
if (pq->head == NULL) // 隊(duì)列為空
{
pq->head = pq->tail = newnode;
}
else // 隊(duì)列不為空
{
pq->tail->next = newnode;
pq->tail = newnode; // 更新隊(duì)尾指針
}
}4、隊(duì)頭出隊(duì)列（頭刪）
// 隊(duì)頭出隊(duì)列
// 寫(xiě)法一：
void QueuePop(Queue* pq)
{
assert(pq);
//溫柔處理方式：
/* if(pq->head == NULL)
return; */
//暴力處理方式：
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next; // 記錄頭節(jié)點(diǎn)的直接后繼
free(pq->head); // 釋放頭節(jié)點(diǎn)
pq->head = next; // 更新隊(duì)頭指針
if (pq->head == NULL) // 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
{
pq->tail = NULL;
}
}
// 寫(xiě)法二：
void QueuePop(Queue* pq)
{
assert(pq);
//暴力處理方式：
assert(!QueueEmpty(pq));
if(pq->head->next == NULL) // 一個(gè)節(jié)點(diǎn)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else // 多個(gè)節(jié)點(diǎn)
{
QueueNode* next = pq->head->next; // 記錄頭節(jié)點(diǎn)的直接后繼
free(pq->head); // 釋放頭節(jié)點(diǎn)
pq->head = next; // 更新隊(duì)頭指針
}
}注意：鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，要單獨(dú)處理，否則可能會(huì)造成 pq->tail 野指針的情況。?
5、獲取隊(duì)列頭部元素
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}6、獲取隊(duì)列隊(duì)尾元素
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}7、獲取隊(duì)列中有效元素個(gè)數(shù)
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}如果頻繁調(diào)用這個(gè)接口函數(shù)，可以在 QueuePtr 中加一個(gè) size 來(lái)記錄數(shù)據(jù)的個(gè)數(shù)。?
8、檢查隊(duì)列是否為空
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq);
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}四、整合代碼
// Queue.c
#include "Queue.h"
// 初始化隊(duì)列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
// 銷毀隊(duì)列
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
cur = NULL;
pq->head = pq->tail = NULL;
}
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); // 動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)
newnode->data = x;
newnode->next = NULL; // 尾節(jié)點(diǎn)next指針置空
if (pq->head == NULL) // 隊(duì)列為空
{
pq->head = pq->tail = newnode;
}
else // 隊(duì)列不為空
{
pq->tail->next = newnode;
pq->tail = newnode; // 更新隊(duì)尾指針
}
}
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next; // 記錄頭節(jié)點(diǎn)的直接后繼
free(pq->head); // 釋放頭節(jié)點(diǎn)
pq->head = next; // 更新隊(duì)頭指針
if (pq->head == NULL) // 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
{
pq->tail = NULL;
}
}
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
n++;
cur = cur->next;
}
return n;
}
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq);
{
assert(pq);
return pq->head == NULL && pq->tail == NULL;
}五、測(cè)試隊(duì)列的功能
六、拓展?
實(shí)際中我們有時(shí)還會(huì)使用一種隊(duì)列叫循環(huán)隊(duì)列。環(huán)形隊(duì)列可以使用數(shù)組實(shí)現(xiàn)，也可以使用循環(huán)鏈表實(shí)現(xiàn)。
1、空的循環(huán)隊(duì)列
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-618913.html
2、滿的循環(huán)隊(duì)列
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-618913.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】隊(duì)列（Queue）的實(shí)現(xiàn) -- 詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu) -- C語(yǔ)言] 隊(duì)列(Queue)](https://imgs.yssmx.com/Uploads/2024/02/467525-1.png)
