相关推荐recommended
LeetCode | 622. 设计循环队列
作者:mmseoamin日期:2023-12-25

LeetCode | 622. 设计循环队列

OJ链接

LeetCode | 622. 设计循环队列,在这里插入图片描述,第1张

思路:

  • 我们这里有一个思路:

  • 插入数据,bank往后走

    LeetCode | 622. 设计循环队列,在这里插入图片描述,第2张

    • 删除数据,front往前走

      LeetCode | 622. 设计循环队列,在这里插入图片描述,第3张

      • 再插入数据,就循环了

        LeetCode | 622. 设计循环队列,在这里插入图片描述,第4张

        • 那上面这个方法可行吗?

          怎么判断满,怎么判断空?

          这样是不是比较难


          • 我们下面有一个好的方法,就是多开一个空间

            下面是我们的结构体的定义

            typedef struct {
                int* a;
                int front;
                int back;
                int k;
            } MyCircularQueue;
            

            初始化

            • 这里的初始化就是给a空间开了k+1个大小
              MyCircularQueue* myCircularQueueCreate(int k) {
                  MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
                  obj->a = (int*)malloc(sizeof(int) * k + 1);
                  obj->front = obj->back = 0;
                  obj->k = k;
                  return obj;
              }
              

              判空

              • 我们这里先来看判空
              • 当我们的头尾相等了就说明是空

                LeetCode | 622. 设计循环队列,在这里插入图片描述,第5张

                bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
                    return obj->front == obj->back;
                }
                

                判满

                LeetCode | 622. 设计循环队列,在这里插入图片描述,第6张

                bool myCircularQueueIsFull(MyCircularQueue* obj) {
                    return (obj->back + 1) % (obj->k + 1) == obj->front;
                }
                

                入队

                LeetCode | 622. 设计循环队列,在这里插入图片描述,第7张

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

                出队

                LeetCode | 622. 设计循环队列,在这里插入图片描述,第8张

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

                取队头

                • 这里很简单直接取对头,但是要判断是否为空,空了就不能取了~~
                  int myCircularQueueFront(MyCircularQueue* obj) {
                      if(myCircularQueueIsEmpty(obj))
                          return -1;
                      return obj->a[obj->front];
                  }
                  

                  取队尾

                  LeetCode | 622. 设计循环队列,在这里插入图片描述,第9张

                  int myCircularQueueRear(MyCircularQueue* obj) {
                      if(myCircularQueueIsEmpty(obj))
                          return -1;
                      //可以这样写
                      //if(obj->back == 0)
                      	//return obj->a[obj->k];
                      //else
                      	//return obj->a[obj->back-1];
                      return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
                  }
                  

                  销毁队列

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

                  完整的代码实现

                  typedef struct {
                      int* a;
                      int front;
                      int back;
                      int k;
                  } MyCircularQueue;
                  MyCircularQueue* myCircularQueueCreate(int k) {
                      MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
                      obj->a = (int*)malloc(sizeof(int)*(k+1));
                      obj->front = obj->back = 0;
                      obj->k = k;
                      return obj;
                  }
                  bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
                      return obj->front == obj->back;
                  }
                  bool myCircularQueueIsFull(MyCircularQueue* obj) {
                      return (obj->back+1)%(obj->k+1) == obj->front;
                  }
                  bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
                      if(myCircularQueueIsFull(obj))
                          return false;
                      obj->a[obj->back] = value;
                      obj->back++;
                      obj->back %= (obj->k+1);
                      return true;
                  }
                  bool myCircularQueueDeQueue(MyCircularQueue* obj) {
                      if(myCircularQueueIsEmpty(obj))
                          return false;
                      ++obj->front;
                      obj->front %= (obj->k+1);
                      return true;
                  }
                  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->back-1+obj->k+1)%(obj->k+1)];
                  }
                  void myCircularQueueFree(MyCircularQueue* obj) {
                      free(obj->a);
                      free(obj);
                  }