面试题精选:循环队列

有界队列：指存储有限个元素的队列，当队列满之后就不能往其中添加了。与之相对的有无界队列，无界队列可以无限的往其中添加元素，在实际使用中往往要注意避免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;
    }
}