【练习题】设计循环队列

一、题目目的

循环队列题目

题目的要求是我们要设计一个队列，这个队列的空间是固定的，我们能对队列进行插入删除操作。

二、解题思路

我们可以用两种方式设计循环队列
第一种：链表
我们可以用链表来设计循环队列，优点是我们不用 malloc 开辟空间，在也不用 realloc 调整空间大小，并且也不必担心空间浪费，不会出现多开空间而用不上的情况。并且我们可以在任意位置插入或删除数据，只用改变链表的指向就行。
第二种：数组
我们也可以用数组来设计循环队列，优点是因为有数组下标的存在，我们在数组中想要查询某一位置的数据时会很方便。

综上所述
>我们发现链表的优点在于空间利用率高，并且在某一位置插入或删除数据时也很方便。但对于这个题来说，我们要设计一个固定空间大小的队列进行循环，并且因为我们设计的是队列，我们只需要对头和尾的数据进行操作，那么链表的优势我们并用不上。
>而数组的下标查找对我们这个题很友好，我们可以通过数组的下标，很轻松的访问到我们需要的数据，而链表就需要遍历。

(ps : 我们假设题目中的 k = 4，也就是开辟的循环队列中可以存储四个数据。)

用链表设计循环队列

我们在实现队列时我们用的是链表，因为链表的头删和尾插操作很方便，那我们想这个循环队列我们可不可以用链表来进行操作。
若用链表来操作，我们可以将链表头尾相连，使链表成环。

为了完成题目中循环的要求我们设计两个指针

phead : 作为头指针，用以保存头节点的地址
ptail : 作为尾指针，用以保存尾节点的下一个节点

1>插入数据：

我们只要将数据插入ptail 所在节点，然后再将ptail 指向它的下一个。

2>删除数据：

我们只需要将phead 指向它的下一个节点，那么当ptail 再次走到这里要插入数据时，直接覆盖就行。

我们要进行插入或者删除操作时要对队列判空和判满
当队列满时我们不能插入数据
当队列空时我们不能删除数据

那么就引出一个问题，就是如何判空判满，当 phead == ptail 时
有可能是空，也有可能是满。

所以我们有一些解决方法

eg1:计数器
我们可以在创建队列的结构体是，在里面加一个变量size用于计数，当size = k 时，为满，当size = 0时为空。
eg2:多开辟一个空间
多开辟一个空间，以此来区别空和满。

我采取的是多开辟一个空间的方法，

当我们有多的一个空间时，我们的满和空就可以区分出来。
当 phead == ptail 时为空
当 ptail->next == phead 时为满。

代码实现

好了思路完成了，接下来就要实现代码了
链表实现的一个麻烦之处就是，我们创建队列。
首先我们要创建一个链表，这个链表中包含了 k + 1 个节点，并且要将他们链接起来。
力扣可能在他的库函数中有 ListNode 这个结构体，所以我就少了一个e，要不然会弹出类型重定义

再下面，因为我们这个是循环链表，在后面插入删除什么的也不会有空的风险，就很轻松了。

判断队列是否为空

判断队列是否为满

插入数据

在插入之前我们要先判断队列是否为满，然后将数据插在ptail位置，再将ptail向后一个节点

删除数据

在删除之前我们要先判断队列是否为空，然后直接将phead向后走一个节点，这样原来的节点就相当于我们还给队列了，数据还在，但是当后面插入时，这个节点会被改变。

返回队首数据

返回之前我们要判断队列是否为空，然后返回phead节点处的数据。

返回队尾数据

在返回之前要判断队列是否为空，然后遍历队列找到尾节点因为ptail是保存尾节点的下一个节点的，所以需要遍历找到ptail前一个节点

队列销毁

在销毁时我们要注意，我们不能直接 free(obj) ，因为obj 中只有最多两个节点，也就是头节点和尾节点

所以我们要循环遍历销毁，保证队列中每一个节点都被销毁。

代码整体

下面是全部代码：

//链表的结构体
typedef int CQDateType;
typedef struct ListNod {
    struct ListNod* next;
    CQDateType val;
}ListNod;

//循环队列的结构体
typedef struct {
    struct ListNod* phead;//存储头节点
    struct ListNod* ptail;//存储尾节点的下一个节点
} MyCircularQueue;

//开辟链表
ListNod* LTBuyNode()
{
    ListNod* plist = (ListNod*)malloc(sizeof(ListNod));
    if (plist == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    plist->next = NULL;
    plist->val = 0;
    return plist;
}

//函数声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//开辟循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    //开辟循环队列
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (cq == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    //先开辟一个节点数为 k + 1 的循环链表
    ListNod* head = LTBuyNode();
    ListNod* pcur = head;
    for (int i = 0; i < k; i++)
    {
        ListNod* tmp = LTBuyNode();
        pcur->next = tmp;
        pcur = pcur->next;
    }
    //出循环则变成一个 k + 1 个节点的链表
    //接下来将他们链接起来
    pcur->next = head;
    //将循环链表赋给循环队列
    cq->phead = head;
    cq->ptail = head;
    return cq;
}

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    //判断队列是否为满
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入数据
    obj->ptail->val = value;
    obj->ptail = obj->ptail->next;
    return true;
}

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //删除数据
    obj->phead = obj->phead->next;
    return true;
}

//返回队首数据
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->phead->val;
}

//返回队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //遍历队列找到队尾
    ListNod* pcur = obj->phead;
    while (pcur->next != obj->ptail)
    {
        pcur = pcur->next;
    }
    return pcur->val;
}

//判断队列是否为空
//为空返回 true 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->phead == obj->ptail;
}

//判断队列是否为满
//为满返回 ture
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return obj->ptail->next == obj->phead;
}

//队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    ListNod* pcur = obj->phead;
    while (pcur != obj->ptail)
    {
        ListNod* plist = pcur;
        pcur = pcur->next;
        free(plist);
        plist = NULL;
    }
    free(obj);
    obj = NULL;
}

用数组设计循环队列

用数组来设计循环队列，是有优势的因为数组方便访问下标，而且数组的缓存利用率高，就是代码实现起来相对有些绕，但是代码总量会少一点，能少个四十行左右，下面来说一下思路。

关于判断队列的空和满和上面一样，都是采用多开一个数组的方式。

但是数组的我们找数据的方式是用下标，那就会出现一个问题，就是当我们插入数据时插入到最后一个时会超出范围

这时我们可以令 (ptail + 1) % (k + 1)

这样就可以巧妙的将 ptail 的值维持在 k + 1 以内，并且还不会影响前面的值。后面会很多使用这个方法
首先是结构体的创建

判断队列是否为空

判断队列是否为满

这里就用了刚刚的方法，因为ptail 的下一个如果超出了数组的边界，就会出错。

插入数据

在插入时先将数据插入 ptail 处，再将ptail 向后一位。

删除数据

将数据删除，直接将 phead 向后移到，在数组中就是将 phead++ ，但因为有可能下一个超出数组边界，所以要 (ptail + 1) % (k + 1) 。

返回队尾数据

返回队尾数据不用向链表那样遍历，我们可以直接改变下标来访问，这也是对于这个题，用数组的优势。

如图，我们想要取队尾数据，就是 ptail 的前一个，正常的情况下我们只要对 ptail - 1就行，但是当 ptail 为对一个元素时，也就是当 ptail 为 0 时减 1 ，就会使 ptail 变为 -1，这样的下标会报错。

返回队首数据

队列销毁

这里我们在销毁时，我们要先释放队列结构体中我们 malloc 的数组，然后再释放 obj 。

代码整体

typedef int QDateType;
typedef struct {
    QDateType* arr;//用数组创建循环队列
    int phead;//队列头的下标
    int ptail;//队列尾的下标
    int k;//队列大小
} MyCircularQueue;

//函数声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//队列初始化
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    QDateType* tmp = (QDateType*)malloc(sizeof(QDateType) * (k + 1));
    if (tmp == NULL)
    {
        perror("malloc fail:");
        exit(1);
    }
    cq->arr = tmp;
    cq->phead = cq->ptail = 0;
    cq->k = k;
    return cq;
}

//向队列插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    //先判断队列是否满
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    //向队列中插入数据
    obj->arr[obj->ptail] = value;
    obj->ptail = (obj->ptail + 1) % (obj->k + 1);
    return true;
}

//删除队列元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    //先判断是否为空
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //删除数据
    obj->phead = (obj->phead + 1) % (obj->k + 1);
    return true;
}

//返回队头数据
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    //先判断是否为空
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //返回队首数据
    return obj->arr[obj->phead];
}

//返回队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    //先判断是否为空
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //返回队尾元素
    return obj->arr[(obj->ptail + obj->k) % (obj->k + 1)];
    //           obj->ptail - 1 + obj->k + 1
}

//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->phead == obj->ptail;
}

//判断队列是否满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    //当ptail下一个是phead时为满
    return (obj->ptail + 1) % (obj->k + 1) == obj->phead;
}

//队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    //先释放结构体中的元素
    free(obj->arr);
    obj->phead = obj->ptail = obj->k = 0;
    //最后释放结构体
    free(obj);
}

三、总结

对于这个题，我们采用了两种方法
用链表创建
用数组创建
这两种方法各有优势，用链表创建是在创建时会很麻烦要手动开辟一个循环链表，而数组就简单的多，但是当建立好链表后，后续的思路比较清晰没有那么多坑。
用数组创建的优势是可以下标访问，不用像链表那样还要循环遍历，降低了空间复杂度，而且数组在缓存利用率上有天然的优势。