bobo老师，我有关于循环队列的问题，想请教下您

Question

bobo老师，您好！我在慕课网上学习了您的课程《玩转数据结构》受益匪浅，真心地向您说声感谢！我正在学习您的课程《学习算法思想 修炼编程内功》，同时，也在复习《玩转数据结构》的课程。在复习到循环队列时，我产生了小小的问题，如果仅仅用front和tail来维护队列，不使用循环的机制，是否可以呢？：

public class MyQueue<E> implements Queue<E> {
    private int front;
    private int tail;
    private E[]data;
    public MyQueue(int capacity){
        data = (E[])new Object[capacity+1];
    }
    public MyQueue(){
        this(10);
    }
    @Override
    public int getSize(){
        return tail-front;
    }
    @Override
    public boolean isEmpty(){
        return front==tail;
    }
    @Override
    public E getFront(){
        return data[front];
    }
    private void resize(int newCapacity){
        E[]newData = (E[])new Object[newCapacity+1];
        for(int i=0;i<(tail-front);i++){
            newData[i] = data[front+i];
        }
        data = newData;
        tail = tail - front;
        front = 0;
    }
    @Override
    public void enqueue(E e){
        if(tail == data.length-1)
            resize((tail-front)*2);

        data[tail] = e;
        tail++;
    }

    @Override
    public E dequeue(){
        E ret = data[front];
        // Loitering Object
        data[front] = null;
        front++;
        if(((tail-front)==(data.length-1)/4) && (data.length-1)/2!=0)
            resize((data.length-1)/2);

        return ret;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("MyQueue size=%d,capacity=%d\n",tail-front,data.length-1));
        stringBuilder.append("front:[");
        for(int i=front;i<tail;i++){
            stringBuilder.append(data[i]);
            if((i+1)!=tail){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]tail");
        return stringBuilder.toString();
    }
}

对上述代码，我同ArrayQueue和LoopQueue一同做过测试，时间我觉得同LoopQueue差不多，但是我总是觉得自己的代码有一些问题，希望bobo老师能够指出我的问题，并且希望老师能够跟我说一下为什么要使用循环队列。

Answer 1

liuyubobobo 2019-04-21 16:18:32

可以的。我在这个课程的补充代码中，提供了一个版本，不使用size，只是用front和tail，可以参考：）

传送门：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/03-Stacks-and-Queues/Optional-02-Loop-Queue-without-Size-Member/src

为什么使用循环队列？因为循环队列的各个操作复杂度是O(1)啊！而我们在上一小节所实现的数组队列，不能做到这一点，出队操作是O(n)，再回顾一下：）

继续加油！：）

• 提问者 twodog二狗 #1

  谢谢老师的回答，我知道队列的dequeue操作是O(n)的时间复杂度，如果仅仅使用front和tail变量维护，不用“循环”这种思想也是可以的吗？我知道bobo老师在课程中提到过，不用size变量仅用tail和front就可以实现size，但是我的疑惑是抛开“循环的机制”，不也是可以将队列优化成一个各个操作复杂度为O(1) 的算法吗？循环的意义究竟在什么地方呢？感谢bobo老师百忙之中的解答~

• 提问者 twodog二狗 #2

  非常感谢！

• liuyubobobo 回复 提问者 twodog二狗 #3

  循环的意义就是将队列在数组这种数据结构上，将各个复杂度优化为O(1)级别。不然的话，我不知道你有什么思路，做到这一点？：）