---

前言

1、學習循環隊列和循環雙端隊列能加深我們對隊列的理解，提高我們的編程能力。
2、本文循環隊列使用的是數組，循環雙端隊列用的是雙向鏈表
3、題目連接：設計循環隊列 ，設計循環雙端隊列。

循環隊列

1、什么是循環隊列？

循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。

2、實現的功能

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

3、設計
有兩種方案：a:利用數組來存儲數據，b：利用鏈表來存儲數據
我們這里使用數組的方式
（1）我們設置一個頭指針，和一個尾指針（指的時最后一個有數據位置的下一個位置，為什么不直接指向最后有數據那個位置呢？因為這樣能更好的判斷隊列是否為空和隊列是否已經滿的情況），頭指針（front），尾指針（rear），容量（k）。

（2） 為了解決尾指針指向最后一個數據后一個的問題，我們可以多申請一個空間，就不會使尾指針指的位置超出數組了，這個問題也叫假溢出。

（3）判斷空，當front=rear時為空

（4）判斷滿，當 front=（rear+1）%（k+1） 為空

（5）刪除隊頭元素，使front=（front+1）%（k+1）即可， 也可以通過判斷front是否在（k+1）的位置，在的話就使front=0，不在的話front=front+1即可

（6）進隊，將數據放到數組下標rear位置上，然后使 rear=（rear+1）%（k+1） 即可，原理同上。

（7）獲取隊頭元素，直接返回隊頭下標的位置的數據即可

（8）獲取隊尾元素，返回 （rear-1+k+1)%(k+1) 位置的數據即可，也可以判斷rear是不是在0的位置，在的話top=k，不在0的位置的話就top=rear-1

4、代碼實現：

//隊列結構體
typedef struct {//儲存數據int *arr;//頭int front;//指向尾的下一個int rear;//大小int k;
} MyCircularQueue;//初始化循環隊列
MyCircularQueue* myCircularQueueCreate(int k) {//隊列MyCircularQueue* obj=( MyCircularQueue*)malloc(sizeof(MyCircularQueue));//初始化成員obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->front=0;obj->rear=0;obj->k=k;return obj;
}//是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//當隊頭的下標等于隊尾的下標時隊列為空return obj->front==obj->rear;
}//是否為滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {//當隊頭的下標等于隊尾加一模上k+1時隊列滿了return obj->front==(obj->rear+1)%(obj->k+1);
}//入隊
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//當隊列滿了就返回falseif(myCircularQueueIsFull(obj))return false;//放到rear位置上obj->arr[obj->rear]=value;//這樣當rear+1==k+1時，讓rear回到0這個位置上obj->rear=(obj->rear+1)%(obj->k+1);return true;
}//出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//空時返回falseif(myCircularQueueIsEmpty(obj))return false;//隊頭下標加1，莫上k+1當front+1==k+1時能回到0那個位置obj->front=(obj->front+1)%(obj->k+1);return true;
}//查看頭元素
int myCircularQueueFront(MyCircularQueue* obj) {//空時返回-1if(myCircularQueueIsEmpty(obj))return -1;//直接展示front位置即可int tmp=obj->arr[obj->front];return tmp;
}//查看隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//空時返回-1if(myCircularQueueIsEmpty(obj))return -1;//因為返回的是rear-1位置上的數據，當rear>0時,查看的位置時rear-1，當rear=0時就是查看k位置的數據了int tmp=obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)];return tmp;}//釋放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}

循環雙端隊列

1、循環雙端隊列就是在循環隊列的基礎上增加了一些接口，如：可以進行隊頭的插入，進行尾部的刪除。

2、實現的功能接口：

實現 MyCircularDeque 類:

（1）MyCircularDeque(int k) ：構造函數,雙端隊列最大為 k 。

（2）boolean insertFront()：將一個元素添加到雙端隊列頭部。 如果操作成功返回 true ，否則返回 false 。

（3）boolean insertLast() ：將一個元素添加到雙端隊列尾部。如果操作成功返回 true ，否則返回 false 。

（4）boolean deleteFront() ：從雙端隊列頭部刪除一個元素。 如果操作成功返回 true ，否則返回 false 。

（5）boolean deleteLast() ：從雙端隊列尾部刪除一個元素。如果操作成功返回 true ，否則返回 false 。

（6）int getFront() )：從雙端隊列頭部獲得一個元素。如果雙端隊列為空，返回 -1 。

（7）int getRear() ：獲得雙端隊列的最后一個元素。 如果雙端隊列為空，返回 -1 。
（8） boolean isEmpty() ：若雙端隊列為空，則返回 true ，否則返回 false 。

（9）boolean isFull() ：若雙端隊列滿了，則返回 true ，否則返回 false 。

3、設計
（1）用雙向鏈表的節點，這樣方便找到尾部的上一個節點，利于隊尾的刪除。
（2）定義size來判斷空和滿，再定義兩個節點指針，分別指向隊頭（front），隊尾（rear），容量（k），前驅指針（next），后驅指針（next1）。
（3）判斷為空，當size=0時為空。
（4）判斷是否滿，當size=k時為滿。
（5）隊頭插入數據，申請一個節點tmp，再將tmp和front連起來，最后front=tmp即可

（6）隊尾插入數據，申請一個節點tmp，再將tmp和rear連接起來，最后rear=tmp即可

（7）隊頭刪除，先保存隊頭的后一個節點next，再將front釋放，最后將front=next并把front->next1=NULL即可，注意順序不能亂。

（8）隊尾刪除，先保存前一個節點next1，再將rear釋放，最后將rear=next1并把rear->next=NULL即可，注意順序不能亂。

（9）獲取隊頭元素，直接返回front的數據即可。
（10）獲取隊尾元素，直接返回rear的數據即可。

4、代碼實現：

//雙向鏈表的結構體
typedef struct  ls
{//前驅struct ls *next;//后驅struct ls *next1;//數據int val;
}ls;class MyCircularDeque {
public://初始化MyCircularDeque(int k) {//容量this->k=k;//大小this->size=0;this->rear=NULL;this->front=NULL;}//隊頭插入數據bool insertFront(int value) {//  滿了，就返回if(isFull())return false;//沒滿//申請一個節點ls *tmp(ls*)malloc(sizeof(ls));tmp->next=NULL;tmp->next1=NULL;tmp->val=value;//空的話頭和尾指向第一個節點if(front==NULL){front=rear=tmp;}//不空，插入頭else{front->next1=tmp;tmp->next=front;front=tmp;}//大小加1size++;return true;}//隊尾插入數據bool insertLast(int value) {if(isFull())return false;//申請節點ls *tmp=(ls*)malloc(sizeof(ls));tmp->next=NULL;tmp->next1=NULL;tmp->val=value;if(rear==NULL){front=rear=tmp;}//尾插到rear后面else{tmp->next1=rear;rear->next=tmp;rear=tmp;}//大小加1size++;return true;}//刪隊頭   bool deleteFront() {//為空if(isEmpty())return false;//只有一個元素ls *tmp=front->next;free(front);if(tmp==NULL)front=rear=tmp;//多個元素else{front=tmp;front->next1=NULL;}//大小-1     size--;return true;}//刪隊尾bool deleteLast() {if(isEmpty())return false;//只有一個元素ls *tmp=rear->next1;free(rear);if(tmp==NULL){rear=front=tmp;}else{tmp->next=NULL;rear=tmp;}// 大小-1size--;return true;}//顯示頭元素int getFront() {//為空if(isEmpty())return -1;//直接返回頭節點的數據return front->val;}//顯示尾節點元素int getRear() {//為空if(isEmpty())return -1;//直接返回尾節點數據return rear->val;}//判斷是否為空bool isEmpty() {//當size==0是為空return size==0;}//判斷是否為滿bool isFull() {//size==k就滿了return size==k;}//釋放鏈表~MyCircularDeque(){ls* tmp=front;while(tmp){ls*p=tmp->next;free(tmp);tmp=p;}}//頭和尾ls* front;ls* rear;//容量和大小int k;int size;
};

以上就是我的分享了

最后，感謝大家的觀看！