622. 设计循环队列

题目描述：

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

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

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

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

测试用例：

示例 1:

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 的范围内；
• 请不要使用内置的队列库。

---

解题分析及思路：

本题可以采用数组 🔗来进行解答.

可以将所有的数据保存在一个数组里面，为保证队列的正常出队与入队，我们需要知道当前队列队头和队尾的位置，当然可以采用双指针的方式，一个指针指向队头，一个指针指向队尾。

• 当执行入队的时候可以将尾指针往后移动。
• 当执行出队的时候可以将头指针往前移动

但是无法预知当前队列是否为空或者满，当然可以使用k + 1的长度来放宽队头与队尾的位置，不过此法需要过度注意一些细节，可以采取别的方法来代替此举。

若想知道队头和队尾的位置，除了两个指针的形式，我们可以保存队列队头firstIndex的位置以及当前队列的元素个数num，不就可以知道队尾的位置了吗

定义队列结构，nums保存所有的元素，firstIndex为队列的队头位置，num代表队列元素的个数。

type MyCircularQueue struct {
	nums       []int
	firstIndex int
	num        int
}

EnQueue入队函数，判断当前队列个数num与数组nums个数是否相等，不相等则入队并返回true，否则返回false

同理，DeQueue出队函数判断当前队列个数num是否大于零（是否为空队列），大于零则出队并返回true，否则返回false

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.num == len(this.nums) {
		return false
	}
	this.nums[(this.firstIndex+this.num)%len(this.nums)] = value
	this.num++
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if this.num > 0 {
		this.firstIndex = (this.firstIndex + 1) % len(this.nums)
		this.num--
		return true
	}
	return false
}

此题需要注意的是队头位置加上队列长度不可越出数组nums长度，取余即可

复杂度：

• 时间复杂度：O(1)
• 空间复杂度：O(k)

执行结果：

• 执行用时：8 ms, 在所有 Go 提交中击败了96.65%的用户
• 内存消耗：6.6 MB, 在所有 Go 提交中击败了96.23%的用户