一吱七、隊列的定義
【定義】：隊列(queue)是只允許在一端進(jìn)行插入操作埋心，而在另一端進(jìn)行刪除操作的線性表。
【特征】：先進(jìn)先出(First In First Out，簡稱FIFO)的線性表（與棧相反）迫肖。允許插入的一端稱為隊尾锅劝，允許刪除的一端稱為隊頭。
【應(yīng)用】：隊列在程序設(shè)計中使用非常頻繁蟆湖。比如實現(xiàn)鍵盤進(jìn)行各種字母或數(shù)字的輸入故爵，到顯示器上的輸出等先進(jìn)先出功能。
二帐姻、隊列的順序存儲結(jié)構(gòu)
線性表有順序存儲和鏈?zhǔn)酱鎯Τ砑瑮：完犃幸彩蔷€性表，所以也存在這兩種存儲方式饥瓷。
隊列的順序存儲的不足
隊列元素的出隊在隊頭剥纷，即下標(biāo)為0的位置，也就意味著呢铆，隊列中的所有元素都得向前一定晦鞋，以保證隊列的隊頭位置不為空，時間復(fù)雜度為O(n).
并且隊列的順序存儲結(jié)構(gòu)還會帶來假溢出等問題棺克。
多以引入了循環(huán)隊列
循環(huán)隊列
循環(huán)隊列就是隊列的頭尾相接悠垛，屬于順序存儲結(jié)構(gòu)。
循環(huán)隊列中的幾個特點(diǎn)：
- 隊空的判斷條件：
front == rear; - 設(shè)隊列的最大存儲空間為
MAXSIZE,入隊操作是娜谊，rear需要加1后移一位确买，賦值語句為：rear = (rear + 1) % MAXSIZE,出隊操作，front加1后移的賦值語句：front = (front + 1) % MAXSIZE
完整代碼：
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int QElemType;
typedef struct {
QElemType data[MAXSIZE]; //用于存放分配的基地址
int front; // 頭指針
int rear; // 尾指針
}SqQueue;
/**
* 1.初始化隊列
*/
Status InitQueue(SqQueue * Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
/**
* 2.獲取隊列長度
*/
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
/**
* 3.入棧操作
*/
Status InsertQueue(SqQueue * Q, QElemType e){
if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR; // 隊滿
Q->data[Q->rear] = e; // 將元素e賦值給隊尾
Q->rear = (Q->rear + 1) % MAXSIZE; //rear指針后移一個位置
return OK;
}
/**
* 4.出棧操作
*/
Status DeleteQueue(SqQueue * Q, QElemType *e){
if (Q->front == Q->rear) return ERROR; // 隊空
*e = Q->data[Q->front]; // 將對頭元素賦值給e
Q->front = (Q->front + 1) % MAXSIZE; // front指針后移一個位置
return OK;
}
三纱皆、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)(鏈隊列)
隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)湾趾，其實就是線性表的單鏈表，只不過它只能尾進(jìn)頭出而已派草，簡稱鏈隊列搀缠。
1.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)定義
代碼實現(xiàn)
typedef int Status;
typedef int QElemType;
typedef struct QNode{ /* 結(jié)點(diǎn)結(jié)構(gòu) */
QElemType data;
struct QNode * next;
}QNode, *QueuePrt;
typedef struct { /* 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) */
QueuePrt front,rear; // 隊頭、隊尾指針
}LinkQueue;
隊頭指針指向鏈隊列的頭結(jié)點(diǎn)近迁，尾指針指向終端結(jié)點(diǎn)艺普。（頭結(jié)點(diǎn)不是必要的，但是加上了可以方便操作）
空隊列：front和rear都指向頭結(jié)點(diǎn)鉴竭。
2.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) - 創(chuàng)建一個隊列
步驟：
- 在內(nèi)存中創(chuàng)建一個頭結(jié)點(diǎn)歧譬。
- 將隊列的頭指針和尾指針都指向這個生成的頭結(jié)點(diǎn)。（因為此時為空隊列）
代碼實現(xiàn)：
/**
* 鏈隊列的創(chuàng)建
*/
Status InitQueue(LinkQueue * Q){
Q->front = Q->rear = (QueuePrt)malloc(sizeof(QNode));
if (!Q->front) exit(0);
Q->front->next = NULL;
return OK;
}
3.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) - 插入操作
入隊操作搏存，其實就是在鏈表尾部插入結(jié)點(diǎn)缴罗。
代碼實現(xiàn)：
/**
* 入隊操作
*/
Status InsertQueue(LinkQueue * Q, QElemType e){
QueuePrt s = (QueuePrt)malloc(sizeof(QNode));
if (!s) exit(0); // 存儲分配失敗
s->data = e;
s->next = NULL;
Q->rear->next = s; // 把擁有元素e的新節(jié)點(diǎn)賦值給原隊尾結(jié)點(diǎn)的后繼
Q->rear = s; // 把當(dāng)前s設(shè)置成隊尾結(jié)點(diǎn)，rear指向s
return OK;
}
4.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) - 出隊操作
出隊操作是將隊列中的第一個元素移出祭埂，隊頭指針不發(fā)生改變面氓，改變頭結(jié)點(diǎn)的next指針即可兵钮。
代碼：
/**
* 出隊操作
*/
Status DeleteQueue(LinkQueue * Q, QElemType *e){
QueuePrt p;
if (Q->front == Q->rear) return ERROR; // 空隊列
p = Q->front->next; // 將欲刪除的隊頭結(jié)點(diǎn)暫存給p
*e = p->data; // 將欲刪除的隊頭結(jié)點(diǎn)賦值給e
Q->front->next = p->next; // 將原隊頭結(jié)點(diǎn)后繼p->next賦值給頭結(jié)點(diǎn)后繼
if (Q->rear == p) { // 若隊列只有一個元素，則刪除后將rear指向頭結(jié)點(diǎn)
Q->rear = Q->front;
}
free(p);
return OK;
}
5.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) - 銷毀隊列
由于鏈度列建立在內(nèi)存的動態(tài)區(qū)舌界，因此當(dāng)一個隊列不再有用的時候掘譬，應(yīng)該把它及時銷毀掉，以免過多的占用內(nèi)存空間呻拌。
/**
* 銷毀隊列
*/
Status DestoryQueue(LinkQueue * Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
