算法、數據結構、與設計模式等在遊戲開發中的運用 （四）：隊列（Queue）
算法、數據結構、與設計模式等在遊戲開發中的運用 （四）：隊列（Queue）
作者：Compasslg
1. 什麼是隊列
如同棧（Stack）一般，隊列（Queue）也是一種抽象的數據結構（Abstract Data Structure）。所以同理的，「隊列」 這個名稱定義的是你如何從外部理解和使用這種數據結構，而非該數據類型的具體實現方式或者內部結構——你可以根據自己的需求選擇用數組、鏈表等各種各樣的數據結構來實現隊列。關於這方面的詳情可以參考我討論Stack的那一篇博文。
相反於棧的先進後出（FILO: First in, Last out），隊列是一種先進先出（FIFO） 的數據類型。就和現世生活中的排隊購物一樣，先進隊伍的人在前面，可以比後進隊伍的人先結賬並脫離隊伍；而新來的人則會加入到隊伍的末尾。
與Stack類似，隊列也有三個基本的方法：一個用於加入新的元素到尾部 （enqueue入隊），一個用於獲取並移除隊列最前端的元素 （dequeue出隊），以及一個用於查看當前隊列是否為空。同時根據需要，隊列也常常會有用於查看最前方元素（Front）和尾端元素（Rear）的方法，與棧的Peek/Top方法相似。
上面談到的是最基本的線性隊列的概念與結構。事實上，除了這種所謂 「傳統意義上的隊列」 以外，編程中也有很多功能花哨甚至可能是非線性的數據結構也號稱「隊列」。一個典型的特殊隊列的例子就是很多算法都會運用到的優先隊列(Priority Queue)，這個會在以後講Heap或者尋路算法的時候再詳細討論。
2. 如何實現和使用隊列
隊列有很多實現方法，其中最簡單的便是利用鏈表（LinkedList）。但在實際運用中，利用鏈表往往不是最優的隊列實現方法，且大多數語言內置的Collection包里也不會用鏈表來實現隊列。如果你對數據結構有一定的了解，就會知道相較於鏈表，使用數組會有明顯的速度和空間使用效率上的優勢（尤其是隊列容量固定的時候）。但由於這篇博文重點在於介紹隊列的概念和使用，為了方便理解這裡會採用最直觀的鏈表來實現隊列的方法（其實在數據不多的情況下，鏈表的這些劣勢基本可以忽略不急）。
public class Queue<T> {
private Node<T> front, rear;
public Queue(){
front = null;
rear = null;
}
// 入隊
// add a new element to the rear of the queue
public void enqueue(T e){
// create a node, assign to both rear and front if the queue was empty
// 新建一個元素並插入到隊列最前方。如果隊列此前為空，那麼這個元素會同時為前端和尾端。
if(front == null){
front = new Node(e);
rear = front;
}else{
rear.next = new Node(e);
rear = rear.next;
}
}
// remove and return the front element
// 出隊
public T dequeue(){
// throw an error if the queue is empty
// 隊列為空時拋出異常
if(front == null){
throw new Exception("dequeue(): queue is empty.");
}
// save front value, remove front node
// 獲取隊列最前端的值，並移除用於保存該值的Node
T e = front.value;
front = front.next;
// if the removed front is the only element in queue
// both front and null should be null
// 如果移除後最前端的值變為空，則將隊尾的值也設置為空
if(front == null){
rear = null;
}
return e;
}
// return true if front is null, meaning no element in Linked List
// 查看隊列是否為空
public boolean isEmpty(){
return front == null;
}
// an inner class representing a node in the linkedlist
// 一個node代表鏈表/隊列中的包含一個元素的容器。
class Node<T>{
T value;
Node<T> next;
public Node(T e){
value = e;
next = null;
}
}
}
這裡要注意的是，我在上一段代碼中使用的是Java語法，但我並沒有選擇使用Java自帶LinkedList，而是直接在隊列的類中自己實現了一個簡單的鏈表。事實上，Java的LinkedList類本身就繼承了一個Queue的接口（Interface），你可以直接將它當隊列來使用，用linkedList.add()來入隊，linkedList.remove()來出隊。因此，如果在外面再套一層Queue的話會顯得有些多此一舉；同時，我選擇直接在Queue中實現鏈表的方式實際上也和Java自帶的鏈表類里實現Queue接口中的方法的方式大同小異，這樣也更方便理解。
3. 遊戲開發中的應用
-
回合制遊戲中的行動順序隊列（Turn Queue）
回合制和半回合制遊戲中常常有速度、行動力的概念來決定場上所有單位的行動順序，這個時候可以通過隊列來安排。當然，很多遊戲中會有提升或降低速度的技能和物品，這個時候會需要重新生成隊列。 -
管理經營類遊戲中的生產隊列
很多管理經營類遊戲，或者即時戰略遊戲中都會有生產隊列的概念。通過使用隊列來提前規劃之後的生產順序可以使玩家操作起來更為方便。一個典型的例子就是文明系列中在城市裡的生產列隊，提前安排之後需要生成的單位或設施，將後續需要製造的東西依次加入隊列，噹噹前生產任務完成時，從隊列中移除並獲取下一個需要生成的單位。 -
行動隊列
很多及時戰略遊戲和MOBA類遊戲中都有用隊列提前安排之後的行動的功能。例如DotA中可以在TP的時候按住Shift將跳刀加到行動隊列中實現落地瞬間跳走，沙王施法前搖時將跳到放到隊列中實現跳大等操作。 -
劇情對話
當劇情對話會因為玩家的選擇產生分支的時候，常常需要用樹結構來儲存，但歸根結底，這可以被當作一種非線性的隊列。實際運行的時候，還是可以用Queue來儲存和操作正在播放的劇情文字，分支產生並被選擇以後再將該分支下的對話加入到隊列中。 -
動畫播放，多節點移動
遊戲動畫中，有時候會有沿着一系列節點移動的操作，這個過程可以使用隊列來完成，將所有節點按照順序加入隊列，然後用dequeue獲取並移除隊列頂端的點來實現按照相同順序移動。 -
消息、事件的傳輸和分發
一些網遊或者多進程的單機需要用接收、處理從網絡或其他進程傳入的指令和消息，而當本地在處理消息的時候，其他陸續傳入的消息將在隊列中等待，然後當前一個任務執行完畢後從隊列中獲取下一個需要被執行的指令或需要處理的消息。
4. 總結
總而言之，隊列是一種非常常見且實用的抽象數據結構。其重點不在實現過程，而是概念和使用方式；很多時候，初學者都會以使用隊列的方式來利用數組或鏈表而不自知。能夠熟練和合理的運用和理解這種極簡卻實用的抽象數據類型可以為遊戲開發提供很大的便利。
