循环队列的实现-EW帮帮网

在这里插入图片描述

循环队列

实现一个循环队列：C语言代码解析与设计思路

实现一个循环队列：C语言代码解析与设计思路

在数据结构的学习中，队列是一种常见的线性结构，而循环队列则是对普通队列的一种优化。它通过将队列的尾部和头部连接起来，解决了普通队列在删除元素后可能出现的空间浪费问题。本文将通过一个具体的C语言实现，详细介绍循环队列的设计思路和代码实现。

1. 循环队列的基本概念

循环队列是一种特殊的队列，它将队列的存储空间首尾相连，形成一个环形结构。这种结构的优点在于，当队列尾部达到存储空间的末尾时，可以循环回到存储空间的开头继续使用，从而充分利用存储空间，避免了普通队列中可能出现的“假溢出”现象。
要注意的一点是，在初始化队列时，容量应比实际大小+1，这样做的原因是要将队列为空以及队列为满的情况区分开来。

2. 数据结构设计

在C语言中，我们可以通过结构体来定义循环队列。以下是循环队列的结构体定义：

typedef struct {
    int front;        // 队列头部指针
    int rear;         // 队列尾部指针
    int capacity;     // 队列的总容量（实际存储容量 + 1）
    int* arr;         // 动态分配的数组，用于存储队列元素
} MyCircularQueue;

front：指向队列的第一个元素。
rear：指向队列的最后一个元素的下一个位置（这种设计可以方便地判断队列是否为空或满）。
capacity：队列的总容量，实际存储元素的数量为 capacity - 1。
arr：动态分配的数组，用于存储队列中的元素。

3. 初始化队列

创建循环队列时，需要分配内存空间，并初始化队列的头部和尾部指针。以下是初始化队列的代码：

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->arr = (int*)malloc(sizeof(int)*(k+1)); // 分配 k+1 的空间
    pq->capacity = k+1; // 设置队列容量
    pq->front = pq->rear = 0; // 初始化头部和尾部指针
    return pq;
}

分配了 k+1 的空间，其中 k 是实际存储元素的数量，多出的一个空间用于区分队列为空和队列满的状态。
初始化时，front 和 rear 都指向 0。

4. 入队操作

入队操作是将一个元素插入到队列的尾部。在循环队列中，需要先判断队列是否已满。以下是入队操作的代码：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if((obj->rear+1)%obj->capacity == obj->front) // 判断队列是否已满
        return false;
    obj->arr[obj->rear] = value; // 将元素插入到队列尾部
    obj->rear = (obj->rear + 1)%obj->capacity; // 更新尾部指针
    return true;
}

判断队列是否已满的条件是 (rear + 1) % capacity == front。
如果队列未满，将元素插入到 rear 指向的位置，然后将 rear 向后移动一位（使用取模操作实现循环）。

5. 出队操作

出队操作是从队列的头部删除一个元素。在循环队列中，需要先判断队列是否为空。以下是出队操作的代码：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(obj->front == obj->rear) // 判断队列是否为空
        return false;
    obj->front = (obj->front+1)%obj->capacity; // 更新头部指针
    return true;
}

判断队列是否为空的条件是 front == rear。
如果队列不为空，将 front 向后移动一位（使用取模操作实现循环）。

6. 获取队列头部和尾部元素

循环队列支持获取队列头部和尾部的元素，但需要先判断队列是否为空。以下是相关代码：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(obj->front == obj->rear) // 判断队列是否为空
        return -1;
    return obj->arr[obj->front]; // 返回队列头部元素
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(obj->front == obj->rear) // 判断队列是否为空
        return -1;
    if(obj->rear == 0) // 如果尾部指针指向 0，说明尾部元素在数组末尾
        return obj->arr[obj->capacity - 1];
    return obj->arr[obj->rear - 1]; // 返回队列尾部元素
}

获取队列头部元素时，直接返回 arr[front]。
获取队列尾部元素时，需要考虑尾部指针的循环情况。

7. 判断队列是否为空或满

循环队列可以通过 front 和 rear 的关系来判断队列是否为空或满。以下是相关代码：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front == obj->rear) // 判断队列是否为空
        return true;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%obj->capacity == obj->front) // 判断队列是否已满
        return true;
    else
        return false;
}

队列为空的条件是 front == rear。
队列已满的条件是 (rear + 1) % capacity == front。

8. 释放队列资源

在使用完循环队列后，需要释放分配的内存空间。以下是释放队列资源的代码：

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr); // 释放数组空间
    obj->arr = NULL;
    free(obj); // 释放队列结构体空间
    obj = NULL;
}

先释放数组空间，然后释放队列结构体空间。

9. 总结

通过上述代码，我们实现了一个功能完整的循环队列。循环队列通过将队列的尾部和头部连接起来，解决了普通队列的空间浪费问题，同时也保持了队列的基本操作特性。在实际应用中，循环队列可以用于任务调度、缓冲区管理等场景。

循环队列的实现