数据结构C语言练习(设计循环队列)

一、循环队列简介

循环队列是一种线性数据结构，基于 FIFO（先进先出）原则，将队尾连接到队首形成循环。其核心优势是能复用队列之前用过的空间，避免普通队列 “假溢出” 问题。实现时，通常申请 k+1 大小的数组（k 为队列设定长度），通过 front（队首）和 rear（队尾）指针配合取模运算处理循环逻辑。

练习题：

1.力扣 622.设计循环队列

二、解题思路

1. 数据结构定义：定义结构体 MyCircularQueue，包含存储数组 arr、队首指针 front、队尾指针 rear、队列容量 capacity。

   typedef struct {
       int* arr;
       int front;//对头
       int rear;//队尾
       int capacity;//循环队列的空间大小
   } MyCircularQueue;

   
2. 空间分配：创建队列时，申请 k+1 大小的数组，利用 “牺牲一个空间” 的方式区分队列空和满的状态。
3. 核心操作：
   • 入队（enQueue）：检查队列是否满，未满则插入元素，更新 rear。
   • 出队（deQueue）：检查队列是否空，非空则删除元素，更新 front。
   • 判空（isEmpty）：front == rear 时队列为空。
   • 判满（isFull）：(rear + 1) % (capacity + 1) == front 时队列满。

三、函数实现详解

1. 队列创建函数 myCircularQueueCreate

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->arr = (int*)malloc(sizeof(int) * (k + 1)); // 申请 k+1 空间
    pq->front = pq->rear = 0; // 初始化队首队尾
    pq->capacity = k; // 设置容量
    return pq;
}

• 作用：分配队列结构体和数组内存，初始化指针和容量。
• 关键点：k+1 空间用于区分队列空满状态(可用空间数还是k)。

2. 判空函数 myCircularQueueIsEmpty

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear; // 队首队尾重合则为空
}

• 逻辑：当 front 和 rear 指向同一位置，说明队列无元素。

3. 判满函数 myCircularQueueIsFull

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

• 逻辑：利用取模运算，判断队尾下一个位置是否等于队首。若相等，说明队列已满。

4. 入队函数 myCircularQueueEnQueue

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) { // 判断是否为满，如果是直接返回false
        return false;
    }
    obj->arr[obj->rear+] = value; // 插入元素
    //然后rear+1向后移动一个位置为下一个插入元素做准备
    //但rear+1有可能会出界所以模上capacity + 1
    obj->rear = (obj->rear + 1) % (obj->capacity + 1); // 更新队尾（循环处理）
    return true;
}

• 步骤：检查队列是否满 → 未满则插入元素 → 更新 rear 指针（通过取模实现循环）。

5. 出队函数 myCircularQueueDeQueue

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) { // 判断是否为空，如果是就返回false
        return false;
    }
    // 让front向后移动一位，为了防止front出界所以模上capacity + 1
    obj->front = (obj->front + 1) % (obj->capacity + 1); // 更新队首
    return true;
}

• 步骤：检查队列是否空 → 非空则更新 front 指针（取模实现循环）。

6. 获取队首元素 myCircularQueueFront

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) { // 判断是否为空，如果是就返回-1
        return -1;
    }
    return obj->arr[obj->front]; // 返回队首元素
}

• 逻辑：先判断队列是否空，非空则返回 front 指向的元素。

7. 获取队尾元素 myCircularQueueRear

int myCircularQueueRear(MyCircularQueue* obj) {
                     // 判空
    if (myCircularQueueIsEmpty(obj)) { 
        return -1;
    }
     // 先假设队尾元素的索引是当前队尾指针减 1
    int prev = obj->rear - 1;

    // 处理循环情况，队尾为 0 时，实际队尾是 capacity
    if (obj->rear == 0) { 
        prev = obj->capacity;
    }
    // 返回队尾元素
    return obj->arr[prev]; 
}

• 逻辑：先判空，再通过计算得到队尾真实索引（处理循环场景），返回对应元素。

8. 释放内存函数 myCircularQueueFree

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr); // 释放数组内存
    free(obj); // 释放结构体内存
}

• 作用：释放队列申请的内存，避免内存泄漏。

四、总结

循环队列通过巧妙的指针和取模运算，解决了普通队列的空间浪费问题。实现时需注意：

• 利用 k+1 空间区分空满状态。
• 所有指针移动操作都需配合取模运算，确保循环逻辑正确。
• 每个操作前先进行空 / 满判断，保证程序健壮性。

通过上述函数实现，可完整支持循环队列的创建、插入、删除、查询等核心操作，满足题目要求。