摘要訊息 : 堆疊是一種只允許在尾部逐個插入或者移除元素的資料結構, 它在電腦科學中的應用非常廣泛.

0. 前言

雙向佇列是頭部尾部插入元素都可以視為 $\Theta(1)$ 的資料結構, 如果我們把雙向佇列作為低層, 禁止在頭部或者中間位置尋訪, 插入和移除元素, 只能在尾部尋訪和逐個添加或者移除元素, 那麼我們就得到了一個全新的資料結構.

更新紀錄 :

• 2022 年 4 月 5 日進行第一次更新和修正.

1. 定義

定義 1. 設有不可尋坊的線性表 $L_{\boldsymbol {\alpha}} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}$, 若尋訪, 插入和移除元素只能逐個在尾部進行, 那麼我們稱 $L_{\boldsymbol {\alpha}}$ 為堆疊 (stack).

在前言中, 我們提到把雙向佇列作為低層, 然而在定義中我們卻使用線性表. 實際上, 任意線性結構的資料結構都可以作為堆疊的低層, 只要將這個線性結構限制只能在尾部逐個插入或者移除元素即可.

定義 1 中還提到了 $L_{\boldsymbol {\alpha}}$ 是不可尋坊的, 也就是說堆疊內部的元素是不可以被存取的, 只有堆疊尾部最後一個元素 (有的書籍會稱為頂部, 這是把向量從下到上豎著排列, 而非從左到右排列) 的元素才可以存取. 要存取堆疊內部的元素, 只有一個一個從尾部移除了元素才可以.

由於每一次只能存取堆疊尾部最後一個元素, 因此最先進入堆疊的元素最後才能出來, 而最後進入堆疊的元素卻能夠最先出來. 為此, 堆疊也被稱為先進後出 (first in last out, FILO) 的資料結構.

在 C++ 中, 那些以其它容器作為低層的資料結構稱為容器配接器 (container adaptor). std::stack 以 std::deque 作為低層資料結構, 因此 std::stack 就是一個容器配接器.

2. 插入和移除

根據定義 1, 我們已經知道了向堆疊插入或者移除元素只能在尾部進行, 而且一次只允許操作一個元素. 那麼, 插入和移除的時間複雜度就取決於低層資料結構在尾部插入和移除元素的時間複雜度 :

• 以向量作為低層資料結構 : 平攤 $\Theta(1)$;
• 以前項連結串列作為低層資料結構 : $\Theta(n)$;
• 以連結串列作為低層資料結構 : $\Theta(1)$;
• 以雙向佇列作為低層資料結構 : 可以視為 $\Theta(1)$ 的.

既然連結串列作為低層資料結構, 向堆疊插入和移除元素的時間複雜度都是 $\Theta(1)$ 的, 那我們為什麼還要以雙向佇列優先作為低層的資料結構呢? 這是因為連結串列的 $\Theta(1)$ 是有額外代價的, 連結串列的每一個節點都維護了兩個指向型標記, 這兩個指向型標記太消耗空間了.

由於堆疊只能存取逐個存取尾部元素, 所以本來可以在線性結構上進行的搜尋, 字典比較和旋轉等演算法都不可以在堆疊上進行.

3. 和堆疊有關的演算法

儘管和線性結構有關的幾個演算法都無法使用在堆疊上, 但是堆疊有幾個比較有名的應用, 在本節中我們將分別介紹這些應用.

3.1 替換遞迴

為了說明如何使用堆疊替換遞迴, 我們首先要介紹一下遞迴的處理過程. 設有函式 f :

Code 1. 累加函式
unsigned f(unsigned x) {
    if(x == 1 or x == 0) {
        return x;
    }
    return f(x - 1) + x;
}

通過閱讀 Code 1 中函式 f 的具體程式碼, 我們知道, 對於任意輸入 $x$, 其作用是輸出 $\displaystyle {1 + 2 + ... + x = \sum \limits_{i = 1}^{x}i}$ 的值. 令引數 $x = 5$, 最終得到的結果應該是 $15$. 現在我們要詳細分析一下函式的運作過程.

當 $x = 5$ 時, 程式需要計算 f(4) + 5. 那麼, 程式必須首先計算出 f(4) 的結果, 然後才能計算表達式 f(4) + 5 的值. 因此, 程式必須保存當前局域變數 x 的值以及當前程式的運作位置 (運作到 return f(x - 1) + x;, 也就是指令的位置), 以便於 f(4) 計算完成之後回過頭來繼續完成剩餘計算. 對於 f(4) 也是類似的, 它需要等到 f(3) 的計算結果; 而 f(3) 需要等待 f(2) 的計算結果; f(2) 需要等待 f(1) 的計算結果.

通過分析, 我們發現 f(5) 雖然最先被呼叫, 但是需要等待 f(4), f(3), f(2) 和 f(1) 的結果. 也就是最先被呼叫的最後才能出結果. 而對於 f(1), 卻可以最先出結果, 因為它不需要等待其它表達式的運算結果. 這顯然和堆疊的特性相吻合. 因此, 我們使用堆疊來儲存函式的狀態 :

當 f(1) 運作得到結果的時候, 就可以從堆疊頂部存取並且移除函式 f(2) 的狀態, 並且恢復 f(2) 的運作, 得到 f(1) + 2 的值. 對於 f(3), f(4) 和 f(5) 也是類似的過程.

所有遞迴都可以使用堆疊進行模擬, 因為編碼器和程式正是這樣去解釋和運作遞迴程式碼的.

3.2 括號匹配

在 C++ 中, 有好幾種括號 : <>, {}, [], (), '', "". 編碼器在編碼的時候必定要進行語法的檢查, 那麼檢查括號是否相匹配非常重要. 那麼任意給定一段程式碼, 應該如何進行檢查呢? 其實, 給定任意一種括號, 其右括號若可以和某一個左括號相匹配, 那麼所有和其種類相同的左括號中, 那個能夠匹配的左括號距離右括號最近.

考慮函式宣告 :

template <typename T>
void f(int &(arr)[10], char = '\0', typename T::type<char> = "");

這其中有十四個括號需要進行匹配, 其中正確的配對是 1 - 2, 3 - 14, 4 - 5, 6 - 7, 8 - 9, 10 - 11, 12 - 13. 從左至右, 我們發現, 最先被發現的左括號直到最後遇到相同類別的右括號時才會被匹配, 這個也堆疊的性質類似, 因此我們使用堆疊來處理括號匹配問題. 任給一段程式碼, 當遇到左括號的時候, 就將其放入堆疊; 當遇到右括號的時候, 若存在下列情況 :

• 堆疊為空;
• 堆疊頂部的括號和它不配對,

那麼就說明出現了括號不匹配的問題. 如果堆疊頂部的左括號剛好和右括號匹配, 那麼從堆疊中移除這個左括號. 還有一種情況需要注意, 就是當程式終結時堆疊中還存在左括號, 這就說明沒有足夠的右括號和堆疊中的左括號匹配, 這也會導致括號不匹配的問題. 將這些描述實作為 C++ 程式碼就是 :

Code 2. 括號匹配
#include <string>
#include <stack>

bool bracket_match(const std::string &str) {
    std::stack s {};
    for(auto c : str) {
        switch(c) {
            case '(':
            case '[':
            case '<':
            case '\'':
            case '"':
            case '{':
                stack.push(c);
                break;
            case ')':
                if(s.empty() or s.top() not_eq '(') {
                    return false;
                }
                s.pop();
                break;
            case ']':
                if(s.empty() or s.top() not_eq '[') {
                    return false;
                }
                s.pop();
                break;
            case '>':
                if(s.empty() or s.top() not_eq '<') {
                    return false;
                }
                s.pop();
                break;
            case '\'':
                if(s.empty() or s.top() not_eq '\'') {
                    return false;
                }
                s.pop();
                break;
            case '"':
                if(s.empty() or s.top() not_eq '"') {
                    return false;
                }
                s.pop();
                break;
            case '}':
                if(s.empty() or s.top() not_eq '{') {
                    return false;
                }
                s.pop();
                break;
            default:
                break;
        }
    }
    return s.empty();
}

需要注意的是, 上面程式碼的行為並不總是正確, 因為 < 和 > 還有比較的含義. 因此對於 < 和 > 還需要在符號表中檢查左右兩側的是關鍵字型別還是表達式.

設括號匹配需要檢查的字元數量為 $n$, 那麼要解決括號匹配的空間複雜度為 $\Theta(n)$, 這是因為我們需要至多 $n$ 個額外空間來儲存每一個括號. 最壞的情況下, $n$ 個字元全部都是左括號. 當然, 函式 bracket_matching 進行了優化, 當檢測到不匹配的時候就會直接終結函式. 解決括號匹配的時間複雜度也是 $\Theta(n)$, 因為所有字元我們都需要檢查.

3.3 開關盒佈線

給定任意矩形, 在矩形的邊上存在若干個管腳 :

任意兩個管腳之間通過佈設一條金屬線來相連接, 這條金屬線稱為電線. 它被限定在了矩形區域之內, 即電線不可以穿過矩形的邊來到矩形之外的區域 :

另外, 如果兩條電線交叉, 那麼就會出現短路的情況 :

我們不允許實際佈線的過程中出現電線交叉的情況. 每一對要連結的管腳稱為網組. 對於任意給定的矩形, 上面隨即分佈著管腳, 我們需要確定這些給定的網組的連接會不會不發生短路. 這樣的問題稱為開關盒佈線問題.

我們注意到, 當一個網組相連接的時候, 連線必定會將矩形分成兩個區域. 若出現一個網組跨越了兩個區域, 就可以判定其不可佈線. 因此, 我們可以根據連線不可跨區域原則, 對網組是否可以在開關盒上面佈線進行判斷.

為了實現這一策略, 可以從任意管腳開始, 按順時針或著逆時針沿著開關盒的邊界進行尋訪. 為了方便表述, 我們按照某一順序從第一個管腳開始進行編號 : $a_{1}$, $a_{2}$, ..., $a_{n}$. 若 $a_{1}$ 與 $a_{i}$ ($i = 1, 2, ..., n$) 相連接, 則將 $a_{1}$ 放入堆疊. 首先處理 $a_{1}$ 到 $a_{i}$ 之間所構成區域中的管腳連線. 若 $a_{1}$ 不和 $a_{2}$ 相連接, 則將 $a_{2}$ 也放入堆疊, ... 以此類推. 當 $a_{j}$ 遇到 $a_{k}$ ($i, j = 1, 2, ..., n$ 且 $i \neq j$) 相連接的時候, 那麼從堆疊頂部移除 $a_{j}$. 不斷重複上述步驟, 當所有管腳都尋訪完畢的時候, 堆疊中如果不存在任何管腳, 那麼這一組網組是可以在開關盒上進行佈線的; 否則, 就不可以在開關盒上面佈線, 這是由堆疊的性質決定的. 由於堆疊只能訪問到其頂部元素, 因此當出現不可佈線的情況的時候, 即使已經遇到了 $a_{i}$ 和 $a_{j}$ 相連接, 但是 $a_{i}$ 並不在堆疊頂部, 頂部元素也無法和 $a_{j}$ 相連接. 因此, $a_{j}$ 會被放入頂部, 從而導致堆疊中 $a_{j}$ 之前的管腳都無法完成佈線.

通過上面分析, 我們可以斷言在開關盒佈線問題中, 若一組網組是可佈線的, 則在非最小區域內必定存在一個網組, 其要連接的兩個管腳對應的編號是相鄰的. 於是我們便可以編寫出下面的程式碼 :

Code 3. 開關盒佈線
#include <utility>
#include <stack>

template <std::size_t N>
bool check_wiring(const std::pair<int, int> (&list)[N]) {
    std::stack s {};
    for(auto c : list) {
        if(s.empty()) {
            s.push(c.first);
            continue;
        }
        if(s.top() == c.second) {
            s.pop();
        }else {
            s.push(c.first);
        }
    }
    return s.empty();
}

想要解決開關盒佈線問題, 所有的編號我們都需要尋訪, 並且至多需要 $n$ 個空間, 因此時間複雜度和空間複雜度都是 $\Theta(n)$.

3.4 逆波蘭表示法

對於帶有括號的四則運算, 大家已經非常熟練了, 一般我們優先計算內部括號的內容, 然後逐個計算外部括號中的運算式, 最終得到結果. 然而這一套計算方案對於電腦來說並不可行. 因為這套計算方案是智能的, 使用一般的演算法很難模擬, 因此我們必須要使用一種適用於電腦的方案.

逆波蘭表示法是運算式的另外一種記法, 這種記法有利於電腦對表達式進行計算. 在逆波蘭記法中, 所有運算子置於運算元的後面, 因此也被稱為字尾表示法. 逆波蘭記法不需要括號來標識運算子的優先級.

對於運算式 $5 + \big ((1 + 2) \times 4 \big ) - 3$, 它的逆波蘭表示法為 $5\ 1\ 2\ +\ 4\ \times\ +\ 3\ -$. 那麼給定任意逆波蘭表示法, 如何得到原運算式的結果呢? 我們需要借助堆疊並且尋訪全部字元 :

• 如果字元為數字, 那麼將其放入堆疊;
• 如果字元為運算子, 那麼從尾部取出兩個數字, 將這兩個數字使用該運算子計算之後, 將結果放入堆疊.

一旦堆疊中只剩下一個數字, 那麼這個數字就是最終運算式的計算結果.

這裡要注意的是, 我們假設所有運算子都是二元運算子. 對於一元運算子甚至多元運算子, 上面的演算法還需要繼續改進.

對於如何得到一個運算式的逆波蘭表示法, 這個需要借助一個稱為二元樹 (《【資料結構】樹——二元樹》) 的資料結構, 此處我們不講述.

計算一個逆波蘭表示的結果需要尋訪 $n$ 個元素, 堆疊至多需要儲存 $n$ 個元素, 因此時間複雜度和空間複雜度都為 $\Theta(n)$.

4. 雙向堆疊 (雙邊堆疊)

當我們使用雙向佇列作為堆疊的低層資料結構的時候, 我們一般為雙向佇列預留一些空間. 但是一旦這裡面很多空間沒有被使用, 就會造成浪費, 此時我們可以在雙向佇列的另外一邊也建立一個堆疊, 使得雙向佇列的頭部和尾部都是一個堆疊, 這兩個堆疊相互獨立, 操作相反. 這樣的資料結構成為雙向堆疊 (bidirectional stack, 有時也稱為雙邊堆疊).

像雙向佇列這種資料結果特別適合作為雙向堆疊的低層, 因為不論在其頭部還是尾部插入或者移除元素, 時間複雜度都可以視為是 $\Theta(1)$.

5. 實作

我自己用 C++ 實作了堆疊 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/stack.hpp, 大家可以參考後自行實作.