LeetCode662.设计循环队列||4种方法实现

目录

题目

 思路1(链表)

代码

思路2(数组)

 代码

---

题目

题目要求的队列需要实现的功能有
①Creat---设置队列长度
②Front---获取队列头
③Rear---获取队列尾
④en----插入元素
⑤de---删除元素
⑥empty---判空
⑦full---判满

 思路1(链表)

🔍普通队列长度没有限制，循环队列的长度是初始化时被规定的。

❓ 请思考：普通的队列我们可以通过链表来实现，那么环状的队列能否继续通过链表实现呢？
💡答案：可以，需要将链表设计为循环链表。🔑解析：这样可以通过最后一个链表节点找到第一个链表节点。

❓请思考：怎么通过循环链表构造循环队列呢？
构造出一个循环链表，定义front指向队列头，定义back指向队列尾后一个空间。规定front==back时队列为空。

 🔨插入4个元素

 ❗注意：此时不能继续插入元素了，如果在插入元素，back接下来就和front一样，而这是我们之前定义队列为空的条件。也就是说：在前提条件front==back表示队列为空时，循环链表有5个节点，只能存储4个数据，推而广之，如果想要队列中存放k个数据，那么循环链表需要定义(k+1)个节点。

🔨删除元素：删除队列头只需要将链表头删即可。

 ❗注意：🚫头删不要将需要删除数据所在的空间释放，这样可能会导致下次插入元素时非法访问内存空间。头删只需要让front指向下一个空间即可。front和back之间的数据才是队列中的元素。

❓请思考：怎么找到队列尾？
💡解决方案：
①循环队列结构中添加一个preTail指针，指向链表尾节点的前一个结点。
②遍历整个链表，在链表尾节点的前一个节点时停止遍历。
③使用双向循环链表。

三种方案大同小异，这里不在赘述

代码

💬方案1代码

//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;Qnode* preTail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->size = 0;q->capacity = k;//创建第一个空间q->head = (Qnode*)malloc(sizeof(Qnode));q->tail = q->head;q->preTail = NULL;Qnode* cur = q->head;//创建k个节点while (k--){cur->next = (Qnode*)malloc(sizeof(Qnode));cur = cur->next;}cur->next = q->head;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj->tail->next == obj->head)return false;//插入数据obj->tail->val = value;obj->preTail = obj->tail;obj->tail = obj->tail->next;obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj->size == 0)return false;//链表头删(不要销free节点的空间)obj->head = obj->head->next;obj->size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj->size == 0 ? -1 : obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {return obj->size == 0 ? -1 : obj->preTail->val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k+1个节点int cnt = obj->capacity + 1;Qnode* cur = obj->head;while (cnt--){Qnode* tmp = cur->next;free(cur);cur = tmp;}free(obj);
}

💬方案2代码

//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->size = 0;q->capacity = k;//创建第一个空间q->head = (Qnode*)malloc(sizeof(Qnode));//tail==front，初始化为空q->tail = q->head;Qnode* cur = q->head;//创建k个节点while (k--){cur->next = (Qnode*)malloc(sizeof(Qnode));cur = cur->next;}cur->next = q->head;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj->size == obj->capacity)return false;//插入数据obj->tail->val = value;obj->tail = obj->tail->next;obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj->size == 0)return false;//链表头删(不要销free节点的空间)obj->head = obj->head->next;obj->size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj->size == 0 ? -1 : obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->size == 0)return -1;//遍历链表Qnode* cur = obj->head;while (cur->next != obj->tail){cur = cur->next;}return cur->val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k+1个节点int cnt = obj->capacity + 1;Qnode* cur = obj->head;while (cnt--){Qnode* tmp = cur->next;free(cur);cur = tmp;}free(obj);
}

💬方shu'zu案3代码

//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;struct Qnode* pre;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->size = 0;q->capacity = k;//创建第一个空间q->head = (Qnode*)malloc(sizeof(Qnode));//tail==front，初始化为空q->tail = q->head;Qnode* cur = q->head;//创建k个节点while (k--){Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));cur->next = newnode;newnode->pre = cur;cur = cur->next;}cur->next = q->head;q->head->pre = cur;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj->size == obj->capacity)return false;//插入数据obj->tail->val = value;obj->tail = obj->tail->next;obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj->size == 0)return false;//链表头删(不要销free节点的空间)obj->head = obj->head->next;obj->size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj->size == 0 ? -1 : obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {return obj->size == 0 ? -1 : obj->tail->pre->val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k+1个节点int cnt = obj->capacity + 1;Qnode* cur = obj->head;while (cnt--){Qnode* tmp = cur->next;free(cur);cur = tmp;}free(obj);
}

思路2(数组)

❓先思考：通过数组实现的环形队列有哪些成员？
🔑数组、队列头下标、队列尾下标、队列元素个数、队列最大容量。

我们规定头下标和尾下标相等时队列为空。
📚来看数组模拟循环队列示意图(队列的容量是5)：
①🔨队列为空

 ②🔨入队

 ③🔨出队

 

 ④🔨入队​​​​​​​

❗注意：从上述过程中可以观察到：在物理结构中 ，队尾可能在队头的前面也可能在队头后面。
🔺思维导图：

 代码

typedef struct {int* a;//a指向数组int front;//头下标int back;//尾下标int size;//队列元素个数int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q->a = (int*)malloc(sizeof(int) * (k + 1));q->size = 0;q->capacity = k;q->front = q->back = 0;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列已满if (obj->size == obj->capacity)return false;obj->a[obj->back] = value;obj->back++;//尾下标越界归0if (obj->back > obj->capacity){obj->back = 0;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->size == 0)return false;obj->front++;//头下标越界归0if (obj->front > obj->capacity)obj->front = 0;obj->size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj->size == 0 ? -1 :  obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {//空队列if (obj->size == 0)return -1;if (obj->back == 0){return obj->a[obj->capacity];}return obj->a[obj->back - 1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}