近期在面试找工作的小伙伴们很多啊，我周围就有好几个认识的朋友在找工作，于是我突发奇想在开了一个面试题精选的专栏，主要会关注一些算法题、设计题，次要会补充一些java面试相关的题(比较本博主是java出身)。其实在此之前已经写过一些相关的文章了，已经整理到专栏里的，后续会持续更新，希望对大家有所帮助，有兴趣的旁友可以关注下。
今天分享的面试题是循环队列，我对这道题记忆深刻，因为我在14年参加来校招面试的时候，二面面试官就问了这道题，当时我没有完全答上来(不过面试官居然给我过了)，后来我当面试官的时候也拿这道题考过别人，也没遇到能彻底答出来的。不巧，前两天又在看别人文章的时候遇到了循环队列，索性就来自己写一下。
有时候虽然面试官表面上是考一道很简单的题，但背后却想着暗度陈仓、凭空……(对不起放错了)。比如这道循环队列，面试官一上来可能不会直接问循环队列，而是让你实现一个有界队列，如果你没一下子想到最优的方案，不要慌还有机会，一名合格的面试官会尝试引导你的思考，比如让你做做复杂度分析，分析下优缺点，最后编码实现下。就拿这题来说，首先考察了基本的数据结构队列，再考察算法复杂度分析的能力，还考察下你归纳总结的能力、表达能力，最后考察下编码能力。
有界队列：指存储有限个元素的队列，当队列满之后就不能往其中添加了。与之相对的有无界队列，无界队列可以无限的往其中添加元素，在实际使用中往往要注意避免OOM。
回到面试题上，给你一个有界队列的接口定义，你来实现一个有界队列，接口如下：
public interface BoundedQueue {
boolean add(int e);
int peek();
int poll();
boolean isEmpty();
boolean isFull();
}
我面过的一个候选人，当时他给出下面的实现方案。
public class MyBoundedQueue implements BoundedQueue {
private int tail = 0;
private int[] arr;
public MyBoundedQueue(int cap) {
this.arr = new int[cap];
}
@Override
public boolean add(int e) {
if (isFull()) {
return false;
}
arr[tail++] = e;
return true;
}
@Override
public int peek() {
if (isEmpty()) {
return -1;
}
return arr[0];
}
@Override
public int poll() {
if (isEmpty()) {
return -1;
}
int res = arr[0];
for (int i = 0; i < tail-1; i++) {
arr[i] = arr[i+1];
}
tail--;
return res;
}
@Override
public boolean isEmpty() {
return tail == 0;
}
@Override
public boolean isFull() {
return tail == arr.length;
}
}
看起来思路很清晰，是实现了有界队列的接口。他的思路是有个指针tail一直指向队尾第一个空位置，如果有插入就插到tail的位置，tail并往后移动。然后根据tail的具体位置来判断队列是满是空，入队如下图示。
我们来重点看下出队，他每次出队都是出第0位的元素，为了准确性必须保证arr[0]始终是队头，所以在每次出队的时候都将后面的所有元素往前移动一位，导致出队的时间复杂度变成了O(n)，如下图所示。
有没有办法做到不用把后面的元素往前移动呢，其实有的，我们只需要用一个head指针指向队列的第一个可用元素前的空位即可，如下图。
如果队列里的元素不动，那我们就得让队头指针(head)动起来，每删除poll()一次，队头指针就往后移动一次，因为只需要移动指针，所以时间复杂度是O(1)。但是我们又有了新的问题，队头指针前面的那些空位置我们如何再利用起来？这里我们就引出了循环队列，你把上图想象成一根软管，可以掰弯然后首尾相连，如下图。
当然这里我们使用数组实现了，只能做到逻辑上首尾相连，插入时如果插到了最后一格就直接跳回到第一格子。但如果你用链表实现的话，就很容易实现首尾相连了。接下来就是难点了，上面的都比较容易理解，但好多人就是不知道如何判定队列是空是满(我当年面试的时候也是这种情况)。你有没有发现上文中我头指针和尾指针都是指向空的，不是说我喜欢这样，而是为了方便判断空和满。 注意看上文中的图，我只在头指针和尾指针之间的空格处存东西，所以当队列是空的时候，循环队列按顺时针方向，头指针在前尾指针在后，且二者相邻，如下图。
如果队列满，首尾指针是指向同一个位置，如下图。
所有的问题我们都通过图示的方式展示清楚了，下面我给出我用数组实现的代码。
public class CircularBoundedQueue implements BoundedQueue {
private int head = 0;
private int tail = 1;
private int[] arr;
public CircularBoundedQueue(int cap) {
this.arr = new int[cap+1];
}
@Override
public boolean add(int e) {
if (isFull()) {
return false;
}
arr[tail] = e;
tail = next(tail);
return true;
}
@Override
public int peek() {
if (isEmpty()) {
return -1;
}
return arr[head+1];
}
@Override
public int poll() {
if (isEmpty()) {
return -1;
}
return arr[head = next(head)];
}
@Override
public boolean isEmpty() {
return tail == next(head);
}
@Override
public boolean isFull() {
return head == tail;
}
private int next(int cur) {
return (cur+1)%arr.length;
}
}
用单链表实现的代码如下：
public class CircularBoundedQueue2 implements BoundedQueue {
private class Node {
int value;
Node next;
}
private Node head;
private Node tail;
public CircularBoundedQueue2(int cap) {
Node p = new Node();
head = p;
for (int i = 0; i < cap; i++) {
Node newNode = new Node();
p.next = newNode;
p = p.next;
}
p.next = head; // 链表最末尾节点next指向头部
tail = head.next;
}
@Override
public boolean add(int e) {
if (isFull()) {
return false;
}
tail.value = e;
tail = tail.next;
return true;
}
@Override
public int peek() {
if (isEmpty()) {
return -1;
}
return head.next.value;
}
@Override
public int poll() {
if (isEmpty()) {
return -1;
}
head = head.next;
return head.value;
}
@Override
public boolean isEmpty() {
return tail == head.next;
}
@Override
public boolean isFull() {
return head == tail;
}
}
