【C数据结构】循环队列_CyclicQueue

骑猪看日落 2024-03-16 20:20 52阅读 0赞

**目录**

循环队列\_CyclicQueue

【1】循环队列

【1.1】循环队列的各个接口

【1.2】循环队列初始化

【1.3】循环队列初销毁

【1.4】循环队列插入

【1.5】循环队列删除

【1.6】循环队列获取头位置数据

【1.7】循环队列获取尾位置数据

【1.8】循环队列判满

【1.9】循环队列判空

--------------------

## 循环队列\_CyclicQueue ##

## 【1】循环队列 ##

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

![348f953d784e47828bc26c85ffa47b99.png][]

### 【1.1】循环队列的各个接口 ###

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <assert.h>
    
    
    // 栈数据结构定义 ///
    #define CYCLIC_QUEUE_CAPACITY 100
    typedef int CQDataType;
    typedef struct CyclicQueue {
        CQDataType* _buffer;
        int _front;
        int _back;
        size_t _size;
        size_t _Capacity;
    }CQ;
    
    // 栈常用接口定义 ///
    /* 循环队列：初始化 */
    void CyclicQueueInit(CQ* cq);
    
    /* 循环队列：销毁 */
    void CyclicQueueDestroy(CQ* cq);
    
    /* 循环队列：插入 */
    void CyclicQueuePush(CQ* cq, CQDataType val);
    
    /* 循环队列：删除 */
    void CyclicQueuePop(CQ* cq);
    
    /* 循环队列：获取头位置数据 */
    CQDataType CyclicQueueFront(CQ* cq);
    
    /* 循环队列：获取尾位置数据 */
    CQDataType CyclicQueueFrontBack(CQ* cq);
    
    /* 循环队列：判断空 */
    bool CyclicQueueEmpty(CQ* cq);
    
    /* 循环队列：判断满 */
    bool CyclicQueueFull(CQ* cq);
    
    /* 循环队列：获取最大容量 */
    size_t CyclicQueueCapacity(CQ* cq);
    
    /* 循环队列：获取当前有效数据个数 */
    size_t CyclicQueueSize(CQ* cq);

### 【1.2】循环队列初始化 ###

/* 循环队列：初始化 */
    void CyclicQueueInit(CQ* cq) {
        // 断言
        assert(cq);
    
        // 提前开辟空间
        cq->_buffer = (CQDataType*)malloc(sizeof(CQDataType) * (CYCLIC_QUEUE_CAPACITY + 1));
        if (cq->_buffer == NULL) {
            perror("malloc fail!");
            exit(-1);
        }
        // 初始化
        memset(cq->_buffer, 0, sizeof(CQDataType) * (CYCLIC_QUEUE_CAPACITY + 1));
        cq->_front = cq->_back = 0;
        cq->_size = 0;
        cq->_capacity = CYCLIC_QUEUE_CAPACITY + 1;
    }

### 【1.3】循环队列初销毁 ###

/* 循环队列：销毁 */
    void CyclicQueueDestroy(CQ* cq) {
        // 断言
        assert(cq);
    
        // 释放空间
        free(cq->_buffer); cq->_buffer = NULL;
        // 初始化
        cq->_front = cq->_back = 0;
        cq->_size = 0;
        cq->_capacity = 0;
    }

### 【1.4】循环队列插入 ###

**插入时注意：**back的位置到达后边界，需要让他回到0位置。

![4ec7e40e66534354967a01b7c73fc56d.png][]

/* 循环队列：插入 */
    void CyclicQueuePush(CQ* cq, CQDataType val) {
        // 断言
        assert(cq);
    
        // 检查是否满
        if (CyclicQueueFull(cq)) {
            printf("Cyclic Queue Full！\n");
            return ;
        }
        // 插入数据
        cq->_buffer[cq->_back++] = val;
        // 如果back到达尾部，需要调整为0
        cq->_back %= cq->_capacity;
        cq->_size++;
    }

### 【1.5】循环队列删除 ###

**删除时注意：**front的位置到达后边界，需要让他回到0位置**(与插入相同)。**

/* 循环队列：删除 */
    void CyclicQueuePop(CQ* cq) {
        // 断言
        assert(cq);
     // 检查空
        if (CyclicQueueEmpty(cq)) {
            printf("Cyclic Queue Empty！\n");
            return;
        }
    
        cq->_front++;
        // 如果front到达尾部，需要调整为0
        cq->_front %= cq->_capacity;
        cq->_size--;
    }

### 【1.6】循环队列获取头位置数据 ###

/* 循环队列：获取头位置数据 */
    CQDataType CyclicQueueFront(CQ* cq) {
        // 断言
        assert(cq);
        // 检查空
        if (CyclicQueueEmpty(cq)) {
            printf("Cyclic Queue Empty！\n");
            return -1;
        }
    
        return cq->_buffer[cq->_front];
    }

### 【1.7】循环队列获取尾位置数据 ###

![3dc0afd8c9ae43e1876ba9e095835297.png][]

/* 循环队列：获取尾位置数据 */
    CQDataType CyclicQueueFrontBack(CQ* cq) {
        // 断言
        assert(cq);
        // 检查空
        if (CyclicQueueEmpty(cq)) {
            printf("Cyclic Queue Empty！\n");
            return -1;
        }
        else
        {
            return cq->_buffer[(cq->_back - 1 + cq->_capacity) % cq->_capacity];
        }
    }

### 【1.8】循环队列判满 ###

![50e920cedc06483a90f1b505b831b4c1.png][]

/* 循环队列：判断满 */
    bool CyclicQueueFull(CQ* cq) {
        // 断言
        assert(cq);
    
        return (cq->_back + 1) % cq->_Capacity == cq->_front;
    }

### 【1.9】循环队列判空 ###

![0e833aacde4a4646b4b6fd5025583f94.png][]

/* 循环队列：判断空 */
    bool CyclicQueueEmpty(CQ* cq) {
        // 断言
        assert(cq);
    
        return cq->_back = cq->_front;
    }

[348f953d784e47828bc26c85ffa47b99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/70475228e55941c09d9ea7cd50697f64.png
[4ec7e40e66534354967a01b7c73fc56d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/69f5b0b48f6444328cf91d060ee43320.png
[3dc0afd8c9ae43e1876ba9e095835297.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3f91b015b9334ca19b05b99c81bfd640.png
[50e920cedc06483a90f1b505b831b4c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/498a2a80f77d416f9b5a1229e971531d.png
[0e833aacde4a4646b4b6fd5025583f94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/048d5463e28d4864bdb20738e49b0fe9.png