?? 作者簡介：一名在后端領域學習，并渴望能夠學有所成的追夢人。
?? 個人主頁：蝸牛牛啊
?? 系列專欄：??數(shù)據(jù)結構、??C++
?? 學習格言：博觀而約取，厚積而薄發(fā)
?? 歡迎進來的小伙伴，如果小伙伴們在學習的過程中，發(fā)現(xiàn)有需要糾正的地方，煩請指正，希望能夠與諸君一同成長！ ??

循環(huán)隊列

隊列又稱為"先進先出（FIFO）"線性表：插入操作只能在隊尾進行，刪除操作只能在隊首進行。

而循環(huán)隊列是隊列的一種特殊形式，循環(huán)隊列（也被稱為環(huán)形隊列）是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于先進先出原則，并且隊尾被連接在隊首之后以形成一個循環(huán)。

循環(huán)隊列固定大小，空間能夠重復利用。

循環(huán)隊列可以用數(shù)組或者鏈表實現(xiàn)，那下面我們來分析一下哪種方式更好：

當我們想使用鏈表實現(xiàn)時，假設我們想要開辟的隊列長度為k = 4；front表示隊頭指針，rear表示隊尾指針：

由上圖可知，當rear和front 都指向同一個位置時隊列為空。

插入一個數(shù)據(jù)之后：

rear向后移動，此時我們知道rear指向的位置是最后一個數(shù)據(jù)的下一個位置。

那當我們一直插入數(shù)據(jù)，直至隊列為滿：

但是當隊列滿的時候，我們發(fā)現(xiàn)rear 和 front也指向同一個位置。那當隊列為空和隊列為滿的時候，rear和front都指向同一個位置，我們怎么判斷此時隊列是滿還是空？

通過判斷front和rear是否為空可以嗎？不行，front和rear剛開始都會指向節(jié)點，不會為空。

解決方法：1.增加一個size或者flag解決；2.增加一個空余節(jié)點。

我們可以多開一個節(jié)點，不是哨兵位節(jié)點，和頭節(jié)點一樣，此時：

隊列為空時：

隊列滿時：

滿的時候不能再插入數(shù)據(jù)，現(xiàn)在假設我們刪除兩個數(shù)據(jù)：

再插入兩個數(shù)據(jù)：

如果我們不斷pop，當rear和front指向同一個位置時，隊列就變?yōu)榭樟恕?/p>

那我們可以用單鏈表來實現(xiàn)循環(huán)隊列嗎？使用鏈表最不好解決的一個問題就是取隊尾數(shù)據(jù)，單鏈表不容易取當前節(jié)點的前一個結點數(shù)據(jù)，我們可以通過增加一個指針rear->prev指向前一個結點。

當我們想使用數(shù)組實現(xiàn)時，假設我們想要開辟的隊列長度為k = 4；front表示隊頭的下標，rear表示隊尾的下標：

使用數(shù)組實現(xiàn)同樣也面臨著front和rear相等時無法判斷隊列是空還是滿的問題，所以我們也可以通過增加一個size或者多開辟一個空間來解決該問題。

當我們插入一個數(shù)據(jù)后發(fā)現(xiàn)rear指向隊尾數(shù)據(jù)的下一個位置，在鏈表中存在的找隊尾問題，在這里找隊尾數(shù)據(jù)變得簡單。

當隊列為空時下標front == rear：

當隊列滿時可以通過公式(rear + 1) % (k + 1) == front來判斷隊列是否滿了：

插入數(shù)據(jù)在rear++之后可以通過rear % （k + 1）來計算插入數(shù)據(jù)之后rear的下標：

刪除數(shù)據(jù)可以在front++之后通過front % (k + 1)得出刪除數(shù)據(jù)之后front的下標：

練習：現(xiàn)有一循環(huán)隊列，其隊頭指針為front，隊尾指針為rear；循環(huán)隊列長度為N。其隊內有效長度為 ？

A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)

假設隊列如下圖所示：

隊內有效長度為2，兩個指針相減得到的是兩個指針之間的元素個數(shù)(rear - front) = 2；上面的四個選項中代入計算只有B符合要求。

設計循環(huán)隊列

題目：設計循環(huán)隊列

設計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。

循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。

你的實現(xiàn)應該支持如下操作：

• MyCircularQueue(k): 構造器，設置隊列長度為 k 。
• Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
• Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
• enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
• deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
• isEmpty(): 檢查循環(huán)隊列是否為空。
• isFull(): 檢查循環(huán)隊列是否已滿。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 設置長度為 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，隊列已滿
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示：

• 所有的值都在 0 至 1000 的范圍內；
• 操作數(shù)將在 1 至 1000 的范圍內；
• 請不要使用內置的隊列庫。

思路：

可以使用數(shù)組的方式實現(xiàn)循環(huán)隊列，在結構體中定義一個一級指針int* arr、隊頭下標front、隊尾下標rear以及要開辟的隊列長度k；然后通過開辟空間及上面關于循環(huán)隊列的知識完成循環(huán)隊列的設計。

注：下面提供的代碼第一個是通過if來計算插入時rear下標和刪除時front下標的，第二個是通過公式計算的。

代碼1：

typedef struct {
    int* arr; //用來指向空間的指針
    int front;//隊頭下標
    int rear;//隊尾下標
    int k;//隊列長度
} MyCircularQueue;

構造器，設置隊列長度為 k
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* r = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申請一個結構體指針
    int* tmp = (int*)malloc(sizeof(int) * (k + 1));//多開一個空間
    if(tmp == NULL)
    {
        perror("malloc");
        exit(0);
    }
    r->arr = tmp;//給指針賦值
    r->front = 0;//設置隊頭下標
    r->rear = 0;//設置隊尾下標
    r->k = k;//隊列長度
    return r;
}

//檢查循環(huán)隊列是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->rear == obj->front)//相等時為空
        return true;
    return false;
}
// 檢查循環(huán)隊列是否已滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear + 1)%( obj->k + 1) == obj->front)
        return true;
    return false;
}
//向循環(huán)隊列插入一個元素。如果成功插入則返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//隊列滿時不能再插入
        return false;
    obj->arr[obj->rear++] = value;//插入數(shù)據(jù)
    if(obj->rear > obj->k)//計算rear下標
    {
        obj->rear = 0;
    }
    return true;
}
//從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//為空時不能刪除
        return false;
    obj->front++;
    if(obj->front > obj->k)//計算front下標
    {
        obj->front = 0;
    }
    return true;

}
//從隊首獲取元素。如果隊列為空，返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}
//獲取隊尾元素。如果隊列為空，返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    int n = obj->rear-1;
    if(n < 0)
    {
        n = obj->k;
    }
    return obj->arr[n];
}
//釋放空間
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}

代碼2：文章來源地址http://www.zghlxwxcb.cn/news/detail-533210.html

typedef struct {
    int* arr; //用來指向空間的指針
    int front;//隊頭下標
    int rear;//隊尾下標
    int k;//隊列長度
} MyCircularQueue;
//構造器，設置隊列長度為 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申請一個結構體指針
    obj->arr=(int*)malloc(sizeof(int)*(k+1));//開辟k+1個int空間用來存儲數(shù)據(jù)，要多開辟一個
    obj->k=k;//隊列長度
    obj->front = obj->rear = 0;
    return obj;
}
//檢查循環(huán)隊列是否為空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front == obj->rear; //相等時為空
}
// 檢查循環(huán)隊列是否已滿。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return ((obj->rear+1)%(obj->k+1) == obj->front);
}

//向循環(huán)隊列插入一個元素。如果成功插入則返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))//隊列滿時不能再插入
        return false;
    obj->arr[obj->rear++] = value;//插入數(shù)據(jù)
    obj->rear = obj->rear%(obj->k+1);//計算rear下標
    return true;
}
//從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))//為空時不能刪除
        return false;
    obj->front++;
    obj->front = obj->front % (obj->k+1);//計算front下標
    return true;
}
//從隊首獲取元素。如果隊列為空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}
//獲取隊尾元素。如果隊列為空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[(obj->rear+obj->k)%(obj->k+1)];
} 

//釋放空間
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}

到了這里，關于【數(shù)據(jù)結構】循環(huán)隊列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！