1.定義
隊(duì)列(queue)是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表疫剃。
- 與棧相反钉疫，隊(duì)列是一種先進(jìn)先出(First In First Out,FIFO)的線性表
- 與棧相同的是，隊(duì)列也是一種重要的線性結(jié)構(gòu)巢价，實(shí)現(xiàn)一個(gè)隊(duì)列同樣需要順序表或鏈表作為基礎(chǔ)
隊(duì)列
2.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
隊(duì)列既可以用鏈表實(shí)現(xiàn)牲阁，也可以用順序表實(shí)現(xiàn)。跟棧相反的是壤躲，棧一般我們用順序表來實(shí)現(xiàn)城菊，而隊(duì)列我們常用鏈表來實(shí)現(xiàn)，簡(jiǎn)稱為鏈隊(duì)列
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue{
QueuePtr front,rear;//隊(duì)頭碉克、尾指針
}LinkQueue;
我們將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn),而隊(duì)尾指針指向終端結(jié)點(diǎn)凌唬。(注:頭結(jié)點(diǎn)不是必要的，但我們加上后操作更方便)
隊(duì)列
空隊(duì)列時(shí)漏麦，front和rear都指向頭結(jié)點(diǎn)
空隊(duì)列
(1)創(chuàng)建一個(gè)隊(duì)列
創(chuàng)建一個(gè)隊(duì)列要完成兩個(gè)任務(wù)：
- 創(chuàng)建頭結(jié)點(diǎn)
- 將隊(duì)列的頭指針和尾指針都指向頭結(jié)點(diǎn)客税，生成空隊(duì)列
Status initQueue(LinkQueue *q){
q->front = (QueuePtr)malloc(sizeof(QNode));
if (!q->front) {
return ERROR;
}
q->rear = q->front;
q->rear->next = NULL;
return OK;
}
(2) 入隊(duì)列操作
入隊(duì)列操作
如圖所示，入隊(duì)列就是在隊(duì)尾插入一個(gè)新的結(jié)點(diǎn)
Status insertQueue(LinkQueue *q,ElemType e){
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) {
return ERROR;
}
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
return OK;
}
(3)出隊(duì)列操作
出隊(duì)列操作是將隊(duì)列中的第一個(gè)元素移出撕贞，隊(duì)頭指針不發(fā)生改變更耻，改變頭結(jié)點(diǎn)的next指針即可
出隊(duì)列操作
如果原隊(duì)列只有一個(gè)元素，那么我們就應(yīng)該處理一下隊(duì)尾指針麻掸，讓它指向頭結(jié)點(diǎn)
處理一個(gè)元素的情況
Status deleteQueue(LinkQueue *q,ElemType *e){
if (q->rear == q->front) {
//隊(duì)尾和隊(duì)頭指向相同酥夭，表示空隊(duì)列
return ERROR;
}
QueuePtr p = q->front->next;
//返回值
*e = p->data;
//頭結(jié)點(diǎn)指向下一個(gè)元素
q->front->next = p->next;
if (q->rear == p) {
//只有一個(gè)元素的隊(duì)列
q->rear = q->front;
}
free(p);
return OK;
}
(4)銷毀一個(gè)隊(duì)列
由于鏈隊(duì)列建立在內(nèi)存的動(dòng)態(tài)區(qū)，因此當(dāng)一個(gè)隊(duì)列不再有用時(shí)應(yīng)當(dāng)把它及時(shí)銷毀掉脊奋，以免過多的占用內(nèi)存空間
Status destroyQueue(LinkQueue *q){
while (q->front) {
QueuePtr p = q->front;
q->front = q->front->next;
free(p);
}
q->front = q->rear = NULL;
return OK;
}
