玩转数据结构之使用数组实现循环队列

上一篇谈到数组队列出队时间复杂度为O(n)，那有什么方式可以当元素出队的时候，不需要移动其他元素的位置呢？这里就引入循环队列的概念。

• 队列为空时，front与tail同时指向队首节点；此时front == tail表示队列为空；
  
• 队列中有元素时，front指向队首节点，tail指向队尾元素下一个节点；
• 队列中移除元素，front向前移动，队列中其他元素不需要移动；
  
• 队列元素满时，预留一个空间，避免front == tail的情况（准确的说应该是front == (tail+1) % data.length）;
  
  小结： 由于队列引入front与tail可以循环存储元素，故而称之为循环队列，虽然牺牲1个空间，但能保证出列时其他元素不需要移动，从而实现入队出队时间复杂度均为O（1）;

• 同样是接口定义，与数组队列一致；

package com.sjgd.stack;


public interface Queue {

   
   int getSize();

   
   boolean isEmpty();

   
   void enqueue(E e);

   
   E dequeue();

   
   E getFront();

}

• 循环队列具体实现类

package com.sjgd.stack;

import java.util.Arrays;


public class LoopQueue implements Queue {
   
   private E[] data;
   
   private int front, tail;

   private int size;

   public LoopQueue(int capacity) {
       //循环队列需要有1个剩余空间，避免队列满的时候front == (tail+1)%data.length的情况发生
       data = (E[]) new Object[capacity + 1];
       front = 0;
       tail = 0;
       size = 0;
   }


   public LoopQueue() {
       this(10);
   }

   public int getCapacity() {
       return data.length - 1;
   }

   @Override
   public boolean isEmpty() {
       //当队首和队尾同时指向同一个节点时，此时队列中没有元素
       return front == tail;
   }

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


   @Override
   public void enqueue(E e) {
       //先判断当前队列中元素是否已满
       if ((tail + 1) % data.length == front) {
           //此时表示队列已满，需要扩容
           resize(2 * getCapacity());
       }
       //插入元素
       data[tail] = e;
       //tail位置进行移动
       tail = (tail + 1) % data.length;
       //元素个数++
       size++;
   }

   private void resize(int newCapacity) {
       E[] newData = (E[]) new Object[newCapacity + 1];
       for (int i = 0; i < getSize(); i++) {
           //data中数据相较于i有front个位置的偏移量
           newData[i] = data[(i + front) % data.length];
       }
       data = newData;
       front = 0;
       tail = size;
   }

   @Override
   public E dequeue() {
       if (isEmpty()) {
           throw new IllegalArgumentException("The Queue is empty!");
       }
       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("The Queue is empty!");
       }
       return data[front];
   }

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

}

• 测试数组队列与循环队列入队出队耗时对比

package com.sjgd.stack;
import java.util.Random;


public class QueueTest {

   public static void main(String[] args) {
       int count = 10000;
       System.out.println("ArrayQueue time: " + getTime(new ArrayQueue<>(), count));
       System.out.println("LoopQueue time: " + getTime(new LoopQueue<>(), count));
   }

   
   public static double getTime(Queue queue, int count) {
       long startTime = System.currentTimeMillis();
       Random random = new Random();
       for (int i = 0; i < count; i++) {
           queue.enqueue(random.nextInt(Integer.MAX_VALUE));
       }
       for (int i = 0; i < count; i++) {
           queue.dequeue();
       }
       long endTime = System.currentTimeMillis();
       return (endTime - startTime) / 1000.0;
   }
}

结果打印：
ArrayQueue time: 0.113
LoopQueue time: 0.003

从上文分析可以得出 循环队列出队入队时间复杂度均为O(1);