2.隊(duì)列

2.1隊(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ì)頭

2.2隊(duì)列的實(shí)現(xiàn)

隊(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ù)，效率會(huì)比較低。

• 隊(duì)列結(jié)構(gòu)

// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data; 
}QNode; 
// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{ QNode* _front; QNode* _rear; 
}Queue; 

• 隊(duì)列接口

// 初始化隊(duì)列
void QueueInit(Queue* q); 
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data); 
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q); 
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q); 
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q); 
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q); 
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* q); 
// 銷毀隊(duì)列
void QueueDestroy(Queue* q);

• 在VS2022中新建一個(gè)工程

Queue20250310.h（隊(duì)列的類型定義、接口函數(shù)聲明、引用的頭文件）
Queue20250310.c（隊(duì)列的接口函數(shù)的實(shí)現(xiàn)）
QueueTest20250310.c（主函數(shù)、測(cè)試各個(gè)接口功能）

2.2.1 初始化隊(duì)列

// 初始化隊(duì)列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;// 初始化隊(duì)列的頭指針和尾指針為NULpq->size = 0; // 初始化隊(duì)列的大小為0
}

2.2.2 銷毀隊(duì)列

// 銷毀隊(duì)列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;// 定義一個(gè)指針指向隊(duì)列的頭節(jié)點(diǎn)while (cur)//遍歷隊(duì)列{QNode* next = cur->next;//找到當(dāng)前節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)free(cur);cur = next;//繼續(xù)往后走}pq->head = pq->tail = NULL;// 將隊(duì)列的頭指針和尾指針置為NULpq->size = 0;//將隊(duì)列的大小置為0
}

2.2.3 隊(duì)尾入隊(duì)列

// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueueDestroy::malloc fail!");return;}newnode->data = data;// 將數(shù)據(jù)存入新節(jié)點(diǎn)newnode->next = NULL;// 將新節(jié)點(diǎn)的指針域置為NULLif (pq->head == NULL)// 如果隊(duì)列為空，則新節(jié)點(diǎn)即為隊(duì)列的頭指針和尾指針{assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else //如果隊(duì)列不為空，則將新節(jié)點(diǎn)插入到隊(duì)列的尾部{//尾插pq->tail->next = newnode;pq->tail = newnode;}pq->size++;// 隊(duì)列的大小加1
}

2.2.4 隊(duì)頭出隊(duì)列

// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head==NULL);QNode* next = pq->head->next;                                                                                                                                                                                                                                                          free(pq->head); // 釋放原頭節(jié)點(diǎn)的內(nèi)存空間pq->head = next;if (pq->head == NULL)// 如果隊(duì)列為空，則將尾指針也置為NULLpq->tail = NULL;pq->size--;
}

2.2.5獲取隊(duì)列頭部元素

// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

2.2.6 獲取隊(duì)列隊(duì)尾元素

// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

2.2.7獲取隊(duì)列中有效元素個(gè)數(shù)

// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.2.8 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0

// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;// 如果隊(duì)列的頭指針為NULL，則隊(duì)列為空
}

3.棧和隊(duì)列面試題

3.1 括號(hào)匹配問(wèn)題。

括號(hào)匹配問(wèn)題

3.2用隊(duì)列實(shí)現(xiàn)棧。

用隊(duì)列實(shí)現(xiàn)棧

3.3 用棧實(shí)現(xiàn)隊(duì)列。

3.4 設(shè)計(jì)循環(huán)隊(duì)列。