设计循环队列---力扣622

1、题目

1.1基础设置与讲解

循环队列，即固定长度的队列，可以想象成一个环形队列

就类似于这种队列，队尾指针后会有一个空位，用于控制判断队列为空还是为满；

typedef int MyDataType;
 
typedef struct {
    MyDataType front;
    MyDataType rear;
    MyDataType* a;
    MyDataType capacity;
} MyCircularQueue;

首先将int更名为MyDataType，方便对数据类型的统一管理；

并定义了一个结构体MyCircularQueue，

结构体内的成员

    MyDataType front;-----用于表示队列头指针
    MyDataType rear;-----尾指针
    MyDataType* a;-----存储队列元素的数组
    MyDataType capacity;-----队列所占空间大小

1.2节点创建

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* new = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (new == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    new->a = (int*)malloc(sizeof(int)*(k+1));
    new->front = new->rear = 0;
    new->capacity = k ;
    return new;
}

首先节点的创建必须有返回值，以供使用，这个返回值显而易见应该是MyCircularQueue*，因为返回的是一个结构体的存储。

先开辟一个大小为MyCircularQueue类型的空间，并且创建一个新结构体用于接收，对开皮的空间进行判定，如果开辟失败则返回perror，并结束进行，如果空间开辟成功，则将结构体内部成员进行初始化，防止出现野指针、空指针等问题。

其中capacity的大小为k，而

    new->a = (int*)malloc(sizeof(int)*(k+1));

此处的k是队列长度，而开辟空间的时候应该加一，因为使用a这个数组存储，而数组是从0开始编号，所以k+1；

1.3队列的满和空

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

第一个函数，判断队列是否为空，为空则返回true，如果不为空则返回false，当头指针与尾指针相同时，则代表队列此时为空，如下图；

第二个函数，判断队列是否为满，为满则返回true，如果不为满则返回false，

1.4入队列

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

首先保证队列不为满，为满则无法进行存储；队尾指针进行数组数据输入。

 obj->rear = (obj->rear) % (obj->capacity+1);

这行代码的作用是将 rear 限制在 0 到 obj->capacity（包含）之间，以确保其不超过队列的容量。

其中如果只是obj->capacity的话只能在0~capacity-1，所以需要obj->capacity+1；

这是因为循环队列是一个环形结构，在到达数组末尾时会绕回到数组的起始位置，因此需要用取模操作来实现这种循环。

1.5出队列

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->a[obj->front] = 0;
    obj->front++;
    obj->front = (obj->front) % (obj->capacity+1);
    return true;
}

1.6取头指针和尾指针的数据

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

1.7对队列进行释放

void myCircularQueueFree(MyCircularQueue* obj) {
    while (obj->a[obj->front] != 0)
    {
        obj->a[obj->front] = 0;
        obj->front++;
        obj->front = (obj->front) % (obj->capacity+1);
    }
    obj->capacity = 0;
    obj->front = obj->rear = NULL;
    free(obj->a);
    free(obj);
}

2、总结

1. 选择合适的数据结构： 循环队列通常基于数组实现，因为数组能够提供 O(1) 的随机访问时间，这对于循环队列中常见的插入和删除操作至关重要。但也可以使用链表实现循环队列，尤其在需要动态扩展队列大小时，链表实现可能更灵活。

2. 确定队列的容量： 循环队列的容量应该是队列数组的大小减去 1，这是因为需要一个额外的位置来区分队列的空和满状态。

3. 定义队列的属性： 需要定义队列结构体，并在其中包含头指针、尾指针以及存储元素的数组等属性。头指针和尾指针用于指示队列的起始位置和结束位置，而数组用于存储队列中的元素。

4. 实现基本操作： 循环队列通常需要实现以下基本操作：

   • 入队操作（enqueue）：向队尾插入元素。
   • 出队操作（dequeue）：从队首删除元素。
   • 判空操作（isEmpty）：检查队列是否为空。
   • 判满操作（isFull）：检查队列是否已满。
   • 获取队首元素（front）：返回队首元素的值，但不删除它。
   • 获取队尾元素（rear）：返回队尾元素的值，但不删除它。