老师，这是我按自己的方法实现的循环队列，麻烦老师看一下，这样写有没有什么问题

Question

我将tail设置成了指向最后一个元素，并根据front和tail计算出了size

public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front;//指向第一个元素
    private int tail;//指向最后一个元素
    public LoopQueue(){
        data=(E[]) new Object[10];
        front=-1;
        tail=-1;
    }
    public LoopQueue(int capacity){
        data=(E[]) new Object[capacity];
        front=-1;
        tail=-1;
    }
    @Override
    public void enqueue(E e) {
	    //扩容
        if (((tail+1)%getCapacity())==front){
            resize(getCapacity()*2);
        }
        //如果数组为空则需要将front和tail指向第一个元素也就是下标0
        if(front==-1){
            front++;
            data[front]=e;
            tail++;
        }else{
            tail=(tail+1)%getCapacity();
            data[tail]=e;
        }
    }

    private void resize(int capacity) {
        E[] newDate=(E[]) new Object[capacity];

        for (int i=0;i<getSize();i++){
            newDate[i]=data[(i+front)%getCapacity()];
        }

        tail=getSize()-1;
        front=0;
        data=newDate;
    }

    @Override
    public E dequeue() {
        if(getSize()/getCapacity()==4){
            resize(getCapacity()/2);
        }
        E e;
        /*
         *如果front==tail，数组只有一个元素，取出后数组为空，此时将front和tail设为-1表示数组为空
         *
         */
        if(front==tail){
            e=data[front];
            data[front]=null;
            front=-1;
            tail=-1;
        }else{
             e=data[front];
            data[front]=null;
            front++;
        }
        return e;
    }

    @Override
    public E getFront() {
        return data[front];
    }

    @Override
    public int getSize() {
        /**
         * 如果front和tail等于-1则数组为空
         * front等于tail则表明只有一个元素
         * front小于tail则
         *      通过用容量减去front得到front左边的元素个数，再用tail+1得到右边的元素个数，两则相加得到最终的size
         * front 大于 tail则
         *      用tail减去front+1得到size
         */
        int size=0;
        if (front==-1&&tail==-1){
            return 0;
        }
        if(front>tail){
            size=(getCapacity()-front)+(tail+1);
        }else if(front<tail){
            size=(tail-front)+1;
        }else if(front==tail){
            size=1;
        }
        return size;
    }

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

Answer 1

liuyubobobo 2021-06-28 07:41:46

我就不给你测试啦。你可以使用课程中的方式，自己设计测试用例进行简单的测试。

另外，一个好的测试方式是，将你的数据结构直接应用到具体问题中。比如队列可以用来完成树的广度优先遍历，在后续课程中会介绍树的广度优先遍历，你可以使用自己的队列去完成相应的任务，来看具体结果。Leetcode 上也有很多需要队列才能完成的问题，你也可以尝试使用自己写的数据结构为基础，去完成这些问题，看是否有问题。这样相当于借助 Leetcode 的测试用例来测试我们自己的数据结构。

P.S. 课程中的大多数数据结构，我都经过了 Leetcode 上问题的测试：）

继续加油！：）

Answer 2

提问者 散落满天的回忆 2021-06-27 21:51:50

不好意思老师，代码出了一点bug，这是修正后的代码

public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front;//指向第一个元素
    private int tail;//指向最后一个元素
    public LoopQueue(){
        data=(E[]) new Object[10];
        front=-1;
        tail=-1;
    }
    public LoopQueue(int capacity){
        data=(E[]) new Object[capacity];
        front=-1;
        tail=-1;
    }
    @Override
    public void enqueue(E e) {
	    //扩容
        if (((tail+1)%getCapacity())==front){
            resize(getCapacity()*2);
        }
        //如果数组为空则需要将front和tail指向第一个元素也就是下标0
        if(front==-1){
            front++;
            data[front]=e;
            tail++;
        }else{
            tail=(tail+1)%getCapacity();
            data[tail]=e;
        }
    }

    private void resize(int capacity) {
        E[] newDate=(E[]) new Object[capacity];

        for (int i=0;i<getSize();i++){
            newDate[i]=data[(i+front)%getCapacity()];
        }

        tail=getSize()-1;
        front=0;
        data=newDate;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
        throw new IllegalArgumentException("The queue is empty");
        }
        
        E e;
        /*
         *如果front==tail，数组只有一个元素，取出后数组为空，此时将front和tail设为-1表示数组为空
         *
         */
        if(front==tail){
            e=data[front];
            data[front]=null;
            front=-1;
            tail=-1;
        }else{
             e=data[front];
            data[front]=null;
            front=(front+1)%getCapacity();
        }
        if(getSize()/getCapacity()==4){
            resize(getCapacity()/2);
        }
        return e;
    }

    @Override
    public E getFront() {
        return data[front];
    }

    @Override
    public int getSize() {
        /**
         * 如果front和tail等于-1则数组为空
         * front等于tail则表明只有一个元素
         * front小于tail则
         *      通过用容量减去front得到front左边的元素个数，再用tail+1得到右边的元素个数，两则相加得到最终的size
         * front 大于 tail则
         *      用tail减去front+1得到size
         */
        int size=0;
        if (front==-1&&tail==-1){
            return 0;
        }
        if(front>tail){
            size=(getCapacity()-front)+(tail+1);
        }else if(front<tail){
            size=(tail-front)+1;
        }else if(front==tail){
            size=1;
        }
        return size;
    }

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