Leetcode:622. 设计循环队列 题解【具详细】

比眉伴天荒 2024-02-18 13:31 96阅读 0赞

目录

一、题目：

二、思路详解：

1.循环队列的存储定义

2.循环队列的创建

3.循环队列的判空与判断情况

(1) 循环队列的判空:

(2) 循环队列的判满

4.循环队列元素的插入

5.循环队列元素的删除

6.获取队头元素

7.获取队尾元素

8.循环队列释放

三、完整代码展示：

一、题目：

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

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

你的实现应该支持如下操作：

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

难度：中等

题目链接：622. 设计循环队列

示例：

  1. MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
  2. circularQueue.enQueue(1);  // 返回 true
  3. circularQueue.enQueue(2);  // 返回 true
  4. circularQueue.enQueue(3);  // 返回 true
  5. circularQueue.enQueue(4);  // 返回 false，队列已满
  6. circularQueue.Rear();  // 返回 3
  7. circularQueue.isFull();  // 返回 true
  8. circularQueue.deQueue();  // 返回 true
  9. circularQueue.enQueue(4);  // 返回 true
  10. circularQueue.Rear();  // 返回 4

题目解析：就是根据题中给的接口进行函数的实现。要求我们实现一个循环队列。

用心阅读下方会有很大的收获。

ce38ff812bd64551b17e39a745edfea6.png

二、思路详解：

1.循环队列的存储定义

首先我们需要定义出一个循环队列的存储定义，这里采用的是使用动态数组来进行模拟循环队列，根据题中给出的接口返回类型，我们可以知道循环队列的数据类型为int 。

其次，还需定义两个记录数组的下标，一个记录队列的队头，另一个记录队列的队尾(也就是指向要入队的下一个元素的位置)。另外还要提供一个表示要存储数据的具体个数。

如图：

f6aa082e61cc4d5bb3fd0320f8e85b1a.png

代码：

  1. //采用动态数组的形式来模拟循环队列
  2. typedef struct {
  3.     int* a;     //指向数组
  4.     int front;  //队头
  5.     int tail;   //队尾
  6.     int k;      //数据个数
  7. } MyCircularQueue;

2.循环队列的创建

循环队列的创建，先使用malloc进行创建一个 循环队列空间

接着根据给的数据个数k让指针a指向一个动态数组，在分别对front,tail,k进行初始化，注意tail = 0表示要存放的下一个数据元素的位置，对动态数组a开辟空间的时候要多开辟一个空间，避免假溢出的现象。最后一定要返回之前创建的循环队列。

代码：

  1. //创建长度为k的循环队列
  2. MyCircularQueue* myCircularQueueCreate(int k) {
  3.     //使用动态内存函数来申请内存
  4.     //这里多申请一个空间的目的是防止假溢出
  5.     //使用malloc创建一个循环队列
  6.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  7.     //为循环队列里面的指针a ,让a指向一个长度为k+1的数组
  8.     obj->a= (int*)malloc(sizeof(int)*(k+1));
  9.     obj->front = 0; //队头从数组的下标0开始
  10.     obj->tail = 0; //队尾指向下一个元素
  11.     obj->k = k; //队列的长度为k
  12.     return obj;
  13. }

物理存储情况，如图：

3643680cd2cb47f499827c11095e148c.png

但是我们一般会到其循环的逻辑结构，逻辑存储，如图：

f1653e9e5f3b4fe28c685f1077d5fda5.png

3.循环队列的判空与判断情况

循环队列的插入和删除是不可避免的，当这之前就需要先完成判和判满的接口。注意：一定要把判空和判满的函数实现放在队列插入和删除函数实现的前面。

(1) 循环队列的判空:

根据函数的返回类型是bool，空我们就返回true ,否则返回false。

  • isEmpty(): 检查循环队列是否为空。

因为这里采取的是通过动态数组来模拟循环队列，所以队列空的条件就是当front == tail 的时候，此时的循环队列就是空的。

如图：

224fcc843e4e479fa3d50b8b7429579e.png

代码：

  1. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  2.     //队空，就是队头与队尾相同时
  3.     return obj->front == obj->tail;
  4. }
(2) 循环队列的判满

同样根据函数的返回类型是bool，空我们就返回true ,否则返回false。

  • isFull(): 检查循环队列是否已满。

什么时候会满呢？当(tail+1)%(k+1) == front,就是队尾下标加1模开辟空间的个数

可能很多会对为什么要多开辟一个空间，原因就在这：对于队列的判满的情况，

当没有创建的额外空间，队列只有数据10 和 11 的情况下，

e3fea062cf774e1ea6384bcd1b3c8b63.png

像上图就是假溢出现象，这个队列并没有满。

总的来说：

循环队列为了区分队列的空和满，需要额外增加一个空的元素来占据队列的一个位置，这样队列满的状态就可以通过头尾指针相邻且不重合来判断，而不会出现头尾指针重合但队列实际上并不满的情况。同时循环队列需要对头尾指针进行模运算，如果没有额外的空间，那么当队列最后一个元素占据了数组最后一个位置时，下一个元素就会从数组的第一个位置开始，这样就无法正确进行模运算，而增加一个空的元素可以解决这个问题。

代码：

  1. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  2.    return (obj->tail+1)%(obj->k+1) == obj->front;
  3. }

25633c90880241de823397b33006b8a1.png

4.循环队列元素的插入

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

插入前判断是否满，满就返回false,接着就是数据的插入，插入后，对tail下标进行取模(因为是反复利用原来的空间，还有就是避免溢出)，插入成功就返回true。

代码：

  1. //插入元素
  2. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  3.     //插入元素前先进行判断是否满
  4.     if(myCircularQueueIsFull(obj))
  5.     {
  6.         return false;
  7.     }
  8.     //插入元素使用尾插
  9.     obj->a[obj->tail] = value;
  10.     obj->tail++;
  11.     //避免tail的下标越界
  12.     obj->tail%=(obj->k+1);
  13.     return true;
  14. }

5.循环队列元素的删除

删除前，要进行判断是否为空。队头减一，进行删除，删除后取模。

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

代码：

  1. //出队
  2. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  3.     //删除元素队列不能为空
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return false;
  7.     }
  8.     //出队，头删
  9.     obj->front++;
  10.     obj->front%=(obj->k+1);
  11.     return true;
  12. }

6.获取队头元素

获取前进行判断，是否为空。

Front: 从队首获取元素。如果队列为空，返回 -1

代码：

  1. //获取队首元素
  2. int myCircularQueueFront(MyCircularQueue* obj) {
  3.     //队列不能为空
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1; //队空返回-1
  7.     }
  8.     return obj->a[obj->front];
  9. }

7.获取队尾元素

获取前进行判断，是否为空。

Rear: 获取队尾元素。如果队列为空，返回 -1

代码：

  1. //获取队尾元素
  2. int myCircularQueueRear(MyCircularQueue* obj) {
  3.     //队列不能为空
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1; //队空返回-1
  7.     }
  8.     //注意当tail = 0的情况
  9.     return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
  10. }

解释一下 上述最后一行代码：

重点：

首先tail是指向要存放下一个元素的位置，找队尾元素时，tail要进行-1。

因为数组下标最小是从0开始的，当tail ==0且队列不为空的情况下，上方代码obj->tail-1,就会造成0-1 == -1的情况。上方采用(obj->tail - 1+ obj->k+1)%(obj->k+1)就可以完美的避免，当然

其实可以写成

  1. int myCircularQueueRear(MyCircularQueue* obj) {
  2.     if(myCircularQueueIsEmpty(obj))
  3.         return -1;
  4.     // return obj->a[(obj->tail-1 + obj->k+1)%(obj->k+1)];
  5.     if(obj->tail == 0)
  6.     {
  7.         return obj->a[obj->k];
  8.     }
  9.     else
  10.     {
  11.         return obj->a[obj->tail-1];
  12.     }
  13. }

8.循环队列释放

因为用malloc开辟的动态内存空间，为了避免内存泄漏，我们还要释放内存。注意释放的顺序。

代码：

  1. void myCircularQueueFree(MyCircularQueue* obj) {
  2.     free(obj->a);
  3.     free(obj);
  4. }

三、完整代码展示：

代码：

  1. //采用动态数组的形式来模拟循环队列
  2. typedef struct {
  3.     int* a;     //指向数组
  4.     int front;  //队头
  5.     int tail;   //队尾
  6.     int k;      //数据个数
  7. } MyCircularQueue;
  9. //创建长度为k的循环队列
  10. MyCircularQueue* myCircularQueueCreate(int k) {
  11.     //使用动态内存函数来申请内存
  12.     //这里多申请一个空间的目的是防止假溢出
  13.     //使用malloc创建一个循环队列
  14.     MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  15.     //为循环队列里面的指针a ,让a指向一个长度为k+1的数组
  16.     obj->a= (int*)malloc(sizeof(int)*(k+1));
  17.     obj->front = 0; //队头从数组的下标0开始
  18.     obj->tail = 0; //队尾指向下一个元素
  19.     obj->k = k; //队列的长度为k
  20.     return obj;
  21. }
  22. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  23.     //队空，就是队头与队尾相同时
  24.     return obj->front == obj->tail;
  25. }
  27. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  28.    return (obj->tail+1)%(obj->k+1) == obj->front;
  29. }
  31. //插入元素
  32. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  33.     //插入元素前先进行判断是否满
  34.     if(myCircularQueueIsFull(obj))
  35.     {
  36.         return false;
  37.     }
  38.     //插入元素使用尾插
  39.     obj->a[obj->tail] = value;
  40.     obj->tail++;
  41.     //避免tail的下标越界
  42.     obj->tail%=(obj->k+1);
  43.     return true;
  44. }
  46. //出队
  47. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  48.     //删除元素队列不能为空
  49.     if(myCircularQueueIsEmpty(obj))
  50.     {
  51.         return false;
  52.     }
  53.     //出队，头删
  54.     obj->front++;
  55.     obj->front%=(obj->k+1);
  56.     return true;
  57. }
  59. //获取队首元素
  60. int myCircularQueueFront(MyCircularQueue* obj) {
  61.     //队列不能为空
  62.     if(myCircularQueueIsEmpty(obj))
  63.     {
  64.         return -1; //队空返回-1
  65.     }
  66.     return obj->a[obj->front];
  67. }
  69. //获取队尾元素
  70. int myCircularQueueRear(MyCircularQueue* obj) {
  71.     //队列不能为空
  72.     if(myCircularQueueIsEmpty(obj))
  73.     {
  74.         return -1; //队空返回-1
  75.     }
  76.     //注意当tail = 0的情况
  77.     return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
  78. }
  80. void myCircularQueueFree(MyCircularQueue* obj) {
  81.     free(obj->a);
  82.     free(obj);
  83. }
  85. /**
  86.  * Your MyCircularQueue struct will be instantiated and called as such:
  87.  * MyCircularQueue* obj = myCircularQueueCreate(k);
  88.  * bool param_1 = myCircularQueueEnQueue(obj, value);
  90.  * bool param_2 = myCircularQueueDeQueue(obj);
  92.  * int param_3 = myCircularQueueFront(obj);
  94.  * int param_4 = myCircularQueueRear(obj);
  96.  * bool param_5 = myCircularQueueIsEmpty(obj);
  98.  * bool param_6 = myCircularQueueIsFull(obj);
  100.  * myCircularQueueFree(obj);
  101. */

发表评论

表情：
评论列表 （有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode622设计循环队列

    使用数组完成对循环队列的设计 空闲单元法：进行队列是否为空，是否为满的情况； front : 指向队列中第一个元素 rear : 指向队列中最后一个元素的

    傷城~傷城~/ 0 赞/ 218 阅读