隊(duì)列：只允許在一端進(jìn)行插入陪腌，在另一端進(jìn)行刪除的線性表烹骨。
鏈隊(duì)列：使用鏈表實(shí)現(xiàn)的隊(duì)列缆瓣；具有隊(duì)頭指針和隊(duì)尾指針喧枷，指示隊(duì)列元素所在的位置。
鏈隊(duì)列特性：
- 只能隊(duì)尾插入元素弓坞、在隊(duì)頭刪除元素隧甚。
- 先進(jìn)先出（First In First Out）的線性表，先進(jìn)入的元素出隊(duì)渡冻，后進(jìn)入的元素才能出隊(duì)戚扳。
優(yōu)點(diǎn)：
- 相比普通的隊(duì)列，元素出隊(duì)時(shí)無需移動(dòng)大量元素族吻，只需移動(dòng)頭指針帽借。
- 可動(dòng)態(tài)分配空間，不需要預(yù)先分配大量存儲(chǔ)空間超歌。
- 適合處理用戶排隊(duì)等待的情況砍艾。
缺點(diǎn)：
- 需要為表中的邏輯關(guān)系增加額外的存儲(chǔ)空間。
時(shí)間復(fù)雜度
- 讀取時(shí)的時(shí)間復(fù)雜度為O(1)巍举。
- 插入辐董、刪除時(shí)的時(shí)間復(fù)雜度為O(1)。
隊(duì)列示意圖
空鏈隊(duì)列示意圖
鏈隊(duì)列插入元素示意圖
鏈隊(duì)列刪除元素示意圖
實(shí)現(xiàn)代碼如下：
// 隊(duì)列（鏈隊(duì)列）
#include <stdio.h>
#include <malloc.h>
#include <math.h>
#define OK 1 // 執(zhí)行成功
#define ERROR 0 // 執(zhí)行失敗
#define TRUE 1 // 返回值為真
#define FALSE 0 // 返回值為假
typedef int Status; // 函數(shù)返回結(jié)果類型
typedef int ElemType; // 元素類型
// 隊(duì)列節(jié)點(diǎn)
typedef struct QNode {
ElemType data; // 元素值
struct QNode *next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} QNode, *QueuePtr;
// 鏈隊(duì)列結(jié)構(gòu)
typedef struct {
QueuePtr front, rear; // 隊(duì)頭指針禀综、隊(duì)尾指針
} LinkQueue;
/**
* 初始化隊(duì)列
* @param Q 隊(duì)列
* @return 執(zhí)行狀態(tài)
*/
Status InitQueue(LinkQueue *Q) {
// 為隊(duì)頭和隊(duì)尾指針分配內(nèi)存
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
// 內(nèi)存分配失敗简烘，結(jié)束程序
if (!Q->front || !Q->rear) {
exit(OVERFLOW);
}
Q->front->next = NULL; // 隊(duì)頭節(jié)點(diǎn)指向NULL
return OK;
}
/**
* 銷毀隊(duì)列
* @param Q 隊(duì)列
* @return 執(zhí)行狀態(tài)
*/
Status DestroyQueue(LinkQueue *Q) {
// 當(dāng)隊(duì)列中還有元素
while (Q->front) {
Q->rear = Q->front->next;// 隊(duì)尾指針指向隊(duì)頭指針的下一個(gè)元素
free(Q->front); // 釋放隊(duì)頭指針?biāo)诠?jié)點(diǎn)
Q->front = Q->rear; // 隊(duì)頭指針指向隊(duì)尾指針（即原來的下一個(gè)元素）
}
return OK;
}
/**
* 清空隊(duì)列
* @param Q 隊(duì)列
* @return 執(zhí)行狀態(tài)
*/
Status ClearQueue(LinkQueue *Q) {
QueuePtr p, q; // p用來遍歷隊(duì)列節(jié)點(diǎn)苔严，q用來指向被刪除的節(jié)點(diǎn)
Q->rear = Q->front; // 隊(duì)尾指針指向隊(duì)頭指針
p = Q->front->next; // p指向隊(duì)頭指針的下一個(gè)節(jié)點(diǎn)
Q->front->next = NULL; // 隊(duì)頭指針的下一個(gè)節(jié)點(diǎn)指向NULL（表示刪除之后的所有元素）
// 當(dāng)隊(duì)列中還有元素，釋放頭節(jié)點(diǎn)之后的所有節(jié)點(diǎn)
while (p) {
q = p; // q節(jié)點(diǎn)指向被刪除節(jié)點(diǎn)
p = p->next; // p指向隊(duì)列的下一個(gè)節(jié)點(diǎn)
free(q); // 釋放q節(jié)點(diǎn)
}
return OK;
}
/**
* 判斷隊(duì)列是否為空
* @param Q 隊(duì)列
* @return 隊(duì)列是否為空
*/
Status QueueEmpty(LinkQueue Q) {
// 頭指針和尾指針位置相等孤澎，隊(duì)列為空
if (Q.front == Q.rear) {
return TRUE;
} else {
return FALSE;
}
}
/**
* 獲取隊(duì)列長(zhǎng)度
* @param Q 隊(duì)列
* @return 隊(duì)列長(zhǎng)度
*/
int QueueLength(LinkQueue Q) {
int i = 0; // 用于統(tǒng)計(jì)隊(duì)列長(zhǎng)度的計(jì)數(shù)器
QueuePtr p; // 用于遍歷隊(duì)列的元素
p = Q.front; // p指向隊(duì)頭節(jié)點(diǎn)
// 當(dāng)p沒有移動(dòng)到隊(duì)尾指針位置
while (p != Q.rear) {
i++; // 計(jì)數(shù)器加1
p = p->next; // p移動(dòng)到隊(duì)列的下一個(gè)節(jié)點(diǎn)
}
return i; // 返回隊(duì)列長(zhǎng)度
}
/**
* 獲取隊(duì)列頭元素
* @param Q 隊(duì)列
* @param e 存儲(chǔ)頭元素值
* @return 執(zhí)行狀態(tài)
*/
Status GetHead(LinkQueue Q, ElemType *e) {
QueuePtr p;
// 隊(duì)列為空届氢，獲取失敗
if (Q.front == Q.rear) {
return ERROR;
}
p = Q.front->next; // p指向隊(duì)列的第一個(gè)元素
*e = p->data; // 將隊(duì)列頭元素的值賦值給e元素
return OK;
}
/**
* 在隊(duì)列的隊(duì)尾處插入元素
* @param Q 隊(duì)列
* @param e 插入元素值
* @return 執(zhí)行狀態(tài)
*/
Status EnQueue(LinkQueue *Q, ElemType e) {
// 給新節(jié)點(diǎn)分配空間
QueuePtr s = (QueuePtr) malloc(sizeof(QNode));
// 分配空間失敗，結(jié)束程序
if (!s) {
exit(OVERFLOW);
}
s->data = e; // 將值賦值給新節(jié)點(diǎn)
s->next = NULL; // 新節(jié)點(diǎn)指向NULL
Q->rear->next = s; // 隊(duì)尾指針的下一個(gè)元素指向新節(jié)點(diǎn)
Q->rear = s; // 隊(duì)尾指針指向新節(jié)點(diǎn)（新節(jié)點(diǎn)成為隊(duì)尾指針的指向的節(jié)點(diǎn)）
return OK;
}
/**
* 刪除隊(duì)頭元素
* @param Q 隊(duì)列
* @param e 存儲(chǔ)出隊(duì)元素的值
* @return 執(zhí)行狀態(tài)
*/
Status DeQueue(LinkQueue *Q, ElemType *e) {
QueuePtr p; // 用于指向被刪除節(jié)點(diǎn)
// 隊(duì)列為空覆旭，出隊(duì)失敗
if (Q->front == Q->rear) {
return ERROR;
}
p = Q->front->next; // p指向隊(duì)列的第一個(gè)元素
*e = p->data; // 將隊(duì)列頭節(jié)點(diǎn)的值賦值給元素e
Q->front->next = p->next; // 頭指針的下一個(gè)節(jié)點(diǎn)指向下下個(gè)節(jié)點(diǎn)（跳過頭節(jié)點(diǎn)）
// 如果被刪除節(jié)點(diǎn)是隊(duì)尾指針指向的節(jié)點(diǎn)（刪除后隊(duì)列為空）
if (Q->rear == p) {
Q->rear = Q->front; // 隊(duì)尾指針指向隊(duì)頭指針
}
free(p); // 釋放隊(duì)頭節(jié)點(diǎn)
return OK;
}
/**
* 打印單個(gè)元素
* @param e 元素值
* @return 執(zhí)行狀態(tài)
*/
Status visit(ElemType e) {
printf("%d ", e);
return OK;
}
/**
* 遍歷隊(duì)列中的元素
* @param Q 隊(duì)列
* @return 執(zhí)行狀態(tài)
*/
Status QueueTravel(LinkQueue Q) {
QueuePtr p; // 用于遍歷隊(duì)列中的節(jié)點(diǎn)
p = Q.front->next; // p指向頭節(jié)點(diǎn)
printf("[ ");
// 當(dāng)隊(duì)列中還有元素
while (p) {
visit(p->data); // 打印當(dāng)前節(jié)點(diǎn)的值
p = p->next; // p移動(dòng)到隊(duì)列下一個(gè)位置
}
printf("]\n");
return OK;
}
int main() {
Status status; // 執(zhí)行狀態(tài)
int j; // j用來遍歷
ElemType e; // 元素值
LinkQueue Q; // 隊(duì)列
/*** 初始化隊(duì)列 ***/
InitQueue(&Q); // 初始化隊(duì)列
printf("初始化隊(duì)列后退子，隊(duì)列是否為空？%s\n", QueueEmpty(Q) == TRUE ? "是" : "否");
/*** 向隊(duì)列中插入10個(gè)元素 ***/
for (j = 1; j <=10; ++j) {
EnQueue(&Q, j); // 將元素j插入隊(duì)列
}
printf("插入10個(gè)元素后隊(duì)列的值為：");
QueueTravel(Q); // 遍歷隊(duì)列
printf("隊(duì)列的長(zhǎng)度為：%d\n", QueueLength(Q)); // 獲取隊(duì)列長(zhǎng)度
printf("插入10個(gè)元素后型将，隊(duì)列是否為空寂祥？%s\n", QueueEmpty(Q) == TRUE ? "是" : "否");
/*** 刪除隊(duì)列中的五個(gè)元素，并打印對(duì)應(yīng)的值 ***/
printf("開始刪除元素：\n");
for (j = 0; j < 5; ++j) {
DeQueue(&Q, &e); // 刪除隊(duì)頭元素七兜，將值存到e中
printf("元素%d出隊(duì)\n", e);
}
printf("5個(gè)元素出隊(duì)后丸凭，隊(duì)列中的值為：");
QueueTravel(Q); // 遍歷隊(duì)列
printf("隊(duì)列的長(zhǎng)度為：%d\n", QueueLength(Q)); // 獲取隊(duì)列長(zhǎng)度
/*** 獲取隊(duì)列頭元素的值 ***/
status = GetHead(Q, &e); // 獲取隊(duì)列頭元素
if (status) {
printf("隊(duì)列頭元素為：%d\n", e);
}
/*** 清空隊(duì)列元素 ***/
ClearQueue(&Q); // 清空隊(duì)列元素
printf("清空隊(duì)列后，隊(duì)列是否為空：%s\n", QueueEmpty(Q) == TRUE ? "是" : "否");
printf("隊(duì)列中的元素為：");
QueueTravel(Q); // 遍歷元素
return 0;
}
運(yùn)行結(jié)果
