隊列
與棧不同狸臣，他就是現(xiàn)實中排隊一樣，講究先來后到粉寞，即 先進(jìn)先出尼荆。
打個比方，你告訴朋友我們做地鐵去西湖唧垦，你輸入 "s-u-b", 如果按照棧 先入后出后入先出 的方式捅儒，朋友會收到 b-u-s, what？有地鐵振亮，我們干嘛做兩個小時的汽車巧还？？坊秸？ 隊列就可以讓朋友按你輸入的順序依次收到 s-u-b 麸祷。
簡單的看一下隊列，是線性結(jié)構(gòu)褒搔，想到什么阶牍？非常熟悉的 線性表 喷面，有兩種存儲結(jié)構(gòu)，順序存儲和鏈?zhǔn)酱鎯?/strong>荸恕。
我們今天先講一講隊列的順序存儲結(jié)構(gòu)——循環(huán)隊列
先看一種隊列
image
假設(shè)開辟一個存儲大小為5個內(nèi)存單元的隊列
我列舉了四種狀態(tài) ：空隊列乖酬，入隊死相，入隊到隊滿融求，刪除只剩一個元素。
先看前三種：當(dāng)為空隊列時算撮，front和rear都指向了同一個元素生宛，判為空；當(dāng)入隊時肮柜，rear向后移動陷舅，指向新元素，當(dāng)出隊時审洞，front指向下一個元素莱睁；當(dāng)front=0，rear=4時芒澜，整隊滿仰剿，操作貌似沒有問題。這一切看似完美痴晦。
但是南吮，，誊酌，如果如下圖部凑，出隊到只剩最后一個元素，front和rear又都指向了一個同元素碧浊，而且僅在隊尾涂邀，又要認(rèn)為隊列為空？不可能啊箱锐，明明最后一塊存儲單元還有一個元素比勉，而且卻不能繼續(xù)入隊新元素，超出了存儲范圍瑞躺，如果要繼續(xù)利用前面出隊的空余空間敷搪，又該怎么用？
image
如果 我們把隊列設(shè)計成下面這樣：
image
哈哈幢哨，循環(huán)了赡勘。隊尾rear指向下一個位置，而不是當(dāng)前的隊尾元素捞镰。
- 如圖(b)所示闸与，a先入隊 b再入隊 C再入隊 毙替，rear指向C后面的位置。
- 如圖(c)所示践樱，隊首元素a出隊厂画，front指向下一個隊首b，但是此時front=1拷邢，而不再是從0開始袱院，一邊出隊一邊入隊，那么front的位置就會是0瞭稼，1忽洛，2，3环肘，4欲虚，5 然后利用取模運算front = (front+1) % max,front又回到0，然后1悔雹。复哆。。腌零。梯找。 使得每次front的位置可以在隊尾之后繼續(xù)回到標(biāo)號從0的位置繼續(xù)往后走，周期循環(huán)莱没。同理初肉，rear，新增到rear = 5時饰躲，也利用取模運算牙咏，新的數(shù)據(jù)從標(biāo)號為0開始繼續(xù)入隊，實現(xiàn)循環(huán)隊列嘹裂。
- 如果隊滿是什么樣妄壶，看下圖
image
????? rear指向的下一個位置是隊首front的b，哇寄狼，還是和之前一樣丁寄，front==rear， 但是我們已經(jīng)用循環(huán)解決當(dāng)只有最后一塊存儲單元有元素而不能再繼續(xù)入隊的問題泊愧。
無礙,我們可以犧牲一個front前的存儲單元伊磺，用來保持隊尾和隊首的距離，來解決最后一個問題：判斷隊滿删咱，(Q.rear+1) % Q.max == Q.front 屑埋， 如果條件成立，意味著空的下一個位置就是隊首front痰滋，此時隊已滿
image
這就是循環(huán)隊列的工作流程
循環(huán)隊列
將上面的過程做一下整理：
- 當(dāng)初始化隊列為空時摘能，front = rear = 0续崖；
- 入隊，rear+1团搞，指向隊尾的下一個存儲單元严望，為了實現(xiàn)循環(huán)利用取模運算：rear = (rear+1) % max;
- 出隊，front+1逻恐，指向下一個隊首像吻，實現(xiàn)循環(huán)：front = (front+1) % max;
- 判斷隊滿，(Q.rear+1) % Q.max == Q.front
定義
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼梢莽，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實際情況而定萧豆，這里假設(shè)為int */
/* 隊列結(jié)構(gòu) */
typedef struct
{
ElemType *data;
int front; /* 記錄隊首元素位置 */
int rear; /* 記錄對尾元素位置 */
int max; /* 記錄開辟內(nèi)存空間的大小 */
}SqQueue;
初始化創(chuàng)建隊列
/// 初始化創(chuàng)建隊列
/// @param Q 隊列指針
/// @param n 指定開辟空間大小奸披，一個空間大小是 sizeof(ElemType)
Status InitQueue(SqQueue *Q, int n)
{
Q->data = malloc(sizeof(ElemType) * n);
if (Q->data == NULL) return ERROR;
Q->max = n;
Q->front = Q->rear = 0;
return OK;
}
獲得元素個數(shù)
/// 獲取隊列元素個數(shù)(包括rear指向的空位置)
/// @param Q 隊列
int GetLength(SqQueue Q)
{
return (Q.rear - Q.front + Q.max) % Q.max;
}
判斷是不是空
Status QueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear) {
return OK;
}
return ERROR;
}
隊滿
Status QueueFull(SqQueue Q)
{
if ((Q.rear+1) % Q.max == Q.front)
{
return OK;
}
else
{
return ERROR;
}
}
獲得隊首元素
Status GetFront(SqQueue Q, ElemType *e)
{
if (QueueEmpty(Q) == OK) {
return ERROR;
}
*e = Q.data[Q.front];
return OK;
}
入隊
/// 入隊操作
/// @param Q 隊列
/// @param e 新數(shù)據(jù)
Status EnQueue(SqQueue *Q, ElemType e)
{
// 判斷隊列有沒有滿
if (QueueFull(*Q)) return ERROR;
Q->data[Q->rear] = e;
// 隊尾向后移動昏名，取模運算，超出隊尾阵面，實現(xiàn)循環(huán)繼續(xù)從隊首開始
Q->rear = (Q->rear+1) % Q->max;
return OK;
}
出隊
/// 出隊列
/// @param Q 隊列
/// @param e 出的元素
Status DeQueue(SqQueue *Q, ElemType *e)
{
// 判斷對了是不是空
if (QueueEmpty(*Q) == OK) return ERROR;
*e = Q->data[Q->front];
// 隊首位置向后移動一位
Q->front = (Q->front+1) % Q->max;
return OK;
}
遍歷輸出
Status QueuePrint(SqQueue *Q)
{
/* 從隊首開時輸出轻局，直到對尾 */
int i = Q->front;
while (i != Q->rear) {
printf("%d ",Q->data[i]);
i = (i+1) % Q->max;
}
printf("\n");
return ERROR;
}
測試輸出
指定隊列最大存儲5個單元，方便觀看
int main(int argc, const char * argv[]) {
SqQueue queue;
InitQueue(&queue, 5);
printf("插入數(shù)據(jù):");
for (int i = 0; i < 30; i++) {
EnQueue(&queue, i);
}
QueuePrint(&queue);
int e ;
printf("出隊:");
if (DeQueue(&queue, &e))
{
QueuePrint(&queue);
}
if (DeQueue(&queue, &e))
{
QueuePrint(&queue);
}
int frontE;
if (GetFront(queue, &frontE)) {
printf("隊頭：%d\n",frontE);
}
printf("插入數(shù)據(jù):");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入數(shù)據(jù):");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入數(shù)據(jù):");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入數(shù)據(jù):");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("開始清空隊列\(zhòng)n");
ClearQueue(&queue);
QueuePrint(&queue);
DestoryQueue(&queue);
return 0;
}
image
