leetcode622.设计循环队列(C语言)

622.设计循环队列

目录

一、题目链接和介绍

二、大体思路

三、具体步骤

四、代码部分

一、题目链接和介绍

622. 设计循环队列 - 力扣（LeetCode）

实现一个循环的队列，其特性队列的先进先出(FIFO)原则，队尾被连接在队首之后以形成一个循环，该题目即为实现其功能。

二、大体思路

①创建一个大小为k+1的数组。使用head和tail两个变量来记录数组中数据的变化；

②存入数据时，tail指针向后移动；删除数据时，head指针向前移动。

③因为要存放k个数据，我们开辟k+1的空间的目的就是防止存入数据时发生了覆盖，当tail+1==head时即表示队列存满。

三、具体步骤

3.1 创建结构体

有一个head变量表示队列的头，tail表示队列的尾，k表示存入队列的大小，a开辟的数组。

typedef struct {
    int *a;
    int k;
    int head;
    int tail;
} MyCircularQueue;

3.2 队列的创建

因为结构体不好控制，而且下面题目的函数形参都是以结构体指针的形式传入，所以我们要初始创建时要使用结构体变量obj来控制。

又因为函数作用域的原因，所以我们创建该结构体时要使用malloc来开辟，这样函数销毁的时候我们创建的变量才不会被销毁，并且可以成功返回该结构体指针。

MyCircularQueue* myCircularQueueCreate(int k) {
        //控制该结构体(MyCircularQueue)的指针
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        //开辟k+1的数组空间
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->head=0;
        obj->tail=0;
        obj->k=k;
        return obj;
}

3.3 队列的插入

我们的思路是，将数据插入到 a[tail] 的位置，然后使 tail++ ，这样就可以数据插入到队列中去。

这里有一个问题，因为我们是循环队列，如果出现这种情况：

head因为删除数据导致前移，然后插入数据时tail走出了数组。

 所以这时我们要判断，如果当tail==k+1时，我们就要让tail回归到对头。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果队列未满，直接返回false，插入失败
    if(myCircularQueueIsFull(obj))
        return false;
        obj->a[obj->tail]=value;
        obj->tail++;
        //obj->tail%=(k+1)

        if (obj->tail==obj->k+1)
        {
            obj->tail=0;
        }
        return true;
}

3.4删除数据

想删除数据，只用将head向前移动一格即可。当然，也可能出现以下这种情况。

所以我们同样可以判断，当head==k+1时，我们将head移动到对头。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    return false;
    ++obj->head;
    if (obj->head==obj->k+1)
    {
        obj->head=0;
    }
    return true;
}

3.5 队列的判空

我们的思路是，队列初始状态下head和tail都存的是同一个下标，即head==tail==0，且我们规定了tail+1==head才是存满的，所以说只有当head和tail相等时队列才为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head==obj->tail;
}

3.6 队列的判满

以下我们有两种形式判定队列的为满的情况

 

二：我们先来看第二种情况，设置一个临时变量temp为tail+1，如果tamp==head就表示队列当前为满返回true。

第一种情况，设置一个临时变量temp为tail+1，如果temp==k+1，将temp置为0，再判断tamp是否等于head，如果等于，就表示为满，返回true。

 

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int next=obj->tail+1;
    //实际是再判断tail是否位于数组最后。
    if (next==obj->k+1)
    next=0;
    return next==obj->head;
}

3.7 队列头部数据

这就很简单了，直接返回head下标处的数据即可。

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

3.8 队列尾部数据

这里又分两种情况：①tail未被置0 ②tail被置零。

如果tail被置零，因为在程序的开始，我们就判断了队列是否为空，所以k位置处肯定是有数据的，我们直接返回k下标处的数据即可。

 

 

int myCircularQueueRear(MyCircularQueue* obj) {
       if (myCircularQueueIsEmpty(obj))
        return -1;
       if (obj->tail==0)
       {
           return obj->a[obj->k];
       }
        //return obj->a[(obj->tail+k)%(k+1)]
       return obj->a[obj->tail-1];
}

3.9 队列的销毁

我们首先要释放数组a，再释放队列。

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

四、代码部分

//使用数组实现
typedef struct {
    int *a;
    int k;
    int head;
    int tail;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        //开辟k+1的空间
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->head=0;
        obj->tail=0;
        obj->k=k;
        return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head==obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int next=obj->tail+1;
    if (next==obj->k+1)
    next=0;
    return next==obj->head;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
        obj->a[obj->tail]=value;
        obj->tail++;
        //obj->tail%=(k+1)

        if (obj->tail==obj->k+1)
        {
            obj->tail=0;
        }
        return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    return false;
    ++obj->head;
    if (obj->head==obj->k+1)
    {
        obj->head=0;
    }
    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
       if (myCircularQueueIsEmpty(obj))
        return -1;
       if (obj->tail==0)
       {
           return obj->a[obj->k];
       }
        //return obj->a[(obj->tail+k)%(k+1)]
       return obj->a[obj->tail-1];
}



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