一、题目
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
-
MyCircularQueue(k):构造器，设置队列长度为 k 。 -
Front: 从队首获取元素。如果队列为空，返回 -1 。 -
Rear: 获取队尾元素。如果队列为空，返回 -1 。 -
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 -
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 -
isEmpty(): 检查循环队列是否为空。 -
isFull(): 检查循环队列是否已满。
二、示例
2.1> 示例：
提示：
- 所有的值都在
0至1000的范围内；- 操作数将在
1至1000的范围内；- 请不要使用内置的队列库。
三、解题思路
3.1> 头尾节点指针+元素计数器
当我们看完这道题的描述之后，如果有的同学们曾经读过ArrayBlockingQueue源码或者看过我之前发过的一篇文章《不了解SynchronousQueue？那ArrayBlockingQueue和LinkedBlockingQueue不会也不知道吧？》，那么就会很容易的想到解题思路并完成代码实现。只是对于ArrayBlockingQueue来说，由于它要处理多线程对资源的抢占，所以加入了ReentrantLock，并且通过lockInterruptibly()这种可接受被打断的方式进行了加锁操作。除了加入锁机制，还加入了Condition实例，通过调用其await()/awaitNanos()和signal()方法实现当队列满了时，再放入元素需要等待，以及当队列空的时候，要获取元素需要等待，以及当满队列有空余空间时，通过signal()方法解除插入时等待的线程，以及当空队列有元素插入进来之后，通过signal()方法通知获取元素等待的线程解除等待。
如果大家对ArrayBlockingQueue感兴趣的话，可以阅读一下我上面提到的文章，也可以自己看一下相关源码，代码逻辑并不复杂，也是很好理解的。好了，我们现在把话题拉回来，来看一下这道算法题的解题思路是怎么样的。
首先，通过题目中的描述，我们要实现一个循环队列，即：一个结合了队列+循环的数据结构。如下图所示：
那么对于底层用于存储的数据结构，我们选择数组即可，因为构造函数会传入环形缓冲器能承载元素的个数，所以，我们通过构造函数来初始化底层数组——int[] element。
那么既然要实现“环形”能力，就需要我们创建两个指针，分别为：head指针和tail指针。通过这两个指针，我们可以满足存取操作，即：向环形缓冲器存入元素的时候，将元素插入到tail指针位置——element[tail] = “待插入元素”；向环形缓冲器获取元素的时候，获取head指针位置的元素——return element[head]；
那如何快速的知道环形缓冲器是空的状态或是满的状态呢？我们可以创建一个int类型的count变量，当向环形缓冲器插入元素的时候，执行count++；如果向环形缓冲器获取元素的时候，执行count--；那么count就可以代表环形缓冲器中保存的元素个数，当count等于0时，说明里面是空的，而当count等于element.length的时候，就说明是满的。
由于是环形结构，所以当head == element.length时，要重置head为0，而同样tail也是这样操作的。
插入元素操作步骤如下图所示：
获取/删除元素操作步骤如下图所示：
四、代码实现
4.1> 头尾节点指针+元素计数器
class MyCircularQueue {
private int[] element;
private int head = 0, tail = -1, count = 0;
public MyCircularQueue(int k) {
element = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) return false; // 队列满了
tail += 1;
if (tail == element.length) tail = 0;
element[tail] = value;
count++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false; // 队列空了
element[head++] = -1;
if (head == element.length) head = 0;
count--;
return true;
}
public int Front() {
if (count == 0) return -1; // 队列空了
return element[head];
}
public int Rear() {
if (count == 0) return -1; // 队列空了
return element[tail];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == element.length;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
