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

来源:3-8 数组队列和循环队列的比较

twodog二狗

2019-04-21

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

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老师能够指出我的问题,并且希望老师能够跟我说一下为什么要使用循环队列。

写回答

1回答

liuyubobobo

2019-04-21

可以的。我在这个课程的补充代码中,提供了一个版本,不使用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),再回顾一下:)


继续加油!:)

0
3
liuyubobobo
回复
twodog二狗
循环的意义就是将队列在数组这种数据结构上,将各个复杂度优化为O(1)级别。不然的话,我不知道你有什么思路,做到这一点?:)
2019-04-22
共3条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程