近期在面试找工作的小伙伴们很多啊，我周围就有好几个认识的朋友在找工作，于是我突发奇想在CSDN开了一个面试题精选的专栏，主要会关注一些算法题、设计题，次要会补充一些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; } }
