LeetCode 622. 设计循环队列
LeetCode 622. 设计循环队列
LeetCode ：https://leetcode-cn.com/problems/design-circular-queue/
题目描述：设计你的循环队列实现。
循环队列是一种线性数据结构，其操作表现基于 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
提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
解题思路：
队列的存储结构中使用的最多的是循环队列。
循环队列包括两个指针， front 指针指向队头元素， rear 指针指向队尾元素的下一个位置。
队列为空的判断条件是：front == rear
队列满的判断条件是：(rear+1) % maxsize == front
队列长度的计算公式：(rear-front+maxsize) % maxsize
正常情况下，当 front == rear 是队列有可能是满也有可能是空，为了区分这两种情况，我们需要在front前添加一个闲置单元。
1、Java 代码实现
用一个数组array来实现，成员变量还有4个整形变量：
1）size 用来记录环形队列的最大长度
2）front 用来记录当前队首位置
3）rear 用来记录当前队尾位置
4）count 用来记录队列中当前有多少个元素
往环形队列中插入元素是往队尾的后一个位置插入元素，当队尾在数组的最右边时要插入元素的话，就在数组的最左边插入元素，之后队尾也就在数组的最左边了。在环形队列中删除元素是删除队首的元素，随着不断地删除元素，队首会从数组的最左边一直到最右边，然后又回到最左边。将队首的位置移动之后，就完成了删除的操作，原来位置的值不用修改。返回队首元素就是返回front位置的值。返回队尾元素就是返回rear位置的值。判断队列的空和满就是判断count的值是多大就可以了。
class MyCircularQueue {
int[] array;
int size = 0; // 队列总大小, size = k
int count = 0; // 队列元素个数, 默认 0
int front = 0; // 队列头的下标, 默认 0
int rear = 0; // 队列尾的下标, 默认 0
public MyCircularQueue(int k) {
array = new int[k]; // array.length = size = k
size = k;
count = 0;
front = 0;
rear = 0;
}
public boolean enQueue(int value) {
if(isFull()) return false; // 队列满了, 就不再存了
array[rear] = value;
rear = (rear + 1) % size; // 队列尾移到下一个下标位置
count++;
return true;
}
public boolean deQueue() {
if(isEmpty()) return false; // 空队列, 没元素出队
front = (front + 1) % size; // 队头加1, 队首元素并没删
count--; // 元素个数减1, 表示少了1个元素, 实际并没删除队首元素
return true;
}
public int Front() {
if(isEmpty()) return -1;
return array[front];
}
public int Rear() {
if(isEmpty()) return -1;
// return array[(size+rear-1)%size]; // 队尾总是指向下一个下标 Success
if(rear == 0) return array[size-1];
return array[rear-1];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == size;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
2、Java 改进版（删除了队列大小 size）
class MyCircularQueue {
int[] array;
int count = 0; // 队列元素个数, 默认 0
int front = 0; // 队列头的下标, 默认 0
int rear = 0; // 队列尾的下标, 默认 0
public MyCircularQueue(int k) {
array = new int[k]; // array.length = k
count = 0;
front = 0;
rear = 0;
}
public boolean enQueue(int value) {
if(isFull()) return false; // 队列满了, 就不再存了
array[rear] = value;
rear = (rear + 1) % array.length; // 队列尾移到下一个下标位置
count++;
return true;
}
public boolean deQueue() {
if(isEmpty()) return false; // 空队列, 没元素出队
front = (front + 1) % array.length; // 队头加1, 队首元素并没删
count--; // 元素个数减1, 表示少了1个元素, 实际并没删除队首元素
return true;
}
public int Front() {
if(isEmpty()) return -1;
return array[front];
}
public int Rear() {
if(isEmpty()) return -1;
// return array[(array.length+rear-1)%array.length]; // 队尾总是指向下一个下标 Success
return rear == 0 ? array[array.length-1] : array[rear-1];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == array.length;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
3、Python 代码实现
class MyCircularQueue(object):
def __init__(self, k):
"""
:type k: int
"""
self.array = [None] * (k+1) // 循环队列多加了一个间隔元素
self.maxSize = k + 1
self.front = 0
self.rear = 0
def enQueue(self, value):
"""
:type value: int
:rtype: bool
"""
if self.isFull(): return False
self.array[self.rear] = value
self.rear = (self.rear + 1) % self.maxSize
return True
def deQueue(self):
"""
:rtype: bool
"""
if self.isEmpty(): return False
self.front = (self.front + 1) % self.maxSize
return True
def Front(self):
"""
:rtype: int
"""
if self.isEmpty(): return -1
return self.array[self.front]
def Rear(self):
"""
:rtype: int
"""
if self.isEmpty(): return -1
return self.array[(self.rear-1+self.maxSize) % self.maxSize]
def isEmpty(self):
"""
:rtype: bool
"""
return self.front == self.rear
def isFull(self):
"""
:rtype: bool
"""
return self.front == ((self.rear + 1) % self.maxSize)
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
4、Java代码改进（循环队列满了后，依然可以放入元素，删除元素的实现）
/*
* 实现一个循环队列，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
* 应支持如下操作：
* 1、MyCircularQueue(k): 构造器，设置队列长度为 k 。
* 2、Front: 从队首获取元素。如果队列为空，返回 -1 。
* 3、Rear: 获取队尾元素。如果队列为空，返回 -1 。
* 4、enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
* 5、deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
* 6、isEmpty(): 检查循环队列是否为空。
* 7、isFull(): 检查循环队列是否已满。
*
* 2021.02.02 in tencent.com
*/
// Java
class MyCircularQueue {
// FIFO
// array = [] // 队列为空
// array = [1,2,3,,] // 队列未满
// array = [1,2,3,4,5] // 队列满了
// array = [6,7,3,4,5] // 满了还插入
// array = [6,7,,1,2] // 满了出队列
int[] array;
int SIZE = 0;
int count = 0;
int front = 0;
int rear = 0;
public MyCircularQueue(int k) {
array = new int[k];
SIZE = k; // 记录队列的总大小
count = 0; // 记录队列里的元素个数, 队列满了则 count = k, 出队列则 count = count-1
front = 0;
rear = 0;
}
// 插入实现1: 循环队列满了后, 再次插入新元素, 直接存入front位置
public boolean enQueue(int value) {
if(count < SIZE) { // 队列未满
array[rear] = value;
count++; // 队列未满时, count一直累加
}
if(front == rear) { // 队列已满
array[front] = value;
front = (front + 1) % SIZE;
}
rear = (rear + 1) % SIZE; // 队列满了后, rear = front 实际指向同一个下标了(故不能通过 front==rear判断队列是空或满)
return true;
}
// 插入实现2: 循环队列满了后, 再次插入新元素, 直接存入rear位置
public boolean enQueue2(int value) {
array[rear] = value;
count++;
if(count >= SIZE) { // 已满
front = (rear + 1) % SIZE;
count = SIZE; // 队列满了后, count一直等于最大值SIZE
}
rear = (rear + 1) % SIZE; // 队列满了后, rear = front 实际指向同一个下标了(故不能通过 front==rear判断队列是空或满)
return true;
}
// public boolean deQueue() {
if(isEmpty()) return -1;
front = (front + 1) % SIZE;
count--;
return true;
}
// public int Front() {
if(isEmpty()) return -1;
return array[front];
}
// public int Rear() {
if(isEmpty()) return -1;
// return rear == 0 ? array[SIZE-1] : array[rear-1]; // Success
rear = (SIZE+rear-1) % SIZE; // Success
return array[rear]
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == SIZE;
}
}
注意点：
1）队列满了后，依然可以插入循环队列，enQueue() 和 enQueue2() 实现
2）判断队列是否满了，有两个方式：
方式一：引入一个计数器 count，每次入队列、出队列，都计数count，判断 count == 0 或 count == SIZE
方式二：队列多加一个空元素，隔离队首和队尾，当 (rear + 1) % SIZE == front，则表示队列满了
5、思考题
上面的循环队列，改成 "约瑟夫环"，又该如何实现呢？
参考推荐：
Python 常用加密算法 base64, md5, sha1
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2021-02-05 17:45:16
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！