佇列是一種能存放多個資料，但無法透過索引（index）來操作的結構。佇列在資料的管理方式具有「先進先出」的特性，在應用上包含任務的排程、待處理資料的等候區（緩衝區，buffer）等等。本文會講解佇列的結構與操作方式，並撰寫 Java 程式，分別以鏈接串列和陣列實作出來。
一、佇列的結構與操作方式
佇列就像是排隊一樣，人會從隊伍的尾端（rear）進入，並且在隊伍的前端（front）依照進入的順序逐一被處理。這兩點形成了「先進先出」（First In First Out，FIFO）的特性。
讀者可以再想像印表機的使用，在電腦上，先按下「列印」的文件會被先處理。而 I/O 的操作是比較慢的，所以電腦把任務存放在工作佇列中等候。
本文會以鏈結串列與陣列實作出不同的佇列。為了有所規範，筆者設計一個叫「IQueue」的介面，定義佇列基本的操作方式。
public interface IQueue<E> {
boolean enqueue(E data);
E dequeue();
E peek();
int size();
boolean isFull();
}
以下是這些方法的用途
enqueue：從佇列尾端新增一筆資料，並回傳是否新增成功。dequeue：從佇列前端拿出一筆資料。peek：回傳佇列前端的資料，但不會從佇列中移除。size：回傳佇列的資料筆數。isFull：回傳佇列空間是否已滿。
二、鏈結串列實作佇列
鏈結串列是由「節點」所構成，因此我們先準備好節點的類別。
public class Node<E> {
private E data;
private Node<E> next;
public Node(E data) {
this.data = data;
}
public E getData() {
return data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
}
再來是佇列的類別，它會實作 IQueue 介面。其具有 frontNode 與 rearNode 的節點欄位，分別代表最前端與最尾端的資料；而 size 欄位代表佇列中有幾筆資料。以下是示意圖與範例程式。
public class LinkedListQueue<E> implements IQueue<E> {
private Node<E> frontNode;
private Node<E> rearNode;
private int size;
public boolean enqueue(E data) {
// TODO
return true;
}
public E dequeue() {
// TODO
return null;
}
public E peek() {
if (this.size == 0) {
throw new RuntimeException();
}
return this.frontNode.getData();
}
public int size() {
return this.size;
}
public boolean isFull() {
return false;
}
}
我們從 enqueue 方法開始實作，做法相當於在串列的最後面加入新節點。因此只要將原本尾端節點的鏈結指向新節點，再更新 rearNode 欄位即可。若佇列中原本就沒有資料，則只要更新前端與尾端節點。
public boolean enqueue(E data) {
Node<E> node = new Node<>(data);
if (this.size == 0) {
this.frontNode = node;
} else {
this.rearNode.setNext(node);
}
this.rearNode = node;
this.size++;
return true;
}
接著是 dequeue 方法，做法相當於刪除串列最前面的節點，並回傳被刪除的資料。因此我們從前端節點（第一個節點）的鏈結獲取第二個節點，將其更新到 frontNode 欄位，最後回傳第一個節點資料。若取出的資料正好是最後一筆，則 frontNode 與 rearNode 欄位最終會被設為 null，代表佇列中沒有資料可以存取了。
public E dequeue() {
if (this.size == 0) {
throw new RuntimeException();
}
Node<E> node = this.frontNode;
this.frontNode = node.getNext();
this.size--;
if (node == this.rearNode) {
this.rearNode = null;
}
return node.getData();
}
三、陣列實作佇列
在佇列的類別中，同樣會實作 IQueue 介面。而資料的儲存之處是一個陣列，其容量（長度）透過建構子來給定。其中 frontIndex 與 rearIndex 欄位則分別代表前端與尾端資料在陣列中的索引。以下是示意圖與範例程式。
public class ArrayQueue<E> implements IQueue<E> {
private Object[] elements;
private int frontIndex = -1;
private int rearIndex = -1;
public ArrayQueue(int capacity) {
this.elements = new Object[capacity];
}
public boolean enqueue(E data) {
// TODO
return false;
}
public E dequeue() {
// TODO
return null;
}
public E peek() {
if (size() == 0) {
throw new RuntimeException();
}
return (E) this.elements[frontIndex];
}
public int size() {
// TODO
return 0;
}
public boolean isFull() {
return size() >= this.elements.length;
}
}
由於佇列的資料筆數可透過 frontIndex 與 rearIndex 欄位的值推導出來，所以筆者不另外宣告 size 欄位，而是透過方法來計算。
接著從 enqueue 方法開始實作，分成佇列為空和佇列非空兩種情形。如果佇列沒有資料，就固定將新資料放在陣列的第一個位置。如果有，我們知道 rearIndex 是最後一筆的索引，因此新資料的索引就是 rearIndex + 1。
public boolean enqueue(E data) {
if (isFull()) {
return false;
}
if (size() == 0) {
this.frontIndex = 0;
this.rearIndex = 0;
} else {
this.rearIndex++;
}
this.elements[this.rearIndex] = data;
return true;
}
再來實作 dequeue 方法。只要將 frontIndex 索引所指向的元素值清空（設為null），更新 frontIndex，並回傳該筆資料即可。
public E dequeue() {
if (size() == 0) {
throw new RuntimeException();
}
E data = (E) this.elements[this.frontIndex];
this.elements[this.frontIndex] = null;
this.frontIndex++;
return data;
}
本節實作的佇列沒有用來記錄資料筆數的欄位，而是使用 size 方法進行計算。當佇列有資料時的判斷方式不難理解，重點在於如何判斷佇列為空。其一是佇列剛建立時，frontIndex 為 -1。其二是當佇列只有一筆資料時，frontIndex 會等於 rearIndex，若再取出，frontIndex 就會加1，使其大於 rearIndex。
public int size() {
if (this.frontIndex > this.rearIndex) {
return 0;
} else if (this.frontIndex == -1) {
return 0;
} else {
return this.rearIndex - this.frontIndex + 1;
}
}
雖然佇列的方法都實作出來了，但會有個問題。rearIndex 會隨著資料的持續加入，最後等於陣列的最大索引。即便從佇列取出資料，但仍被 enqueue 方法判斷佇列已滿。解決的方式是先將陣列元素往前搬移，才加入新資料。以下是示意圖與範例程式。
private void forwardElements() {
int size = size();
for (int i = 0; i < size; i++) {
this.elements[i] = this.elements[this.frontIndex + i];
}
int uncleanedAmount = size > this.frontIndex
? this.frontIndex
: size;
for (int i = uncleanedAmount - 1; i >= 0; i--) {
this.elements[size + i] = null;
}
this.frontIndex = 0;
this.rearIndex = size - 1;
}
以上的實作，首先從 frontIndex 索引指向的元素開始，逐一將元素複製到陣列的第一個、第二個…，依此類推。從以下的示意圖中，讀者會發現複製完成後，陣列後方有殘留元素需要清除。
一開始算出的 size 除了是資料筆數，也代表搬移完畢後，最後一筆的索引加1。透過 frontIndex 與 size，可判斷搬移前、後的索引範圍是否重疊。若有，殘留元素的數量就是元素的位移量，也就是搬移前的 frontIndex（上圖情況一）。否則為佇列的資料筆數（上圖情況二）。
知道要清除的數量後，我們從複製前的最後一個元素索引開始往前清除。完成後，再調整佇列的 frontIndex 與 rearIndex 欄位即可。最後將此方法應用到 enqueue 方法。
public boolean enqueue(E data) {
if (isFull()) {
return false;
}
if (this.rearIndex == this.elements.length - 1 && this.frontIndex > 0) {
forwardElements();
}
// 其餘略過
}
五、擴大佇列的陣列容量
上一節實作出的佇列，由於在建立時就已經決定陣列容量，所以當空間滿了，將無法再加入新資料。本節我們會基於上一節的佇列做進一步的調整，讓容量能自行擴大，以下簡稱擴容。
首先宣告另一個無參數的建構子，而陣列的容量給予0。這是一種節省記憶體空間的手法，考慮了建立出佇列，卻完全沒用到的可能性。等真的要新增資料，再索取記憶體進行擴容就好。
public class ArrayListQueue<E> implements IQueue<E> {
private Object[] elements;
private int frontIndex = -1;
private int rearIndex = -1;
public ArrayListQueue() {
this.elements = new Object[0];
}
public ArrayListQueue(int capacity) {
this.elements = new Object[capacity];
}
public boolean enqueue(E data) {
// TODO
return true;
}
// 其餘略過，與ArrayQueue相同
}
接下來實作擴容的程式。針對上述容量為0的佇列，我們給予預設容量10。之後每次都讓容量擴大為原本的1.5倍。建立出新陣列後，再將目前的資料複製過去，並指定給佇列即可。
private void grow() {
int newCapacity = this.elements.length == 0
? 10
: (int) (this.elements.length * 1.5);
Object[] newElements = new Object[newCapacity];
for (int i = 0; i < this.elements.length; i++) {
newElements[i] = this.elements[i];
}
this.elements = newElements;
}
最後在加入資料時，先判斷佇列是否已滿，是的話則呼叫 grow 方法。如此一來便不必擔心佇列空間不夠了。但另一方面，也會有多餘空間用不到，形成浪費的問題，這是陣列的缺點。
public boolean enqueue(E data) {
if (isFull()) {
grow();
}
// 其餘略過，與ArrayQueue相同
}
以下是本文的完整程式碼：
https://gist.github.com/ntub46010/7c222c5bf882e547028ae600075a40a0
留言
張貼留言