這是一道leetcode關(guān)于隊列的經(jīng)典題：

622.?設(shè)計循環(huán)隊列https://leetcode.cn/problems/design-circular-queue/

思路：?

?大家注意這個題目要求，這個隊列是定長的，如果滿了則不能再添加數(shù)據(jù)。那么我們設(shè)計一個隊頭front和隊尾rear，每次添加數(shù)據(jù)rear向后走，這時就有一個問題，怎么區(qū)分空和滿呢？當最后一個數(shù)據(jù)入隊列之后，由于這是個循環(huán)隊列，rear會回到front這個位置。那么比較好的一種方法就是多開一個空間，滿的條件是rear+1==front。

?

實現(xiàn)：

循環(huán)隊列的定義：

typedef struct {
    int K;
    int* a;
    int front;
    int rear;
} MyCircularQueue;

循環(huán)隊列的創(chuàng)建：

為隊列和數(shù)組創(chuàng)建空間，需要注意的是數(shù)組a的空間是K+1個，要多開一個.

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多開辟一個空間，用以區(qū)分空和滿
    obj->K=k;
    obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
    obj->front=0;
    obj->rear=0;
    return obj;
}

判斷隊列是否為空：

如果front==rear則為空。

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

判斷隊列是否為滿：

如果rear+1==front則為滿，或者說(rear+1)%(k+1）==front。

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

?數(shù)據(jù)入隊列：

先判斷隊列是否滿了，滿了則返回false。如果不滿則在rear這個位置上添加數(shù)據(jù)，再把rear++，再將rear=rear%（k+1）。

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

    obj->rear=(obj->rear)%(obj->K+1);
    return true;
}

數(shù)據(jù)出隊列：

判斷一下隊列是否為空，空則返回false。出隊列直接將front++即可，再將front=front%（k+）。

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

取隊列頭部數(shù)據(jù)：

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

取隊列尾部數(shù)據(jù)：

這里需要注意，尾部數(shù)據(jù)的位置是在rear-1這個位置，所以rear-1+k+1就是rear+k.

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

銷毀隊列：

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

完整代碼：

typedef struct {
    int K;
    int* a;
    int front;
    int rear;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多開辟一個空間，用以區(qū)分空和滿
    obj->K=k;
    obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
    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->a[obj->rear]=value;
    obj->rear++;

    obj->rear=(obj->rear)%(obj->K+1);
    return true;
}

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

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

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

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

這次的分享到這里就結(jié)束了，感謝大家的閱讀！文章來源地址http://www.zghlxwxcb.cn/news/detail-758989.html

到了這里，關(guān)于手把手教你實現(xiàn)一個循環(huán)隊列（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！