数据结构之循环队列（改进版队列）-----重点、难点

一、为什么需要引入循环队列？

1、队列顺序存储结构的特点

注意：如上Front指针永远不会动，永远指向第一个元素，Rear指针永远指向最后一个元素。出队时所有元素都会向左移动。

2、队列顺序存储结构的弊端

（1）队列的顺序存储结构本身是由ArrayList实现的

（2）在数据元素入队的时候，相当于在ArrayList表尾添加元素

（3）在数据元素出队的时候，相当于在ArrayList表头删除元素

（4）很明显，入队的时间复杂度O(1)，出队的时间复杂度O(n)

（5）线性表增删数据元素时间复杂符都是O(n)，但是这个是按平均算的

（6）队列的出队时间复杂度O(n)，可不是按平均算的，因为每次出队都是O(n)

因为队列出现以上不足的地方所以需要对其弊端进行避免！而我们所设计的循环队列就规避了这些弊端！

二、循环队列出生过程

1、优化第一步

优化操作：能否让队头指针和队尾指针一样随着数据元素的变化而移动？
如上述图示：入队和出队操作都是O(1)

弊端：
1）Rear指针不能再继续后移了

2）浪费了一些空间

2、优化第二步

优化操作：当队尾或队头指针到达尾部时，如需后移可重新指向表头
弊端:
队列满的条件 (Rear+1)%n==Front

队列空的条件 (Rear+1)%n==Front
注意：队列满和空的条件时一样的 !

3、优化第三步

优化操作：将一个空间预留出来不存任何元素，尾指针始终指向这个null空间
队列满的条件 (Rear+1)%n==Front

队列空的条件 Rear==Front
这样满和空的条件就不冲突了 !

注意：因为Rear指针需要占用一个空间所以，创建数组、扩容和缩容时数组都应该预留一个位置出来。

三、代码实现

Queue.java:

package DS01.动态数组;

public interface Queue<E> extends Iterable<E>{
    //获取队列中元素的个数
    int getSize();
    //判断队列是否为空
    boolean isEmpty();
    //入队一个元素
    void enqueue(E e);
    //出队一个元素
    E dequeue();
    //获取队头
    E getFront();
    //获取队尾
    E getRear();
    //清空队列
    void clear();
}

ArrayLoopQueue.java:

package DS01.动态数组;

import java.lang.reflect.Array;
import java.util.Iterator;

//循环队列
public class ArrayQueueLoop<E> implements Queue<E> {
    private E[] data;
    private int front;
    private int rear;
    private int size;

    public ArrayQueueLoop(){
        data= (E[]) (new Object[11]);//因为有一个空的空间
        front=0;
        rear=0;
        size=0;
    }

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

    @Override
    public boolean isEmpty() {
        return size==0&&front==rear;
    }

    @Override
    public void enqueue(E e) {
        if((rear+1)%data.length==front){
            resize(2*data.length-1);
        }
        data[rear]=e;
        rear=(rear+1)%data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列空");
        }
        E ret=data[front];
        front=(front+1)%data.length;
        size--;

        if(size<=(data.length-1)/4&&(data.length-1)/2>=10){
            resize((data.length-1)/2+1);
        }

        return ret;
    }
    private void resize(int newLen){
        E[] newData= (E[]) (new Object[newLen]);
        int p=front;
        int i=0;
        while(true){
            newData[i]=data[p];
            i++;
            p=(p+1)%data.length;
            if(p==rear){
                break;
            }
        }
        front=0;
        rear=size;
        data=newData;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public E getRear() {
        if(isEmpty()){
            throw new IllegalArgumentException("队列为空");
        }
        return data[(rear-1+data.length)%data.length];
    }

    @Override
    public void clear() {
        data= (E[]) (new Object[11]);//因为有一个空的空间
        front=0;
        rear=0;
        size=0;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append(String.format("ArrayQueueLoop: %d/%d\n",size,data.length-1));
        sb.append('[');
        if(isEmpty()){
            sb.append(']');
        }else{
            for(int i=front;i!=rear;i=(i+1)%data.length){
                sb.append(data[i]);
                if((i+1)%data.length==rear){
                    sb.append(']');
                }else{
                    sb.append(',');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayQueueLoopIterator();
    }
    private class ArrayQueueLoopIterator implements Iterator{
        int p=front;
        @Override
        public boolean hasNext() {
            return p!=rear;
        }

        @Override
        public Object next() {
            E ret=data[p];
            p=(p+1)%data.length;
            return ret;
        }
    }
}

测试类：

package DS01.动态数组;

public class TestArrayQueueLoop {
    public static void main(String[] args) {
        ArrayQueueLoop<Integer> loop=new ArrayQueueLoop<>();
        System.out.println(loop);
        for(int i=1;i<=15;i++){
            loop.enqueue(i);
        }
        System.out.println(loop);
        for(int i=1;i<=10;i++){
            loop.dequeue();
        }
        System.out.println(loop);

        for(Integer i:loop){
            System.out.print(i+" ");
        }


    }
}