無所不在的排隊：佇列

佇列（Queue）是我們在設計系統、設計程式時時常會用到的一種資料結構，幾乎每個程式設計者都有使用過佇列的經驗。

小到自己設計的佇列資料結構或內建的佇列類別，或是大到可分散式運作的一組佇列伺服器（Queue Server），佇列的應用在軟體系統中幾乎是無所不在。

不過，儘管如此，如何運用佇列，對軟體開發人員而言，還是一門相當大的學問。在這一回中，就讓我們來略為探討吧。

佇列的不同用法
所謂的「佇列」其實就是一種依照順序存取的抽象資料結構。一般人所最常接觸的，可能是所謂的FIFO（First In First Out）Queue，也就是依照先進先出的原則來存取的佇列。不過，佇列的「順序」不只是先進先出這種規則而已，像所謂Priority Queue（優先序佇列）便是依據佇列中元素被定義的「優先序」來決定存取的先後順序。優先序佇列的例子在生活中也很常見，例如在急診室裡，病人的看診順序就不是依照先到先看診的方式，而是依據病情的緊急程度。

因為佇列的定義很簡單，所以在其中的操作也很簡單。

你所能對佇列做的最根本操作，就是下列兩種：一種是把元素置入佇列中，也就是enqueue，另一種便是將元素自佇列中取出，也就是dequeue。

這兩項操作是佇列的最基本操作，有些佇列還會提供一些額外的操作，像是窺看但不取出佇列最前端（也就是下一個取出）的元素。此外，針對不同的變形，佇列還會有一些不同的特性，像是所謂的Deque（Double Ended Queue），它就是兩端皆可存取的佇列，而不會只可從頂端取出。

不同架構的佇列
在一般的電腦系統裡，佇列依據它是否獨立存在於獨立的行程裡，可區分為兩種：「行程內（In-Process）佇列」，及「以網路為基礎（Network-Based）的佇列」。

所謂的「行程內佇列」代表佇列的程式和使用佇列的客戶端程式是位在同一個行程之內，這通常是我們最常運用佇列的情況。

例如我們在使用C++的STL中的std::queue或是Java內建的java.util.Queue類別時，佇列的程式和使用佇列的客戶端程式，都是運行在同一個行程之內，它們之間，不需要透過網路或其他跨行程通訊（Inter-Process Communication）的方式來進行溝通，也不需要在溝通時，把要操作的元素資料做類似序列化（serialization）的動作，以便傳輸。所以，不會因為資料傳輸，或是為了資料傳輸而做的計算，而付出額外的代價。

因此，使用行程內的佇列在效率上通常會比較好。而另一類以網路為基礎的佇列，佇列是存在於獨立的行程之外，通常這種情況我們就把它稱為佇列伺服器，因為這個獨立的行程透過一個特定的通訊協定，或是跨行程的通訊方法，來對客戶端程式提供佇列的服務。

因為，透過網路或跨行程的通訊方法來存取佇列，都必須針對所欲在佇列中操作元素的資料內容，予以處理，例如像是序列化或是解序列化，也都必須將這些內容，透過網路或通訊的管道來做傳輸。一方面增加了計算量上的負擔，另一方面也增加了傳輸時的負擔，不但耗用頻寬，而且也需要投入計算來處理資料。

不過，以網路為基礎的佇列單節點來看的效率，比較不那麼好，卻擁有一個很重要的優勢，也就是它比較容易擴展規模。行程內的佇列雖然運行效率好，但是，會受限於單一個行程所能配置的資源量，而無法擴展規模。

例如，一個32位元的電腦，有可能作業系統僅能分配4G位元組的記憶體空間給單一行程，若是佇列需要的記憶體空間，因為規模的增加而必須超過4G位元組，那麼，行程內的佇列就會因為記憶體空間的限制，而無法擴展規模。這些硬體資源上的限制，不只會發生在記憶體空間，也會發生在CPU計算能力、檔案儲存空間、網路傳輸頻寬、等等。相較於行程內的佇列，能透過網路為客戶端提供服務的佇列伺服器，反而得以有機會透過在架構中的多個佇列伺服器，來得到更多的資源，以便提供更強大的服務能力。

所謂的規模可擴充性（scalability）指的，不是在效率比較高，而是可以透過投入更多的資源，來得到提供更大規模服務的能力。以網路為基礎的佇列，不但可以透過分散式的架構得到擴充規模的能力，而且，還有機會因此而得到更多容忍錯誤的能力，也就是說，即使有部份的佇列損毀，還能維持一定的服務能力。

用到佇列的幾種理由

我們會基於什麼目的，而在系統或程式中應用佇列呢？通常有三種原因：（1）在演算法中需要佇列特性的資料儲存結構（2）基於資源配置的最佳化（3）進行跨執行緒或跨行程的通訊。

不少我們所熟知的演算法，其中都運用了佇列的資料結構，來存放演算法進行過程中所操作的資料。例如像在圖的走訪（Graph Traversal）中，「廣度優先搜尋（Breadth First Search）」的演算法，就會將每次未走訪過的節點置入一個FIFO佇列中，每次要走訪一個新節點時，都從佇列中取出一個節點來處理；或是像著名的Prim的最小展開樹（Minimal Spanning Tree）演算法中，使用優先序佇列，都是在演算法中利用佇列特性的例子。

同時，在我們實務的開發中，也會遇到所設計的演算法需要利用佇列的特性。

除了演算法中利用佇列循序存取特性的應用之外，利用佇列來做資源配置的最佳化，也是佇列很常看到的應用。

基本上，佇列就是讓你得以在服務成本及服務品質之間，取得平衡的一種機制。資源通常是有限的，資源的量時常決定了服務的品質，因為資源的量愈多、愈充足，服務的品質時常會更好。但是，資源的量通常也決定了服務的成本，因為所使用的資源量愈多，花在資源的代價就愈高。

佇列的第三個常見的應用，便是做為跨執行緒或跨行程的通訊之用。佇列允許你將資料元素置於其中，也允許你自其中取出。所以，想要進行通訊的雙方甚至是多方，便可以將想要通訊的內容置於佇列中。

因為佇列本身具有緩衝、暫存的作用，所以通訊的雙方或多方，可以進行「非同步」的通訊，也就是說，發送訊息和接收訊息的速率和步調不一定得保持完全一致。當發送方上線時，接收方不一定要在線上，反之亦然。非同步和緩衝都是佇列重要的先天特質，接下來你會發現，有很多佇列的應用都是基於這兩項特質而來。像傳統跨行程通訊（Inter-Process Communication，IPC）需面對的生產者及消費者的問題，其中生產者和消費者其實就是在做通訊的活動。

事實上，所謂訊息發送者與訊息接收者的模型中，訊息發送者就像是一個生產者，只不過它所生產的是訊息，而接收者就是消費者，所消費的也是訊息。像我們所常使用的一些即時通訊軟體，都會利用所謂的「訊息佇列（Message Queue）」來儲存訊息。

在下一回中，將更進一步介紹佇列應用實務上的一些議題。