循环队列的实现

文章目录

• 循环队列的概念
• 循环队列的实现
• • 循环队列的判空和判满
  • ��表or数组

    循环队列的概念

    设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

    • 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

      循环队列的实现

      首先我们需要明确循环队列需要实现的功能：

      • MyCircularQueue(k): 构造器，设置队列长度为 k 。
      • Front: 从队首获取元素。如果队列为空，返回 -1 。
      • Rear: 获取队尾元素。如果队列为空，返回 -1 。
      • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
      • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
      • isEmpty(): 检查循环队列是否为空。
      • isFull(): 检查循环队列是否已满。

        循环队列的判空和判满

        对上述功能加以思考后我们就发现了循环队列和普通队列区分开来的一个难点：如何判断循环队列是空的还是满的。

        以队列长度为4的循环队列举例，当我们刚刚创建队列时队头队尾的位置如下：

        • 此时我选择是将rear指向队尾的下一个数据，不难发现当循环队列为空的时候，front==rear；

          然后当我们enQueue 1，2，3，4；

          这时我们尴尬地发现，front还是等于rear，也就是说我们不能通过front和rear的值来判断循环队列是空的还是满的。或者，当front等于rear时我们随机给出空和满中的一个答案。

          显然这个并不能算是解决方法的解决方法会导致循环队列的功能实现出BUG。

          因此，我又想出了以下两个解决方案

        • 首先，也是最容易想到的，直接在循环队列的结构体里面加上size来记录元素个数，那不就从根源上解决了问题了吗？
        • 其次，我们上述讨论front和rear不能判空和满，原因是空和满时，front和rear都是相等的。如果我们稍稍改变循环队列的长度，使得循环队列满的时候，front！=rear，那么问题不久迎刃而解了吗？事实上我们可以构建循环队列时申请k+1个空间，那么当rear的下一个是front，这时循环队列就是满的。

          接下来我以第一种方法来实现循环队列/=。

          链表or数组

          很多人看到循环队列时都会想到用循环链表来实现，诚然我也是这么想的，但随之问题接踵而至。譬如求队尾元素，时间复杂度为O（n），而用数组实现的话，时间复杂度为O（1）.除此之外，销毁循环链表也是相较数组实现麻烦。

          因此我这里考虑用数组来实现循环链表。

          • 首先我们优先实现循环链表的判空和判满：

            typedef struct {    int*arr;    int front;    int rear;    int k;    int size;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->size==0;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    return obj->size==obj->k;}

            • 再在此基础上实现其他功能：

              MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));    obj->rear=obj->front=obj->size=0;    obj->k=k;    obj->arr=(int*)malloc(k*sizeof(int));    return obj;    }bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    if(myCircularQueueIsFull(obj))        return false;    obj->arr[obj->rear]=value;    obj->size++;    obj->rear=(obj->rear+1)%obj->k;    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return false;    obj->front=(obj->front+1)%obj->k;    obj->size--;    return true;}int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->arr[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->arr[(obj->rear-1+obj->k)%obj->k];}void myCircularQueueFree(MyCircularQueue* obj) {    free(obj->arr);    free(obj);}

              值得注意的是在上述代码实现过程中，我们巧妙地运用了取模的方式来简化了特殊情况的判断。这也是我们在实现循环队列时所能提升的能力之一。