隊列 Queue

• 隊列也是一種線性結構
• 相比數組，隊列對應的操作是數組的子集
• 只能從一端（隊尾）添加元素，只能從另一端（隊首）取出元素
• 隊列是一種先進先出的數據結構

隊列的實現及復雜度分析

Queue<E>

• void enqueu(E)
• E dequeue()
• E getFront()
• int getSize()
• boolean isEmpty()

數組隊列的復雜度分析

ArrayQueue<E>

• void enqueue(E)? ? ?O(1) 均攤
• E dequeue()? ? ? ? ? ? O(n)?
• E getFront()? ? ? ? ? ? ?O(1)
• int getSize()? ? ? ? ? ? ?O(1)
• boolean isEmpty()? ?O(1)

代碼實現：

public class ArrayQueue<E> implements Queue<E> {private Array<E> data;public ArrayQueue(int Capacity){data = new Array<>(Capacity);}public ArrayQueue(){this(10);}@Overridepublic int getSize(){return data.getSize();}public int getCapacity(){return data.getCapacity();}@Overridepublic boolean isEmpty(){return data.isEmpty();}@Overridepublic void enqueue(E e){data.addLast(e);}@Overridepublic E dequeue(){return data.removeFirst();}@Overridepublic E getFront(){return data.getFirst();}@Overridepublic String toString(){StringBuilder res = new StringBuilder();res.append("Queue : front [");for (int i = 0; i < data.getSize(); i++) {res.append(data.get(i));if (i != data.getSize() - 1)res.append(", ");}res.append("] tail");return res.toString();}public static void main(String[] args){ArrayQueue<Integer> queue = new ArrayQueue<>();for(int i = 0 ; i < 10 ; i ++){queue.enqueue(i);System.out.println(queue);if(i % 3 == 2){queue.dequeue();System.out.println(queue);}}}
}

循環隊列的復雜度分析

LoopQueue<E>

• void enqueue(E)? ? ?O(1) 均攤
• E dequeue()? ? ? ? ? ? O(1) 均攤?
• E getFront()? ? ? ? ? ? ?O(1)
• int getSize()? ? ? ? ? ? ?O(1)
• boolean isEmpty()? ?O(1)

front == tail? ? ? ? ? ? ? ? 隊列為空

(tail + 1) % c = front? 隊列已滿

tail不用于存儲元素，capacity中浪費一個空間?

代碼實現：

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);}@Overridepublic boolean isEmpty(){return size == 0;}public boolean isFull(){return front == (tail + 1) % data.length;}public int getCapacity(){return data.length - 1;}@Overridepublic int getSize(){return size;}@Overridepublic void enqueue(E e){if (isFull())resize(getCapacity() * 2 + 1);data[tail] = e;tail = (tail + 1) % data.length;size++;}@Overridepublic E dequeue(){if (isEmpty())throw new IllegalArgumentException("Dequeue Failed.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 + 1);return ret;}@Overridepublic E getFront(){if (isEmpty())throw new IllegalArgumentException("Queue is empty.");return data[front];}public void resize(int newCapacity){if (newCapacity <= 0)throw new IllegalArgumentException("newCapacity is Illegal.");E[] newData = (E[])new Object[newCapacity];for (int i = 0; i < size; ++i)newData[i] = data[(i + front) % data.length];data = newData;front = 0;tail = size;}@Overridepublic String toString(){StringBuilder res = new StringBuilder();res.append(String.format("LoopQueue Capacity = %d, Size = %d\n", getCapacity(), getSize()));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<>();for (int i = 0; i < 10; i++) {queue.enqueue(i);System.out.println(queue);if (i % 3 == 2) {queue.dequeue();System.out.println(queue);}}}
}

性能比較：

測試函數：

// 測試使用q運行opCount個enqueueu和dequeue操作所需要的時間，單位：秒private static double testQueue(Queue<Integer> q, int opCount){long startTime = System.nanoTime();for (int i = 0; i < opCount; ++i)q.enqueue(i);for (int i = 0; i < opCount; ++i)q.dequeue();long endTime = System.nanoTime();return (endTime - startTime) / 1000000000.0;}

測試：

    public static void main(String[] args){int opCount = 100000;ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();double timeArray = testQueue(arrayQueue, opCount);System.out.println("ArrayQueue time :" + timeArray + " s");LoopQueue<Integer> loopQueue = new LoopQueue<>();double timeQueue = testQueue(loopQueue, opCount);System.out.println("LoopQueue time :" + timeQueue + " s");}

運行結果：

在10^5數量級上，我的這臺電腦上，所展現性能差異還是很明顯的，由于數組隊列的出隊操作是 O(n) 級別，消耗了大量的時間。