### 数组队列的问题
数组队列的实现是具有局限性的,关键问题就是出队的时间复杂度是O(n)级别的 . 当队首元素出队的时候所有的元素要向前移动一位,
这样如果有百万量的数据的话,消耗的计算资源是非常庞大的.有没有其他方法呢 ?
当我们推出队首的元素后,所有元素位置保持不变,front++
### 循环队列
当front == tail 的时候队列为空,当有新元素入队,tail++,当推出元素就front++. 当tail超过队列的容量之后,tail的位置移动到最前面,可以把这个队列看成是一个环形的.所以叫循环队列.
当front == tail 的时候队列为空,所以当tail + 1 == front 队列满,就说明我们要扩容了.在这里我们有意识的浪费了一个空间 . tail +1 == front说明队列满其实是不准确的.
真实应该是(tail+1)%c(容量) == front 说明队列满.
### 实现
~~~
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;
}
private void resize(int newCapacity)
{
E[] newData = (E[]) new Object[newCapacity + 1];
for(int i = 0; i < size; i++) {
newData[i] = data[(i + front) % data.length];
}
data = newData;
front = 0;
tail = size;
}
@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 dequeue frm 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];
}
@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[i]);
if((i + 1) % data.length != tail)
res.append(",");
}
res.append("] tail");
return res.toString();
}
}
~~~
