[TOC]
# 數組隊列的問題
數組隊列的出隊復雜度是O(n)
隊列的首移除,不把里面的元素重新排列,就把font指向向后移動
**font == tail 隊列為空**
**(tail+1)%c == front 隊列滿**
如果tail到最后,這個數組此時不應該擴容,因為數組前面有空間沒有被利用
那么這時候應該把tail移動到前面沒有用的位置
capacity中,浪費一個空間
# 接口
還是用之前的動態數組
~~~
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
~~~
# 實現類
~~~
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 int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front == tail;
}
//入隊
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {
//表示要擴容
resize(getCapacity() * 2);
}
data[tail] = e;
//添加了一個元素,tail就要+1,同時為了防止數組滿了,需要跑隊列前面
tail = (tail + 1) % data.length;
size++;
}
//擴容
private void resize(int newCapacity) {
//在構造函數那邊還會再+1的
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 E dequeue() {
//空隊列是不能出隊的
if (isEmpty()) {
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
}
//出隊是要把頭部的元素出去
E ret = data[front];
//把頭部元素的引用置為null,讓他可以被gc,占著引用無法gc
data[front] = null;
//頭元素向后移動1位,同時不能超過數組的長度
front = (front + 1) % data.length;
size--;
//如果出隊之后,裝的元素少于1/4就縮容,但是隊列中元素不能為0
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();
}
}
~~~
# 測試
~~~
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<Integer>();
for (int i = 0; i<10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 ==2) {
queue.dequeue();
System.out.println(queue);
}
}
}
~~~
# 復雜度分析
