一.简介：

由于数组队列，每次出队都是一个O(n)级是操作，所以使用数组队列并不是一个很好的选择，这里提供一种更高效的队列实现，循环队列。

二.基本结构：

I@XG9N8$`$Q`3MS{6U0GI83.png

每次出队操作，不去移动数组元素，而是保留空位，由front指向队首，tail指向队尾也就是下一个元素入队时的位置，在数组队列中当tail指向最后一个位置时，就需要扩容了，但在循环队列中，由于出队操作时，保留了空位，整个队列变成了环形，tail指向第一个空位，直到（tail+1）%capacity=front时，队列才是真正的满了，这里之所以保留一个空位，是为了和tail==front时，队列为空，进行区分。

三.代码实现

/**
 * 循环队列
 */
public class LoopQueue<E> implements Queue<E> {

  private E[] data;
  //front 队首，tail 队尾
  private int front, tail;
  private int size;

  public LoopQueue(int capacity) {
    //因为有一个位置将空出来，所以当用户想创建容积为capacity的队列，实际上是创建一个capacity+1的的队列
    data = (E[]) new Object[capacity + 1];
    front = 0;
    tail = 0;
    size = 0;
  }

  public LoopQueue() {
    this(10);
  }

  /**
   * 入队
   */
  @Override
  public void enqueue(E e) {
    //动态扩容，这里使用getCapacity()是为了拿到实际容量
    if ((tail + 1) % data.length == front) {
      resize(2 * getCapacity());
    }
    data[tail] = e;
    tail = (tail + 1) % data.length;
    size++;
  }

  /**
   * 现在出队时间复杂度变成了O(1)
   */
  @Override
  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;
  }

  @Override
  public E getFront() {
    if (isEmpty()) {
      throw new IllegalArgumentException("cannot dequeue from an empty queue!");
    }
    return data[front];
  }

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

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

  public void resize(int capacity) {

    E[] newData = (E[]) new Object[capacity + 1];
    for (int i = 0; i < size; i++) {
      newData[i] = data[(front + i) % data.length];
    }
    front = 0;
    data = newData;
    tail = size;
  }

  /**
   * 循环队列又有个元素是不会使用的，所以元素实际容量为data.length--1
   */
  public int getCapacity() {
    return data.length - 1;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(String.format("Queue:size=%d,capacity=%d", size, getCapacity()));
    builder.append("   front[");
    for (int i = front; i != tail; i = (i + 1) % data.length) {
      builder.append(data[i]);
      if ((i + 1) / data.length != tail) {
        builder.append(",");
      }
    }
    builder.append("]tail");
    return builder.toString();

  }

  public static void main(String[] args) {
    LoopQueue<Integer> queue = new LoopQueue<>();
    for (int i = 0; i < 10; i++) {
      queue.enqueue(i);
      System.out.println(queue);

      if (i % 3 == 2) {
        queue.dequeue();
        System.out.println(queue);
      }
    }
  }
}

四.循环队列与数组队列效率对比

1.测试代码

public class Main {

  public static void main(String[] args) {
    int opCount = 100000;
    ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
    double time1 = testQueue(arrayQueue, opCount);
    System.out.println("ArrayQueue ,time:" + time1 + " s");
    LoopQueue<Integer> loopQueue = new LoopQueue<>();
    double time2 = testQueue(loopQueue, opCount);
    System.out.println("LoopQueue ,time:" + time2 + " s");


  }

  public static double testQueue(Queue<Integer> q, int opCount) {
    long start = System.nanoTime();
    for (int i = 0; i < opCount; i++) {
      Random random = new Random();
      q.enqueue(random.nextInt());
    }
    for (int i = 0; i < opCount; i++) {
      Random random = new Random();
      q.dequeue();
    }
    long end = System.nanoTime();
    return (end - start) / 10e9;
  }
}

2.测试结果

ArrayQueue ,time:0.3034960087 s
LoopQueue ,time:0.0018054093 s

五.结论

虽然数组队列结构简单，但是由于出队操作每一次都要移动队列中其他所有元素，也就是说是一个O(n)结的操作，而循环队列的出队操作不需要每次都移动其他元素，而只是在缩容时移动，也就是说这是一个均摊复杂度为O(1)的操作，所以循环队列效率要优于数组队列