循环队列的顺序存储结构Java

大家好，又见面了，我是你们的朋友全栈君。

循环队列的顺序存储结构

在上次，我们讲到的是，队列的顺序存储结构也是由ArrayList实现的，从此就可以看出，在入队时候的时间复杂度为O(1)，但是在出队时候的时间复杂度为O(n)，这是因为，每次在出队后要将数组后面的有效元素前移一位。
所以，这里就会用到循环队列，显然，这种队列也是顺序存储结构，在这个循环队列中也会去实现接口Queue。
首先，我们要想到的是如何将一般的队列改变为循环队列。

• 和之前一般的队列的顺寻存储结构一样，默认初始数组容量为10（循环队列的数组实际容量为11，这是因为要空出一个数组空间，至于为什么，将在后面进行解释）；
• 定义一个头指针front和尾指针rear，用这两个指针去维护循环队列中元素的入队和出队；
• 定义一个size，去统计当前循环队列中的元素的有效个数；

现在，我们先看一下循环队列是如何入队和出队的。
初始时：

入队一个元素：

出队一个元素：

这样，front和rear指针就可以很轻松的去维护循环队列的入队和出队，并且它们的时间复杂度都为O(1)，但是要注意特殊情况的存在，比如，当数组的0角标没有元素但7角标也有元素的时候，rear指针就要移动到front的前面，如下图所示：

这个时候很明显，循环队列已经满了，所以我们就会想到，如何判断循环队列什么时候为满，什么时候为空？

其实，利用它的周期性可以很明显的得出结论：
队列为满的时候：(rear+1)%n == front; (n为数组的总长度；如上图：(0+1)%8等于1也就是等于front指向的位置)
如果出现这种情况，如下图示：

因为，我们每次的出队，front指针都会向后面移动一位，而rear指针是不会移动的，如果我们将上图的两个元素全部出队列，会出现这样的情况：

很显然，判断队列为空也为:(rear+1)%n == front;

这样的话就会重复，所以这就是我们之前说，为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
因此，判断队列为空的条件就为：rear == front;
如下图：

如上图，我们现在入队一个元素：

每次在入队的时候，将rear指针始终指向队尾最后一个元素的空间。
并且每次入队的时候，rear的变化也要注意：rear = (rear+1)%n;

说了这么多，我们就来看一下具体的代码实现。
首先和我们之前一样，先来看看它的顺序存储结构：

package DS01.动态数组;
import java.util.Iterator;
/** * @author 七夏 * @param <E> * @version 1.0 * 循环队列:如果我们默认创建一个为容量为10的的循环队列时，我们须在该循环队列容量的基础上再加1， * 这是为了在判断循环队列是否为空时，起到作用 * * 循环队列为满时的条件：(rear+1)%data.length 等于 front * 循环队列为空时的条件：front == rear * 元素每次进队时，队头front每次更新：front = (front+1)%data.length * 元素每次出队时，队尾rear每次更新：rear = (rear+1)%data.length * 函数 E getRear() 在获取队尾元素时的方法为：data[(rear-1+data.length)%data.length] */
public class ArrayQueueLoop<E> implements Queue<E>{ 
   
	//设置默认初始容量（后面会加1）
    private static final int DEFAULT_CAPACITY = 10;
    private E[] data;
    private int front;
    private int rear;
    private int size;

    public ArrayQueueLoop(){ 
   
        this(DEFAULT_CAPACITY);
    }
    public ArrayQueueLoop(int capacity){ 
   
        if(capacity <= 0){ 
   
            throw new IllegalArgumentException("指定容量错误："+capacity);
        }
        data = (E[])(new Object[capacity+1]);//加1，让数组多出一个空间
        front = 0;
        rear = 0;
        size = 0;
    }
}

现在，看一下入队代码：

	@Override
    public void enqueue(E e) { 
   
    	//判断队列是否满
        if((rear + 1)%data.length == front){ 
   
            //扩容
            resize(data.length*2-1);
        }
        data[rear] = e;
        //更新rear队尾指针位置
        rear = (rear+1)%data.length;
        size++;
    }

出队：

	@Override
    public E dequeue() { 
   
        if(isEmpty()){ 
   
            throw new IllegalArgumentException("队列为空");
        }
        //拿出对头元素
        E res = data[front];
        //更新front对头指针位置
        front = (front+1)%data.length;
        size--;
        //缩容
        if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){ 
   
            resize(data.length/2+1);
        }
        return res;
    }

扩容：

	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;
            //如果p指针等于rear队尾指针时，结束循环
            if(p == rear){ 
   
                break;
            }
        }
        /* 上述while循环相当于下述for循环 for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){ newData[i] = data[p]; } */
        front = 0;
        rear = size;
        data = newData;
    }

实现iterator方法：
和之前都大致类似，在这里，我们在内部类中首先定义一个p指针，用来遍历循环队列，在hasNext函数中，只要p指针不等于rear队尾指针，说明该循环队列“尚不为空”（当前指向的元素后面还有元素）；next函数中，创建res变量获取当前元素，之后将更新p指针的位置，最终返回res。

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

        @Override
        public E next() { 
   
            E res = data[p];
            //更新p指针的指向位置
            p = (p+1)%data.length;
            return res;
        }
    }

其他方法：
在这些方法中，我们要注意toString方法和getRear方法，在getRear方法中，我们直接返回data[(rear-1+data.length)%data.length]。

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

    @Override
    public boolean isEmpty() { 
   
        return size == 0 && front == rear;
    }
    @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[DEFAULT_CAPACITY+1]);
        front = 0;
        rear = 0;
        size = 0;
    }
    @Override
    public String toString() { 
   
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),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();
    }