数据结构（三）——基于数组的队列和循环队列
队Queue也是一个线性的存储结构，原则是先入先出（FIFO），区别于栈的先进后出。就类似与排队买票，先进入队列的就先买票出列；入队在一端操作（队尾），出队只能在另一端操作（队首）；
一个队列的基本操作就是入队，出队，获取队列大小，判断是否为空等等；这篇博客就是自己实现一个基于数组的队列和循环队列。
根据上面的分析，创建一个Queue接口，提供入队，出队，判空等操作：
public interface Queue<E> { //使用泛型使得队列可以存储各种类型的元素
void enqueue(E e); //入队（从队尾操作）
E dequeue(); //出队，返回出队的元素（从队首操作）
public int getSize(); //获取队列中元素的个数
boolean isEmpty(); //判断队列是否为空
E front(); //获取队首的元素
}下面，基于数组实现一个队列，来看看具体的方法怎么实现：
为了实现队列的可扩容，我们用于实现的数组是博客“数据结构（一）——封装动态数组”中的动态数组；具体的原理可以查看之前的那篇博客，这里只贴代码：
package com.itheima.array;
/**
* @author GuoBaoYu
* 使用泛型，可以存放任意类型的数据；
*/
public class Array<E> {
private E[] data; //内部是静态数组
private int size;
public Array(int capacity) {
data =(E[]) new Object[capacity];
size = 0;
}
/**
* 默认构造一个容量为10的数组
*/
public Array() {
this(10);
}
public int getCapacity(){
return data.length;
}
public boolean isEmpty(){
return size==0 ;
}
public int getSize(){
return size;
}
public void addLast(E element){
add(size, element);
}
public void addFirst(E element){
add(0,element);
}
//动态数组进行自动扩容和减少容量
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for(int i = 0; i < size;i++){
newData[i] = data[i];
}
data = newData;
}
/**
* @param index
* @param element
* 向指定的位置插入元素
*/
public void add(int index,E element){
if(size == getCapacity()){
// throw new IllegalArgumentException("AddLast is failed. Array is full.");
// 之前如果数组空间满了，抛出异常；现在进行扩容
int newCapacity = getCapacity()*2;
resize(newCapacity);
}
if(index < 0 || index > size){
throw new IllegalArgumentException("Argument index is illegal.index is required index >=0 and index <= size. ");
}
for(int i = size-1; i>=index; i--){
data[i+1] = data[i];
}
data[index] = element;
size++;
}
@Override
public String toString(){
StringBuilder builder = new StringBuilder();
builder.append(String.format("size = %d,capacity = %d\t", size,getCapacity()));
builder.append("[");
for(int i = 0; i < size; i++){
builder.append(data[i]);
if(i<size-1){
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
public E get(int index){
if(index >=size || index <0){
throw new IllegalArgumentException("Argument index is illegal.");
}
return data[index];
}
public void set(int index, E element){
if(index >=size || index <0){
throw new IllegalArgumentException("Argument index is illegal.");
}
data[index] = element;
}
public boolean contains(E element){
for(int i =0; i <size;i++){
if(data[i].equals(element)){
return true;
}
}
return false;
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size-1);
}
public int find(E element){
for(int i=0 ; i < size; i++){
if(data[i].equals(element)){
return i;
}
}
return -1;
}
//删除index位置的元素，并返回删除的元素的值
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed.index is an illegal argument.");
}
E element = data[index];
for(int i = index+1; i < size; i++){
data[i-1] = data[i];
}
size--;
if(size <= getCapacity() /4 && data.length/2 !=0){
resize(getCapacity()/2);
}
return element;
}
//删除第一个元素
public E removeFirst(){
return remove(0);
}
//删除最后一个元素
public E removeLast(){
return remove(size-1);
}
/**
* @param element
* @return
* 删除指定的数据
*/
public boolean removeElement(E element){
int find = find(element);
if(find!=-1){
remove(find);
return true;
}
return false;
}
}基于这个动态数组Array，实现一个队列：
package com.itheima.queue;
import com.itheima.array.Array;
public class ArrayQueue<E> implements Queue<E>{
private Array<E> array;
public ArrayQueue() {
array = new Array<E>(10);
}
//允许用户指定队列的容量
public ArrayQueue(int capacity){
array = new Array<E>(capacity);
}
public int getCapacity(){
return array.getCapacity();
}
//入队从数组的尾部操作
public void enqueue(E e) {
array.addLast(e); //入队时队列是否满，是否触发扩容操作在array.addLast()方法中考虑，所以这里直接调用；
}
//出队从数组的首部操作
public E dequeue() {
return array.removeFirst();
//出队时队列是否为空，是否触发缩容操作在array.removeFirst()方法中考虑，所以这里直接调用；
}
public int getSize() {
return array.getSize();
}
public boolean isEmpty() {
return array.isEmpty();
}
public E getFront() {
return array.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("ArrayQueue:");
res.append("front:[");
for(int i = 0; i < array.getSize();i++){
res.append(array.get(i));
if(i < array.getSize()-1){
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
}一个简单的测试：
上面的这种实现方式可以实现队列的动态扩容。但是依旧存在一定的缺陷：基于数组实现的队列，在进行出队操作时是调用了数组的removeFirst()方法，移除数组下标为0的元素，后面的每个元素向前移动一个位置，再进行size--,时间复杂度为o(n):过程如下：(第三步的size还要进行size--，标在4的位置，图截错了..这里声明一下)
为了解决这一点，在数组队列的基础上改进循环队列：基本思路是，在进行入队和出队操作(主要为了出队操作，不需要移动数组中元素的位置)，只需要维护队列（数组）的front（头）和tail（尾）的值，出队变成了O（1）的操作；
使用这种方式的另一个好处是构成了循环队列：什么是循环呢？
当出现下面这种存储情况时：
看起来不能再入队，tail不能再进行tail++了，因为tail指示的是队尾的后面第一个空的位置；但是实际上并不是不能再入队，而是可以把数组看成一个环，数组的前面还有空间，tail变为(tail+1)%8=0,tail指示在下标为0的空间！所以tail真正的操作应该是（tail+1）%数组长度；
以上就是循环队列的基本思想。下面是循环队列的实现，是基于普通静态数组的：
package com.itheima.queue;
import com.itheima.array.Array;
/**
* @author GuoBaoYu
*
* @param <E>
* 循环队列
*/
public class LoopQueue<E> implements Queue<E> {
private E[] data;
private int front,tail;
private int size; //队列的元素的个数
public LoopQueue(int capacity) {
//用户想要存放capacity个数据，根据之前的原理分析，为了防止判空和判满冲突，需要预留一个空间！
data = (E[]) new Object[capacity+1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue() {
this(10);
}
public int getCapacity(){
return data.length-1;
}
/* (non-Javadoc)
* @see com.itheima.queue.Queue#enqueue(java.lang.Object)
* 入队：
* 1.如果队满，调用resize()方法进行扩容；
* 2.把数据放入tail的位置
* 3.维护tail和size的值
*/
public void enqueue(E e) {
if( (tail+1)% data.length == front){ //数组判满；进行%data.length是为了让数组循环起来
//TODO 队列满了以后进行扩容
resize(getCapacity() *2);
}
data[tail] = e;
tail = (tail+1)%data.length;
size++;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for(int i= 0; i < size;i++){
newData[i] = data[(front+i)% data.length];
}
data = newData;
front = 0;
tail = size;
}
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
}
E ret = data[front];
data[front] = null;
front = (front+1)%data.length;
size--;
if(size==getCapacity()/4 && getCapacity()/2!=0){
resize(getCapacity()/2);
}
return ret;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return front == tail;
}
public E front() {
if(isEmpty()){
throw new IllegalArgumentException("No elements in this queue.");
}
return data[front];
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("LoopQueue:");
res.append("front:[");
for(int i = front; i != tail;i = (i+1)%data.length){
res.append(data[i]);
if((i +1)% data.length != tail){
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
}一个简单的测试：
可以看到，出队的结果和使用removeFirst()达到的效果是一样的；
代码中值得注意的地方在于自动调整容量的resize()方法的实现和遍历队列的toString()方法：
在进行入队时，先根据之前分析的条件，(tail+1)%data.length==front判断是否队满，如果队满进行扩容。扩容的思路是将队列数组的大小调整为原来的2倍，当然也可以是1.5倍，看个人了；当需要扩容时，数组中的元素可能是这样存放的：
要想调整为容量为16的数组，我们完全没有必要还按这个顺序存放数据，可以像下面这样：
相当于在扩容的同时对数据进行了整理；还是创建一个两倍大小+1的数组，新数组的0位置对应原来的front，1对应front+1......
位置都存在front的偏移，所以有了resize()代码中：把data[(front+i)%data.length]赋值给newData[i]
最后更改data的指向，维护新数组的front和tail的值；如此实现扩容！当然resize()方法只是传递了一个新的容量作为参数；在enqueue()方法中传递一个大的新容量作为扩容；当出队很多数据后可以传递一个小的容量，进行缩容。
在覆盖toString()方法时，和之前的从下标为0开始遍历不同，变为从front开始遍历，直到遍历到最后一个元素，也需要注意一下。
以上就是一个循环队列的实现，把出队操作的时间复杂度降为了O（1）。
下面通过测试比较一下两种队列的效率：
可以看到对10000个数据的出队，LoopQueue循环队列的效率远高于ArrayQueue；