数据结构入门——大师：queue(二) LoopQueue

1.什么是循环队列

由于队列会出队入队，因此我们需要利用好队列出队的空间，因此我们需要设置循环队列

2.循环队列的实现

循环队列和之前简单队列不同，因此我们需要从头开始实现

 /**
     * 定义队首和队尾
     */
    private int front,tail;
     //底层还是数组
    private E[] data;
    private int size;

• 循环队列有个队首和队尾，队首指向队列的头，队尾指向队列尾部，队尾到数组的最后时候，再入队，会指向数组头部
• 循环队列需要浪费一个空间：由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==tail来判别队列是"空"还是"满"。

解决这个问题的方法至少有三种：

① 另设一[布尔变量]以区别队列的空和满；

② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满
（注意：tail所指的单元始终为空）；

③使用一个计数器记录队列中元素的总数（即队列长度）。

2.循环队列的初始化操作

    public LoopQueue(int capacity){
        //循环队列需要浪费一个空间
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }
}

3.入队

  @Override
    public void enqueue(E e) {
        //判断队满
        // ,那么 tail+1=front才能代表队满，为了使得两个不能超过data.length所以需要%一下
        if((tail + 1) % data.length == front ){
            //需要扩容
            resize(getCapacity() * 2);
        }
        //数据放到队尾
        data[tail] = e;
        //本来是tail = tail +1即可，因为到数组长度的最大值需要重头再来，所以需要% 重新开始计
        tail = (tail + 1)%data.length;
        size ++;
    }
}

入队就是如果tail + 1=front 进行扩容，如果不是那么就将元素放在tail位置，然后tail+1指向后一个空的地方

4.队列扩容

 private void resize(int newCapacity){
        E[] newData =(E[]) new Object[newCapacity + 1];
        //本质上%data.length 反正数组越界，因为这个值肯定是小于data.length的，
        // 当其 大于等于6时候会从0重新计数，而循环队列原数组的数据也是这样的
        for(int i = 0; i < size; i ++){
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        tail = size;
        front = 0;
    }
}

扩容的结果就是原来队列的头是新数组的头部，原来队列尾在旧的数组

5.出队

 @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        E ret = data[front];
        data[front] = null;
        front =( front + 1) % data.length;
        size --;
        //出队，那就要缩容
        if(size == getCapacity() / 2 && getCapacity() / 2 != 0){
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("queue is empty");
        }
        return data[front];
    }

出队就是将front元素抛出去，然后置空，front后移一位，然后进行缩容，本质上属于饿汉式缩容，因为size一减少就会去缩容