### 數組隊列的問題
數組隊列的實現是具有局限性的,關鍵問題就是出隊的時間復雜度是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();
}
}
~~~
