C++ 頭文件系列(queue)

簡介

這個頭文件定義了兩個跟隊列有關的類----quque、priority_queue，分別實現的是隊列 和 優先隊列這兩個概念。 但是與這兩個類模版與其它類模版（vector、array等）最大的不同是，它們是 容器適配器。

容器適配器

顧名思義，容器適配器是對容器的適配，從代碼層面來講，它就是對容器的再封裝。 因此，這些容器適配器實際上都是由其他容器的功能實現的。 不難看出， 容器適配器所具有的功能是內部容器功能的子集。

普通的類封裝一般是為了封裝成特定問題領域下的類，提供特定的接口，以解決開發中遇到的實際問題為主要目的； 而作為一門語言庫中的庫類，它們更多考慮的是可重用性，所以庫類一般封裝成像stack、quque等具有抽象性的概念。

隊列

你可以把隊列看成一種被適配的容器，它有兩個重要的特性：

• FIFO（first-in first-out）： 先入隊的元素總是先出隊。
• 兩端出入： 元素從一端入隊，從另一端出隊。

操作對應的成員函數

• 入隊 -> push
• 出隊 -> pop

為什麼少了很多常見函數

細心的你們肯定發現了，queue類模版提供的函數很少，一些非常常見的函數都沒有。 如果讓我用一句話來解釋的話，那就是----所有涉及頭尾兩端外的位置的函數，都不在隊列的概念內！

因為在隊列中，所有元素的存取都只能通過入隊和出隊操作。 如果你想獲取位於中間位置的元素，那麼對不起，你只能先把前面的元素取出來；如果你想對隊中的元素本身進行操作，抱歉，你得先獲取它（當然，然，出於實際上的方便使用，queue類模版還是包含了一些本不在概念內的函數：size、back等）。 在隊列上的操作是非常有限的，所以隊列只在一些特殊且適合情況下才被使用。

那這些消失的函數都包括哪些呢？

1. 所有Iterator函數： 沒錯，是所有，你沒有看錯！ 因為所有迭代器都可以通過步進（advance函數或者算數加減）操作，從而指向隊列中間的元素。
2. 更改大小的非pop非push函數（包括增加和刪除）： 隊列大小的改變只能被入隊出隊操作影響。
3. 所有隨機存取函數 ： 元素的獲取只能按序，而獲取是操作的前提。

優先隊列

優先隊列也是一中容器適配器，這種隊列主要具有以下兩個性質：

• 按優先級排序
• 按優先級獲取

在優先隊列中，所有的元素都是按照優先級排序。 具體來說，當每一次元素入隊時，都會對隊列進行優先級排序，優先級最高的排在最前面，優先級最低的排在最後面。 而獲取元素時，只能按優先級從高到底依次獲取。

從某種意義上來說，隊列（queue）和 優先隊列（priority_queue）是相似的，甚至可以說 隊列是優先隊列的特殊情況。 它們都按照某種規律排序，只是排序的規則不同： 隊列按元素的入隊時間排序，優先隊列按元素優先級排序。

優先級

那麼如何定義該種隊列的優先級呢？ 在聲明優先隊列對象的時候，你可以傳遞一個二元謂詞（Binary Predicate）來執行排序的任務。 如果你不傳遞自定義的二元謂詞，則優先隊列默認使用functional頭文件中的less函數對象。

這個二元謂詞執行嚴格弱序排序（Strick Weak Ordering）。這個排序有以下四個屬性（假設comp為比較操作，x、y、z為待比較的元素, x non-comp y等價於(x comp y) == false && (x comp y) == false)）：

• 自反性（(x comp x) == false）
• 不對稱性（(x comp y) ！= (y comp x)）
• 傳遞性（((x comp y) == true， (y comp z) == true)) => ((x comp z) == true))）
• 不可比性（(x non-comp y, y non-comp z) => (x non-comp z)）

這著實有點晦澀，搞得我都頭暈了。 簡單的講，這個二元謂詞比較兩個元素，如果第一個比較的元素應該排在第二個前面（即第一個元素的優先級高於第二個），那麼它返回true。 元素的相等性也是通過這個謂詞操作推出來的：如果第一個元素的優先級不高於第二個元素，並且第二個元素的優先級也不高於第一個元素，那麼這兩個元素就相等。

操作對應的函數

• 入隊 -> push
• 出隊 -> pop

值得注意的是，不像隊列那樣，優先隊列裡的元素沒有時間前後之分，所以priority_queue模版類去掉了front和back成員函數，代之以top函數，用以指代下一個出隊的優先級最高的元素。