隊(duì)列

與棧不同，他就是現(xiàn)實(shí)中排隊(duì)一樣，講究先來(lái)后到，即 先進(jìn)先出。

相關(guān)定義

• 隊(duì)列：它是一種操作受限的線(xiàn)性表，其限制在表的一端進(jìn)行插入，另一端進(jìn)行刪除。
• 對(duì)尾、對(duì)頭：可進(jìn)行插入的一端稱(chēng)為隊(duì)尾（rear）,可進(jìn)行刪除的一端稱(chēng)為隊(duì)頭（front）
• 入隊(duì)、出隊(duì)：向隊(duì)中插入元素叫入隊(duì)，新元素進(jìn)入之后就稱(chēng)為新的隊(duì)尾元素。從隊(duì)中刪除元素叫出隊(duì)，元素出隊(duì)后，其后繼結(jié)點(diǎn)元素就稱(chēng)為新的隊(duì)頭元素。

隊(duì)列的兩種存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。 我們今天先講一講隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)——循環(huán)隊(duì)列

為什么要有循環(huán)隊(duì)列的設(shè)計(jì) - 假溢出

image.png

假設(shè)開(kāi)辟一個(gè)存儲(chǔ)大小為5個(gè)內(nèi)存單元的隊(duì)列
我列舉了四種狀態(tài) ：空隊(duì)列，入隊(duì)，入隊(duì)到隊(duì)滿(mǎn)，刪除只剩一個(gè)元素。
先看前三種：當(dāng)為空隊(duì)列時(shí)，front和rear都指向了同一個(gè)元素，判為空；當(dāng)入隊(duì)時(shí)，rear向后移動(dòng)，指向新元素，當(dāng)出隊(duì)時(shí)，front指向下一個(gè)元素；當(dāng)front=0，rear=4時(shí)，整隊(duì)滿(mǎn)，操作貌似沒(méi)有問(wèn)題。這一切看似完美。
但是，，，如果如下圖，出隊(duì)到只剩最后一個(gè)元素，front和rear又都指向了一個(gè)同元素，而且僅在隊(duì)尾，又要認(rèn)為隊(duì)列為空？不可能啊，明明最后一塊存儲(chǔ)單元還有一個(gè)元素，而且卻不能繼續(xù)入隊(duì)新元素，超出了存儲(chǔ)范圍，如果要繼續(xù)利用前面出隊(duì)的空余空間，又該怎么用？

image.png

因此需要設(shè)計(jì)成循環(huán)結(jié)構(gòu)來(lái)解決這個(gè)問(wèn)題

image.png

• 如圖(b)所示，a先入隊(duì) b再入隊(duì) C再入隊(duì) ，rear指向C后面的位置。
• 如圖(c)所示，隊(duì)首元素a出隊(duì)，front指向下一個(gè)隊(duì)首b，但是此時(shí)front=1，而不再是從0開(kāi)始，一邊出隊(duì)一邊入隊(duì)，那么front的位置就會(huì)是0，1，2，3，4，5 然后利用取模運(yùn)算front = (front+1) % max,front又回到0，然后1。。。。。 使得每次front的位置可以在隊(duì)尾之后繼續(xù)回到標(biāo)號(hào)從0的位置繼續(xù)往后走，周期循環(huán)。同理，rear，新增到rear = 5時(shí)，也利用取模運(yùn)算，新的數(shù)據(jù)從標(biāo)號(hào)為0開(kāi)始繼續(xù)入隊(duì)，實(shí)現(xiàn)循環(huán)隊(duì)列。

• 如果隊(duì)滿(mǎn)是什么樣，看下圖

  
  
  image.png

rear指向的下一個(gè)位置是隊(duì)首front的b，還是和之前一樣，front==rear， 但是我們已經(jīng)用循環(huán)解決當(dāng)只有最后一塊存儲(chǔ)單元有元素而不能再繼續(xù)入隊(duì)的問(wèn)題。
無(wú)礙,我們可以犧牲一個(gè)front前的存儲(chǔ)單元，用來(lái)保持隊(duì)尾和隊(duì)首的距離，來(lái)解決最后一個(gè)問(wèn)題：判斷隊(duì)滿(mǎn)，(Q.rear+1) % Q.max == Q.front ， 如果條件成立，意味著空的下一個(gè)位置就是隊(duì)首front，此時(shí)隊(duì)已滿(mǎn)

image.png

這就是循環(huán)隊(duì)列的工作流程

循環(huán)隊(duì)列

將上面的過(guò)程做一下整理：

• 當(dāng)初始化隊(duì)列為空時(shí)，front = rear = 0；
• 入隊(duì)，rear+1，指向隊(duì)尾的下一個(gè)存儲(chǔ)單元，為了實(shí)現(xiàn)循環(huán)利用取模運(yùn)算：rear = (rear+1) % max;
• 出隊(duì)，front+1，指向下一個(gè)隊(duì)首，實(shí)現(xiàn)循環(huán)：front = (front+1) % max;
• 判斷隊(duì)滿(mǎn)，(Q.rear+1) % Q.max == Q.front

循環(huán)隊(duì)列相關(guān)操作

• 定義

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;/* Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類(lèi)型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

/* 隊(duì)列結(jié)構(gòu) */
typedef struct
{
    ElemType *data;
    int front;  /* 記錄隊(duì)首元素位置 */
    int rear;   /* 記錄對(duì)尾元素位置 */
    int max;    /* 記錄開(kāi)辟內(nèi)存空間的大小 */
}SqQueue;

• 初始化

/// 初始化創(chuàng)建隊(duì)列
/// @param Q 隊(duì)列指針
/// @param n 指定開(kāi)辟空間大小，一個(gè)空間大小是 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;
}

• 獲得元素個(gè)數(shù)

/// 獲取隊(duì)列元素個(gè)數(shù)(包括rear指向的空位置)
/// @param Q 隊(duì)列
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;
}

• 隊(duì)滿(mǎn)

Status QueueFull(SqQueue Q)
{
    if ((Q.rear+1) % Q.max == Q.front)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}

• 獲得隊(duì)首元素

Status GetFront(SqQueue Q, ElemType *e)
{
    if (QueueEmpty(Q) == OK) {
        return ERROR;
    }
    
    *e = Q.data[Q.front];
    return OK;
}

• 入隊(duì)

/// 入隊(duì)操作
/// @param Q 隊(duì)列
/// @param e 新數(shù)據(jù)
Status EnQueue(SqQueue *Q, ElemType e)
{
    // 判斷隊(duì)列有沒(méi)有滿(mǎn)
    if (QueueFull(*Q)) return ERROR;
    
    Q->data[Q->rear] = e;
    // 隊(duì)尾向后移動(dòng)，取模運(yùn)算，超出隊(duì)尾，實(shí)現(xiàn)循環(huán)繼續(xù)從隊(duì)首開(kāi)始
    Q->rear = (Q->rear+1) % Q->max;
    
    return OK;
}

• 出隊(duì)

/// 出隊(duì)列
/// @param Q 隊(duì)列
/// @param e 出的元素
Status DeQueue(SqQueue *Q, ElemType *e)
{
    // 判斷對(duì)了是不是空
    if (QueueEmpty(*Q) == OK) return ERROR;
    
    *e = Q->data[Q->front];
    // 隊(duì)首位置向后移動(dòng)一位
    Q->front = (Q->front+1) % Q->max;
    
    return OK;
}

• 遍歷輸出

Status QueuePrint(SqQueue *Q)
{
    /* 從隊(duì)首開(kāi)時(shí)輸出，直到對(duì)尾 */
    int i = Q->front;
    while (i != Q->rear) {
        printf("%d ",Q->data[i]);
        i = (i+1) % Q->max;
    }
    printf("\n");
    
    return ERROR;
}