前言????????

? ? ? ? 循環隊列是隊列的一種特殊的結構，在生產者——消費者模型中常常使用它，?它在邏輯上是一個環形的連續的結構。在物理可以使用數組來實現。

目錄

1.循環隊列的邏輯結構

2.空的循環隊列和滿的循環隊列

3.循環隊列插入和刪除?

4.代碼實現?

---

1.循環隊列的邏輯結構

????????

? ? ? ? ?循環隊列在邏輯上連續的。

2.空的循環隊列和滿的循環隊列

? ? ? ? 因為是采用數組進行隊列的實現的，如果是存儲N個數據的隊列，需要開辟N + 1個空間，當隊頭指針Front等于隊尾指針rear時，隊列為空。當隊尾指針?（rear+1）%（N + 1）+ 1等于隊頭指針時，此時隊列為滿，為什么隊尾指針要對N + 1進行取模運算呢，因為數組是連續的，當循環隊列的尾指針走到數組的末尾時需要從數組下標為零的位置重新開始。不然數組的訪問就會越界，對于頭指針來說也是一樣的。如圖：

3.循環隊列插入和刪除?

? ? ? ? ?循環隊列和隊列一樣，也是在隊頭插入數據，隊尾刪除數據。需要注意的是如果隊頭已經在數組的末尾了這時候刪除掉隊頭的元素，隊頭的指針要更新到數組下標為零的元素，也就是front=（front+1）。那么下一次，隊列刪除的就是數組的第一個元素，如圖：

? ? ? ? ?插入元素也是一樣的，如果rear超過了數組的長度以后要回到開始的位置。

? ? ? ? 為什么給數組開空間的時候要多開一個呢，因為始終要留出一個空位來，不然無法確定隊列滿的條件。?

4.代碼實現?

????????

typedef struct
{int* _array;int _front;int _rear;int _k;
} MyCircularQueue;bool myCircularQueueIsFull(MyCircularQueue* obj);//判斷隊列是否滿了。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判斷隊列是否為空MyCircularQueue* myCircularQueueCreate(int _k) {MyCircularQueue* qu = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));qu->_array = (int*)malloc(sizeof(int) * (_k + 1));//多開一個qu->_front = qu->_rear = 0;//初始化指針qu->_k = _k + 1;return qu;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//入數據
{if (obj == NULL)return false;//隊列為空直接返回//如果隊列滿了也就不能插入元素了if (myCircularQueueIsFull(obj)){return false;}else{//隊尾入數據obj->_array[obj->_rear] = value;++(obj->_rear);obj->_rear = obj->_rear % (obj->_k);//確保rear是在合適的位置return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) //隊頭出數據
{if (obj == NULL)return false;if (obj->_front == obj->_rear)//隊列為空時不能出數據return false;++(obj->_front);obj->_front %= (obj->_k);//確保front不會越界return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))//隊列為空返回-1return -1;return obj->_array[obj->_front];
}
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))//隊列為空返回-1return -1;int tail = obj->_rear - 1;if (tail == -1)//如果tail為-1說明這時候rear在數組的開頭，需要出隊尾的元素在數組的末尾tail = obj->_k - 1;return obj->_array[tail];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->_front == obj->_rear;//rear等于front時，隊列為空
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return ((obj->_rear + 1) % obj->_k == obj->_front); //rear + 1等于front說明隊列滿了
}void myCircularQueueFree(MyCircularQueue* obj) {if (obj == NULL)return;//確保指針存在free(obj->_array);//先釋放開辟的數組free(obj);
}

? ? ? ? 原題鏈接循環隊列的實現?，如果大家有興趣的，嘗試一下。

?