自己动手写Queue

什么是队列

队列是一种先进先出的数据结构（First In First Out）。结合生活实际，这里的队列就是从生活中的排队得来的。比如我们正在排队办理业务，后来的人只能从队列最后一个进入队伍（入队），当前面的的人办理完业务的时候他就离开了队伍（出队）。由此我们可以发现，要实现队列其实最重要的就是出队和入队的操作。所以我们就可以定义我们的Queue接口了。

  /**
 * @author Lin
 * @date 2019-04-15 19:19
 **/
public interface Queue<E> {

  /**
   * 入队
   * @param e 元素
   */
  void enqueue(E e);

  /**
   * 出队
   * @return 出队的元素
   */
  E dequeue();

  /**
   * 获取大小
   * @return 队列大小
   */
  int getSize();

  /**
   * 获取队头元素
   * @return 队头元素
   */
  E getFront();

  /**
   * 判断是否为空
   * @return 布尔
   */
  boolean isEmpty();
}

数组队列

了解队列的特点，我们不难就想到了上次使用数组实现栈，其实队列和栈也差不多，只不过更改了出和入的操作罢了，这里我就不明细讲了，直接上代码

  /**
 * @author Lin
 * @date 2019-04-15 19:19
 **/
public class ArrayQueue<E> implements Queue<E>{

  private Array<E> array;

  public ArrayQueue(){
    array=new Array<>();
  }

  public ArrayQueue(int capacity){
    array=new Array<>(capacity);
  }

  @Override
  public void enqueue(E e) {
    array.addLast(e);
  }

  @Override
  public E dequeue() {
    return array.removeFirst();
  }

  @Override
  public int getSize() {
    return array.getSize();
  }

  @Override
  public E getFront() {
    return array.getFirst();
  }

  @Override
  public boolean isEmpty() {
    return array.isEmpty();
  }
}

循环队列

我们来对上面的数组队列做一个时间复杂度分析

当我们进行入队操作的时候时间复杂度肯定为O(1),这是非常高效的。但是，我们要进行出队的时候就大不相同了，因为我们每次出队，当移除头元素的时候我们就需要将后面的元素挨个往前移动，因为我们这个底层就是依靠动态数组实现的，所以就是调用动态数组删除某个索引元素的方法，那么这个时间复杂度就是O(n),也就是说当我们进行出队操作的时候，队伍量越大我们消耗的时间就越大，这是低效且我们不愿意看到的。在数据结构中，很多时候我们都会使用空间和时间的互换，时间换取空间资源，空间资源换取时间资源，所以我们这里可以使用循环队列来提高出队效率。

循环队列是什么，其实就相当于将队列的头和尾相连接

如图：

我们增加了一个头索引和尾索引来达到虚拟的连接（这个当然不是真实的）。当我们初始化这个队列的时候，头索引和尾索引都是0,当头索引和尾索引相等的时候这个队列为空，首先记着这个（很好理解，就是头和尾中间没有间隔那不就是空了么）。当我们进行入队操作的时候，将元素放入循环队列的尾索引处，放置完成后将尾索引+1（后移一个单位）。当进行出队的时候，我们将头元素删除，并将头索引+1（后移一个单位）。是不是很简单？当然不可能这么简单，因为这个队列是循环的，头和尾是相连的，这里我们就可以利用相连的特性来使用我们刚刚可能出队的时候浪费的空间资源，怎么做？其实就是更改一下我们头索引和为索引相加的位置，我们将他们++操作更改为front=(front+1)%capacity就行，这里的capacity是指整个队列的容量。

还有一个注意点就是当我们整个队列满的时候我们是无法判断队列是否为空的，因为这时候头索引和尾索引也是相等的，这个时候我们就需要牺牲一个存储单元来解决冲突。

下面就直接贴代码

/**
 * @author Lin
 * @date 2019-04-15 19:40
 **/
public class LoopQueue<E> implements Queue<E> {

  private E[] array;
  private int front, tail;

  public LoopQueue() {
    this(10);
  }

  public LoopQueue(int capacity) {
    array = (E[])new Object[capacity+1];
    //头尾索引置为0
    front = 0;
    tail = 0;
  }


  private int getCapacity() {
    return array.length - 1;
  }

  //入队
  @Override
  public void enqueue(E e) {
    //当使用长度和容量相等的时候进行扩容
    if (((tail - front + this.getCapacity()+1) % (this.getCapacity()+1)) == this.getCapacity()) {
      resize(this.getCapacity() * 2);
    }
    //将元素e放入队尾
    array[tail]=e;
    tail++;
  }

  //出队
  @Override
  public E dequeue() {
    //当队列为空抛出异常
    if (front==tail){
      throw new IllegalArgumentException("The loopQueue has no element");
    }else {
      //将头元素置为null并且将头索引向后移动一个单位
      E temp=array[front];
      array[front]=null;
      front=(front+1)%array.length;
      //当队列只使用了四分之一时将队列缩容
      if (this.getSize()==this.getCapacity()/4&&this.getCapacity()/2!=0){
        resize(this.getCapacity()/2);
      }
      return temp;
    }
  }

  //获取当前队列的实际长度（使用头尾索引计算）
  @Override
  public int getSize() {
    return (tail - front + this.getCapacity()+1) % (this.getCapacity()+1);
  }

  @Override
  public E getFront() {
    return array[front];
  }

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

  //扩容
  private void resize(int capacity) {
    E[] newArray = (E[])new Object[capacity+1];
    int size = (tail - front + this.getCapacity()+1) % (this.getCapacity()+1);
    for (int i = 0; i < size; i++) {
      newArray[i]=array[(front + i) % size];
    }
    array = newArray;
    front = 0;
    tail = size ;
  }

  @Override
  public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    stringBuilder.append("[");
    for (int i = front; i != tail; i = (i + 1) % array.length) {
      if ((i + 1) % array.length == tail) {
        stringBuilder.append(array[i]);
      } else {
        stringBuilder.append(array[i]).append(",");
      }
    }
    stringBuilder.append("] tail container:").append(this.getCapacity());
    return stringBuilder.toString();
  }
}

    //测试
    public static void main(String[] args) {
    LoopQueue<Integer> loopQueue=new LoopQueue<>();
    for (int i=0;i<17;i++){
      loopQueue.enqueue(i);
      System.out.println(loopQueue);
    }
    loopQueue.dequeue();
    loopQueue.dequeue();
    loopQueue.dequeue();
    System.out.println(loopQueue);
  }

数组队列和循环队列的比较

大数比较

  private static double testQueue(Queue<Integer> q, int opCount){

  long startTime = System.nanoTime();

  Random random = new Random();
  for(int i = 0 ; i < opCount ; i ++){
    q.enqueue(random.nextInt(Integer.MAX_VALUE));
  }

  for(int i = 0 ; i < opCount ; i ++){
    q.dequeue();
  }


  long endTime = System.nanoTime();

  return (endTime - startTime) / 1000000000.0;
}

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");
}

运行结果：

可以看出，当数据量大的时候，LoopQueue完胜。

当我们把数据量变为10的时候我们不难发现，LoopQueue还是胜出,并且速度比数组队列快一个量级。