LeetCode | 622. 设计循环队列

OJ链接

思路：

• 我们这里有一个思路：

• 插入数据，bank往后走

  

  • 删除数据，front往前走

    

    • 再插入数据，就循环了

      

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

        怎么判断满，怎么判断空？

        这样是不是比较难

        ---

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

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

          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;
            }
            

            判空

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

              

              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;
                    //可以这样写
                    //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);
                }