循環隊列詳解！！c 語言版本（兩種方法）雙向鏈表和數組法！！

1.什么是循環隊列

2.循環隊列的實現（兩種方法）

第一種方法數組法

1.源代碼

2.源代碼詳解！！

1.創造隊列空間和struct變量

2.隊列判空

3.隊列判滿（重點）

4.隊列的元素插入

5.隊列的元素刪除

6.隊列的頭元素

7.隊列的尾元素（重點）

8.隊列空間的釋放

第二種方法雙向循環鏈表法

1.源代碼

2.源代碼詳解！！

?1.創造哨兵位和 struct 變量

2. 隊列判空和隊列判滿

3.元素插入

4.元素刪除

5.頭元素

6.尾元素

7.空間的釋放

三關于這兩種方法的差距?

3.循環隊列有什么用

1.什么是循環隊列

首先關于循環隊列，你得先知道什么是隊列，詳情可以去看看我的另一篇博客

數據結構棧與隊列詳解！！-CSDN博客

這里簡單的說一下，隊列就是字面意思，你在銀行排隊，你不是什么VIP只是普通人，那你先排隊那你就先得服務，隊列就是你先插入的數字（入隊），就得先放出（出隊）。大致就是這個意思。

而循環隊列呢？他的原理也是隊列，但和隊列不同的地方在于，他的空間是固定的。在一個空間里進行重復的入隊出隊。

這是一張循環隊列的大致圖。

其中和隊列一樣有兩個指針指向頭和尾。添加實在尾針處加，而刪除就是將隊首的元素刪除。為什么循環呢？就是在你的尾指針走到最后一格的時候（就是總共有5個空間，你的尾指針已經走到5并且已經插入數據）你的隊列就滿了，這時候循環隊列已經不能插入數據，只能刪除數據。

刪除數據就是把你的頭指針的元素刪除，如果刪除走到尾指針，頭和尾在一個位置了。

所以綜上可以抽象出，當你的頭和尾指針走到一起的時候，這時候隊列是空。

但你的尾走到底頭元素的上一個，那就說明你的隊列已充滿。

當隊尾追到了隊頭那就是滿，當隊頭追到了隊尾那就是空

2.循環隊列的實現（兩種方法）

第一種方法數組法

數組法采用的是多開辟一個空間，用來做假溢出，判斷隊列是否充滿，當然還有一種定size法，大家可以討論一下！！

1.源代碼

typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->k = k;obj->front = 0;obj->rear = 0;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->rear %= obj->k + 1;obj->a[obj->rear] = value;obj->rear++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj->front %= obj->k + 1;obj->front++;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->rear - 1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a = NULL;free(obj);obj = NULL;
}

2.源代碼詳解！！

1.創造隊列空間和struct變量

typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (k + 1));obj->k = k;obj->front = 0;obj->rear = 0;return obj;
}

?關于匿名typedef struc 就是定義了一個類型名就叫做MyCircularQueue。

里面的元素第一個用來開辟空間，第二個定義頭指針，第三個定義尾指針，第4個就是空間的大小。（這里的指針并不是真的指針，而是對于一個數組來說的下標）

關于創造隊列的空間，首先既然他是一個結構體變量，那得先給他開辟一個空間用來給里面的元素地址存儲

第二因為你是要在一個數組里進行循環隊列，那你就得開辟一塊數組的空間。（k+1是因為這里采用的是多開辟一格進行判滿）。

第三給結構體里的變量賦初始值。?

2.隊列判空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}

?關于隊列的判空，就是兩個隊頭和隊尾指針如果重疊時，兩者應該是滿了或者空了的關系，所以兩者的判斷表達式不能相同，所以下面的判滿得想到另一個表達式才能保證隊列不報錯（當隊尾追到了隊頭那就是滿，當隊頭追到了隊尾那就是空）

3.隊列判滿（重點）

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

?這里關于隊列的判滿，采用的是這一串表達式的原因是，假設這時你開辟的有元素的空間是3，那現在的K就是3，但由于采用的是多開辟一格來判滿的方法，那就是代表了開辟了4個空間。

4個空間對應的下標為0 1 2 3.那為什么要改兩個指針rear和k加一呢？假設這時你的rear和front 都還在下標為 0 的位置，如果你不給 rear 加一，那你得出的結果就是 0 % 4 == 0.

這樣導致的后果就是和上面判空的條件是一樣的 0 == 0.會導致插入操作錯誤，會一直判滿從而不能進行插入。

而如果你給 rear 和 k 都加一就變成了 1 % 4 == 1.而這時 front 是 = 0的

就不會出現誤判的情況。只有當你的 rear 走到你多開辟的那一塊空間后才會出現判滿的情況。（這只是當 front 沒變的情況下的討論，關于 front改變后的討論，你可以構思一下大致相同。）

4.隊列的元素插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}obj->rear %= obj->k + 1;obj->a[obj->rear] = value;obj->rear++;return true;
}

?隊列的插入就是在rear的下標初進行插入。首先你要進行判滿，是因為循環隊列如果滿了以后就不會在追加新的元素，就很像游戲里的背包，滿了以后就不能獲得物品。為什么要讓rear % k+1呢？因為當你的元素走到最后一格的下一格，這時候是越界訪問的。因為是循環隊列，所以可以把他重新變到下標為 0 的位置。

我們的rear 的位置，每次都會加1 所以每次是在rear 的位置插入數據。

5.隊列的元素刪除

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front %= obj->k + 1;return true;
}

?元素刪除，首先如果你的隊列為空那就刪除不了了，返回false。

如果不為空，那front++ 即可，并且和 rear 一樣要 % k+1，是為了使隊列變成循環。如果不這樣就會越界訪問并且與題意不符（循環）。

要先++ 的原因是，如果你后++ 就會導致，如果此時你的front已經處于最后一個位置，

后++就會導致取頭元素時越界。如果先++ ，然后在%k+1 這樣在出了最后一格以后可以及時，變回0 下標，不會越界。

6.隊列的頭元素

int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}

?返回頭元素相較簡單，只要返回此時front 位置的元素即可。

7.隊列的尾元素（重點）

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}//if (obj->rear == 0)//{//	return obj->a[obj->k];//}//else//{//	return obj->a[obj->rear - 1];//}return obj->a[((obj->rear - 1) + (obj->k + 1)) % (obj->k + 1)];
}

?和頭元素的不同點在于，隊尾元素不能直接取隊尾的下標。

因為由前面的插入操作我們可以知道，在rear位置插入數據后，rear是要進行++的，此時在rear下標里是沒有元素的，隊尾實際上是在rear 的前一個下標的位置。

但如果你只用 obj->a[obj->rear - 1] 來訪問的話（如果你的rear是先%k +1，再++是可以的），但如果是先++，再%就不可以了，你可以思考一下當rear == 0，的時候，那你訪問的就是obj->[-1] 那就是未知訪問，錯誤。有兩種方法。

第一種，判斷當rear == 0的時候，你可以直接選擇返回最后一格 obj->k 的元素，

rear ！= 0時就返回 obj->rear - 1的下標的元素。

第二種，直接判斷不用 if else，obj->a[((obj->rear - 1) + (obj->k + 1)) % (obj->k + 1)]。

這串表達式的意思就是，因為我們是要返回 rear - 1下標位置的元素，所以我們 rear - 1；

而加上 k +1的原因是在 rear -1 的位置下，你加+ 上這個循環隊列的大小，那你還是在原地的，這里是為了防止特殊情況 rear = -1 時，rear = -1 原本是想訪問隊列最后一個空間的元素，但等于 - 1訪問不到，所以 rear = -1 加上一個 k+1,其實就是等于 k ，k % k +1 = k。所以訪問最后一個位置的元素。

8.隊列空間的釋放

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a = NULL;free(obj);obj = NULL;
}

?將開辟的空間釋放即可，但要先釋放obj->a 處的空間。

第二種方法雙向循環鏈表法

1.源代碼

typedef struct MyCircularQueue {struct MyCircularQueue* prev;struct MyCircularQueue* next;int val;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* phead = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));phead->next = phead;phead->prev = phead;phead->val = -1;phead->k = k;return phead;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj->next == obj){return true;}return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {MyCircularQueue* cur = obj->next;int size = 1;while (cur != obj){cur = cur->next;size++;}return size == obj->k;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->val = value;MyCircularQueue* prev = obj->prev;newnode->prev = prev;newnode->next = obj;prev->next = newnode;obj->prev = newnode;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}MyCircularQueue* Next = obj->next;obj->next = Next->next;Next->next->prev = obj;free(Next);Next = NULL;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->next->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->prev->val;
}void myCircularQueueFree(MyCircularQueue* obj) {MyCircularQueue* cur = obj->next;while (cur != obj){MyCircularQueue* del = cur;cur = cur->next;free(del);del = NULL;}free(obj);obj = NULL;
}

2.源代碼詳解！！

?1.創造哨兵位和 struct 變量

typedef struct MyCircularQueue {struct MyCircularQueue* prev;struct MyCircularQueue* next;int val;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* phead = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));phead->next = phead;phead->prev = phead;phead->val = -1;phead->k = k;return phead;
}

?我們定義一個雙鏈表的struct 結構。

然后再定義一個頭結點，并且將變量賦值。

2. 隊列判空和隊列判滿

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if (obj->next == obj){return true;}return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {MyCircularQueue* cur = obj->next;int size = 0;while (cur != obj){cur = cur->next;size++;}return size == obj->k;
}

?相較于數組的循環隊列，雙鏈表的判空判滿就比較簡單。空就是只有一個哨兵位就是空。

滿就是用一個size ++ 遍歷鏈表，后如果size == obj->k 就是滿。size 必須從 0?開始。

因為不從0?開始，總體隊列會少一個空間。

3.元素插入

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)){return false;}MyCircularQueue* newnode = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->val = value;MyCircularQueue* prev = obj->prev;newnode->prev = prev;newnode->next = obj;prev->next = newnode;obj->prev = newnode;return true;
}

元素的插入就是雙鏈表的尾插。?

4.元素刪除

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return false;}MyCircularQueue* Next = obj->next;obj->next = Next->next;Next->next->prev = obj;free(Next);Next = NULL;return true;
}

元素刪除就是雙鏈表的頭刪。?

5.頭元素

int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->next->val;
}

返回頭元素?

6.尾元素

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)){return -1;}return obj->prev->val;
}

返回尾元素?

7.空間的釋放

void myCircularQueueFree(MyCircularQueue* obj) {MyCircularQueue* cur = obj->next;while (cur != obj){MyCircularQueue* del = cur;cur = cur->next;free(del);del = NULL;}free(obj);obj = NULL;
}