??個人主頁:?? :???初階牛???
??推薦專欄:
??????C語言初階
??????C語言進階??個人信條: ??知行合一
??本篇簡介:>:講解用c語言實現數據結構的循環(huán)隊列.
一、題目介紹:
先聲明一下:
題目來源：力扣（LeetCode）
題目名稱:設計循環(huán)隊列:題目鏈接
難度: 中等
介紹:
設計你的循環(huán)隊列實現。 循環(huán)隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huá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
二、接口函數的分析:
2.1 循環(huán)隊列的結構
typedef int Queuedate;
typedef struct {
Queuedate* date;
int front;//隊首下標
int rear;//隊尾
int k;//隊列的長度(固定的)
} MyCircularQueue;
剛開始設計循環(huán)隊列時:
為了顯示循環(huán)的模樣,更加形象的圖:
此時遇到了一個難題:
為了解決隊列判滿與判空沖突問題,這里選擇設計2:以多開一個空間為代價.
那有沒有辦法不開空間也能解決這個問題呢?
另外方案:
增加一個size指針,用于記錄循環(huán)隊列元素的實際元素個數.
滿隊列: size=k
空隊列: size為0的時候是空隊列
2.2 初始化"循環(huán)隊列"(myCircularQueueCreate)
步驟:
- 為使得
myCircularQueueCreate函數生命周期結束后,obj(循環(huán)隊列)不被銷毀,所以需要動態(tài)申請(malloc)空間. - 為
obj(循環(huán)隊列)的date指針申請k(容量)個單位的空間. - 將
front(隊首下標)和rear(待插入位置下標)設置初始狀態(tài)為0. - 將參數
k的值,存入obj(循環(huán)隊列)保存,作為循環(huán)隊列的最大容量. - 返回
obj(循環(huán)隊列).
代碼:
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));;
obj->date = (Queuedate*)malloc(sizeof(Queuedate) * (k + 1));
if (obj->date == NULL)//如果開辟空間失敗
{
perror("obj malloc error");
}
//初始化時,隊首和隊尾都暫時賦值為0下標
obj->front = obj->rear = 0;
//記錄k的值,k表示循環(huán)隊列的容量.
obj->k = k;
return obj;
}
2.3 入隊(myCircularQueueEnQueue)
返回值說明:
true表示入隊成功.
false表示入隊失敗.
步驟:
1.進行入隊操作前,需要考慮隊滿情況(隊滿直接返回false即入隊失敗).
2.在rear下標位置插入新元素value.
3. 由于這里是循環(huán)隊列,所以相比于普通的隊列,這里需要一個rear自增時需要使其能夠循環(huán)回0下標處.(重點)
此時rear=4,如果我們進行 %周期 操作
(rear++) % (k + 1)
= 5 % 5
=0
這樣,rear就可以重新從0開始循環(huán)了.
代碼實現:
bool bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
obj->date[obj->rear] = value;
//隊尾++,注意考慮回0情況.
obj->rear = (obj->rear + 1) % (obj->k + 1);
return true;
}
2.4 出隊(myCircularQueueDeQueue)
步驟解析:
- 出隊列之前要考慮隊列是否為空,隊列為空返回false.
-
front(隊首下標)向后移動一位.
由于是循環(huán)隊列,front也要考慮特殊情況,也需要能夠回0(%周期)操作.
2.5 取隊首、隊尾元素
隊首元素很簡單獲取,返回obj->date[obj->front]即可.
需要注意的是:如果循環(huán)隊列為空,這里規(guī)定隊首返回值-1;(題干有要求).
隊尾元素獲取稍微復雜一些,因為存在特殊情況,如下圖:
此時可以直接返回obj->date[rear-1] 嗎?
那豈不是date[-1]了,所以我們需要對rear進行處理.rear - 1 + k + 1加上一套周期,那么:
0 - 1 + 5 % 5 = 4
似乎是滿足要求的.
可是,不要高興的太早了,我們?yōu)榱私鉀Q這一特殊情況進行了==+周期==,那普通情況呢?
rear - 1 + k + 1加上一套周期還對嗎?
2 - 1 + 5 = 6.
所以我們還需要進行==%周期==操作.
即完整的:obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//規(guī)定,如果隊列為空,則隊首是-1;
{
return -1;
}
return obj->date[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//規(guī)定,如果隊列為空,則隊首是-1;
{
return -1;
}
return obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}
代碼實現:
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front = (obj->front + 1) % (obj->k + 1);
return true;
}
2.6 循環(huán)隊列的判空、判滿:
在設計循環(huán)隊列的時候就考慮過這個問題,所以相信大家解決這兩個接口還是很簡單的吧!
判空:front(隊首)和rear (待插入)指向相等時,為空.
判滿:
front(隊首)和rear (待插入)的下一個相等時為滿.(注意%周期哦).
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if (obj->rear == obj->front)
{
return true;
}
else
{
return false;
}
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if ((obj->rear + 1) % (obj->k + 1) == obj->front)
{
return true;
}
else
{
return false;
}
}
循環(huán)隊列的銷毀:
只需要將之前在堆區(qū)申請的兩次空間釋放即可.文章來源：http://www.zghlxwxcb.cn/news/detail-467277.html
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->date);
free(obj);
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-467277.html
三、總代碼:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef int Queuedate;
typedef struct {
Queuedate* date;
int front;//隊首下標
int rear;//待插入位置的下標
int k;//隊列的長度(固定的)
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));;
obj->date = (Queuedate*)malloc(sizeof(Queuedate) * (k + 1));
if (obj->date == NULL)
{
perror("obj malloc error");
}
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
obj->date[obj->rear] = value;
//隊尾++
obj->rear = (obj->rear + 1) % (obj->k + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front = (obj->front + 1) % (obj->k + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果隊列為空,則隊首是-1;
{
return -1;
}
return obj->date[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))//如果隊列為空,則隊首是-1;
{
return -1;
}
return obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if (obj->rear == obj->front)
{
return true;
}
else
{
return false;
}
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if ((obj->rear + 1) % (obj->k + 1) == obj->front)
{
return true;
}
else
{
return false;
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->date);
free(obj);
}
到了這里，關于什么?要求設計一個循環(huán)隊列?的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
