622. 设计循环队列
一、题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
二、示例
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
三、使用顺序表实现
使用顺序表实现的循环队列：
循环队列的结构定义：
1.首先顺序表的大小固定，从上面接口定义可以看到，顺序表能存储元素个数为队列的长度k，这可以通过malloc申请固定长度空间实现。
2.其次队列需要队头和队尾，需要front和rear两个索引。
队空条件：
front == rear
队满条件：
我们发现此时队满的条件也为 front == rear，这就无法区分是队空还是队满。
为此，我们可以采用以下两个解决方案：
1.预留一个空间用来区分队空和队满：
// 队空
front == rear
// 队满
rear + 1 == front
2.增加一个size变量记录队列中元素个数：
// 队空
size == 0
// 队满
size == k
这里我们采用第一种方式，采取牺牲一个存储空间的方法，来区分队空和队满。此时实现队列所用的顺序表的长度应该为 k+1。
同时采用第一种方法时，在计算队列中元素的个数时需要计算给出：
(rear + k + 1 - front) % (k + 1)
3.1 循环队列的结构定义
下面给出队列的结构定义：
typedef struct {
int front;
int rear;
int k;
int* a;
} MyCircularQueue;
3.2 循环队列初始化与销毁
初始化：
这里rear表示队尾元素下一个位置。
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
// 采用牺牲一个存储空间的方法区分队空和队满
obj->a = (int*)malloc(sizeof(int) * (k + 1));
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
销毁：
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
3.3 循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
3.4 循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
3.5 入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
// 如果队满返回false
if (myCircularQueueIsFull(obj))
return false;
// 入队就是顺序表尾插
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k + 1);
return true;
}
3.6 出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
// 队空不能出队
if (myCircularQueueIsEmpty(obj))
return false;
// 出队就是顺序表头删 头指针加1即可
obj->front++;
obj->front %= (obj->k + 1);
return true;
}
3.7 队首元素
int myCircularQueueFront(MyCircularQueue* obj) {
// 返回队首元素保证队列不为空
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
3.8 队尾元素
从初始化可以看出rear指向队尾元素的下一个位置，所以rear应该先减1，才是在顺序表中的索引。又由于rear可能会为0，因此需要先加 k+1使rear指向表后，然后再减1使rear指向表中最后一个元素位置。可以写成：
rear + (k + 1） - 1 = rear + k
再考虑到其余普通情况防止顺序表越界，还需要队该数取余：文章来源：https://www.toymoban.com/news/detail-447923.html
(rear + k) % (k + 1)
便有以下返回队尾元素的代码：文章来源地址https://www.toymoban.com/news/detail-447923.html
int myCircularQueueRear(MyCircularQueue* obj) {
// 返回队尾元素保证队列不为空
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
完整接口实现
typedef struct {
int front;
int rear;
int k;
int* a;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
// 采用牺牲一个存储空间的方法区分队空和队满
obj->a = (int*)malloc(sizeof(int) * (k + 1));
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
// 如果队满返回false
if (myCircularQueueIsFull(obj))
return false;
// 入队就是顺序表尾插
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
// 队空不能出队
if (myCircularQueueIsEmpty(obj))
return false;
// 出队就是顺序表头删 头指针加1即可
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->rear + obj->k) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
到了这里，关于【刷题】622. 设计循环队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
