玩转数据结构之循环队列 - 黑马程序员技术交流社区

黑马程序员技术交流社区

标题:

作者:

时间:

标题:

数组队列存在的问题是，当队首元素出队之后，所有剩余元素都需要向前移动，这样时间复杂度是O(n)

这里引入循环队列，依靠移动front和tail的位置保持队列的首尾位置，这样减小了时间复杂度。

那么与数组队列不同的地方还在于，当tail已经移动到索引为7的位置后，下一次再有元素入队，tail实际上会移动到索引为0的位置，所谓循环队列，应该把队列看作是一个圆环。

最后，对于capacity为8的情况，当tail在索引1，此时再有元素入队，tail++则会等于front，但队列并不为空，因此这里需要再添加一个判断，如果（tail + 1）% c == front则表示队列满。

循环队列的特点就在于循环移动，更具体一些理解，可以以钟表为例，当时间来到1点之后，下一个小时可以叫做12点同样也可以叫做0点，这就是一个循环，循环队列的索引就像钟表一样形成了一个环。

具体实现：

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

   public LoopQueue(int capacity){
      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(getCapacity() * 2);
      data[tail] = e;
      tail = (tail + 1) % data.length;
      size ++;
   }

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

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

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

————————————————

原文链接：「Forizon」 https://blog.csdn.net/hesongzefairy/article/details/104480440

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2