# 第?12?章?棧與隊列 **目錄** + [1\. 數據結構的概念](ch12s01.html) + [2\. 堆棧](ch12s02.html) + [3\. 深度優先搜索](ch12s03.html) + [4\. 隊列與廣度優先搜索](ch12s04.html) + [5\. 環形隊列](ch12s05.html) ## 1.?數據結構的概念 數據結構（Data Structure）是數據的組織方式。程序中用到的數據都不是孤立的，而是有相互聯系的，根據訪問數據的需求不同，同樣的數據可以有多種不同的組織方式。以前學過的復合類型也可以看作數據的組織方式，把同一類型的數據組織成數組，或者把描述同一對象的各成員組織成結構體。數據的組織方式包含了存儲方式和訪問方式這兩層意思，二者是緊密聯系的。例如，數組的各元素是一個挨一個存儲的，并且每個元素的大小相同，因此數組可以提供按下標訪問的方式，結構體的各成員也是一個挨一個存儲的，但是每個成員的大小不同，所以只能用.運算符加成員名來訪問，而不能按下標訪問。 本章主要介紹棧和隊列這兩種數據結構以及它們的應用。從本章的應用實例可以看出，一個問題中數據的存儲方式和訪問方式就決定了解決問題可以采用什么樣的算法，要設計一個算法就要同時設計相應的數據結構來支持這種算法。所以Pascal語言的設計者Niklaus Wirth提出：_算法+數據結構=程序_（詳見[[算法+數據結構=程序]](bi01.html#bibli.wirth "Algorithms + Data Structures = Programs")）。 ## 2.?堆棧 在[第?3?節 “遞歸”](ch05s03.html#func2.recursion)中我們已經對堆棧這種數據結構有了初步認識。堆棧是一組元素的集合，類似于數組，不同之處在于，數組可以按下標隨機訪問，這次訪問`a[5]`下次可以訪問`a[1]`，但是堆棧的訪問規則被限制為Push和Pop兩種操作，Push（入棧或壓棧）向棧頂添加元素，Pop（出棧或彈出）則取出當前棧頂的元素，也就是說，只能訪問棧頂元素而不能訪問棧中其它元素。如果所有元素的類型相同，堆棧的存儲也可以用數組來實現，訪問操作可以通過函數接口提供。看以下的示例程序。 **例?12.1.?用堆棧實現倒序打印** ``` #include <stdio.h> char stack[512]; int top = 0; void push(char c) { stack[top++] = c; } char pop(void) { return stack[--top]; } int is_empty(void) { return top == 0; } int main(void) { push('a'); push('b'); push('c'); while(!is_empty()) putchar(pop()); putchar('\n'); return 0; } ``` 運行結果是`cba`。運行過程圖示如下： **圖?12.1.?用堆棧實現倒序打印**  數組`stack`是堆棧的存儲空間，變量`top`總是保存數組中棧頂的下一個元素的下標，我們說“`top`總是指向棧頂的下一個元素”，或者把`top`叫做棧頂指針（Pointer）。在[第?2?節 “插入排序”](ch11s02.html#sortsearch.insertion)中介紹了Loop Invariant的概念，可以用它檢驗循環的正確性，這里的“`top`總是指向棧頂的下一個元素”其實也是一種Invariant，Push和Pop操作總是維持這個條件不變，這種Invariant描述的對象是一個數據結構而不是一個循環，在DbC中稱為Class Invariant。Pop操作的語義是取出棧頂元素，但上例的實現其實并沒有清除原來的棧頂元素，只是把`top`指針移動了一下，原來的棧頂元素仍然存在那里，這就足夠了，因為此后通過Push和Pop操作不可能再訪問到已經取出的元素，下次Push操作就會覆蓋它。`putchar`函數的作用是把一個字符打印到屏幕上，和`printf`的`%c`作用相同。布爾函數`is_empty`的作用是防止Pop操作訪問越界。這里我們預留了足夠大的棧空間（512個元素），其實嚴格來說Push操作之前也應該檢查棧是否滿了。 在`main`函數中，入棧的順序是`'a'`、`'b'`、`'c'`，而出棧打印的順序卻是`'c'`、`'b'`、`'a'`，最后入棧的`'c'`最早出來，因此堆棧這種數據結構的特點可以概括為LIFO（Last In First Out，后進先出）。我們也可以寫一個遞歸函數做倒序打印，利用函數調用的棧幀實現后進先出： **例?12.2.?用遞歸實現倒序打印** ``` #include <stdio.h> #define LEN 3 char buf[LEN]={'a', 'b', 'c'}; void print_backward(int pos) { if(pos == LEN) return; print_backward(pos+1); putchar(buf[pos]); } int main(void) { print_backward(0); putchar('\n'); return 0; } ``` 也許你會說，又是堆棧又是遞歸的，倒序打印一個數組犯得著這么大動干戈嗎？寫一個簡單的循環不就行了： ``` for (i = LEN-1; i >= 0; i--) putchar(buf[i]); ``` 對于數組來說確實沒必要搞這么復雜，因為數組既可以從前向后訪問也可以從后向前訪問，甚至可以隨機訪問，但有些數據結構的訪問并沒有這么自由，下一節你就會看到這樣的數據結構。 ## 3.?深度優先搜索 現在我們用堆棧解決一個有意思的問題，定義一個二維數組： ``` int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; ``` 它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的路線。程序如下： **例?12.3.?用深度優先搜索解迷宮問題** ``` #include <stdio.h> #define MAX_ROW 5 #define MAX_COL 5 struct point { int row, col; } stack[512]; int top = 0; void push(struct point p) { stack[top++] = p; } struct point pop(void) { return stack[--top]; } int is_empty(void) { return top == 0; } int maze[MAX_ROW][MAX_COL] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; void print_maze(void) { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) printf("%d ", maze[i][j]); putchar('\n'); } printf("*********\n"); } struct point predecessor[MAX_ROW][MAX_COL] = { {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}, }; void visit(int row, int col, struct point pre) { struct point visit_point = { row, col }; maze[row][col] = 2; predecessor[row][col] = pre; push(visit_point); } int main(void) { struct point p = { 0, 0 }; maze[p.row][p.col] = 2; push(p); while (!is_empty()) { p = pop(); if (p.row == MAX_ROW - 1 /* goal */ && p.col == MAX_COL - 1) break; if (p.col+1 < MAX_COL /* right */ && maze[p.row][p.col+1] == 0) visit(p.row, p.col+1, p); if (p.row+1 < MAX_ROW /* down */ && maze[p.row+1][p.col] == 0) visit(p.row+1, p.col, p); if (p.col-1 >= 0 /* left */ && maze[p.row][p.col-1] == 0) visit(p.row, p.col-1, p); if (p.row-1 >= 0 /* up */ && maze[p.row-1][p.col] == 0) visit(p.row-1, p.col, p); print_maze(); } if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) { printf("(%d, %d)\n", p.row, p.col); while (predecessor[p.row][p.col].row != -1) { p = predecessor[p.row][p.col]; printf("(%d, %d)\n", p.row, p.col); } } else printf("No path!\n"); return 0; } ``` 運行結果如下： ``` 2 1 0 0 0 2 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 2 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 2 2 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 0 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 0 0 0 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 0 0 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 2 0 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 2 2 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 0 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 0 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 2 ********* (4, 4) (3, 4) (2, 4) (1, 4) (0, 4) (0, 3) (0, 2) (1, 2) (2, 2) (2, 1) (2, 0) (1, 0) (0, 0) ``` 這次堆棧里的元素是結構體類型的，用來表示迷宮中一個點的x和y座標。我們用一個新的數據結構保存走迷宮的路線，每個走過的點都有一個前趨（Predecessor）點，表示是從哪兒走到當前點的，比如`predecessor[4][4]`是座標為(3, 4)的點，就表示從(3, 4)走到了(4, 4)，一開始`predecessor`的各元素初始化為無效座標(-1, -1)。在迷宮中探索路線的同時就把路線保存在`predecessor`數組中，已經走過的點在`maze`數組中記為2防止重復走，最后找到終點時就根據`predecessor`數組保存的路線從終點打印到起點。為了幫助理解，我把這個算法改寫成偽代碼（Pseudocode）如下： ``` 將起點標記為已走過并壓棧; while (棧非空) { 從棧頂彈出一個點p; if (p這個點是終點) break; 否則沿右、下、左、上四個方向探索相鄰的點 if (和p相鄰的點有路可走，并且還沒走過) 將相鄰的點標記為已走過并壓棧，它的前趨就是p點; } if (p點是終點) { 打印p點的座標; while (p點有前趨) { p點 = p點的前趨; 打印p點的座標; } } else 沒有路線可以到達終點; ``` 我在`while`循環的末尾插了打印語句，每探索一步都打印出當前迷宮的狀態（標記了哪些點），從打印結果可以看出這種搜索算法的特點是：每次探索完各個方向相鄰的點之后，取其中一個相鄰的點走下去，一直走到無路可走了再退回來，取另一個相鄰的點再走下去。這稱為深度優先搜索（DFS，Depth First Search）。探索迷宮和堆棧變化的過程如下圖所示。 **圖?12.2.?深度優先搜索**  圖中各點的編號表示探索順序，堆棧中保存的應該是座標，我在畫圖時為了直觀就把各點的編號寫在堆棧里了。可見正是堆棧后進先出的性質使這個算法具有了深度優先的特點。如果在探索問題的解時走進了死胡同，則需要退回來從另一條路繼續探索，這種思想稱為回溯（Backtrack），一個典型的例子是很多編程書上都會講的八皇后問題。 最后我們打印終點的座標并通過`predecessor`數據結構找到它的前趨，這樣順藤摸瓜一直打印到起點。那么能不能從起點到終點正向打印路線呢？在上一節我們看到，數組支持隨機訪問也支持順序訪問，如果在一個循環里打印數組，既可以正向打印也可以反向打印。但`predecessor`這種數據結構卻有很多限制： 1. 不能隨機訪問一條路線上的任意點，只能通過一個點找到另一個點，通過另一個點再找第三個點，因此只能順序訪問。 2. 每個點只知道它的前趨是誰，而不知道它的后繼（Successor）是誰，所以只能反向順序訪問。 可見，_有什么樣的數據結構就決定了可以用什么樣的算法_。那為什么不再建一個`successor`數組來保存每個點的后繼呢？從DFS算法的過程可以看出，雖然每個點的前趨只有一個，后繼卻不止一個，如果我們為每個點只保存一個后繼，則無法保證這個后繼指向正確的路線。由此可見，_有什么樣的算法就決定了可以用什么樣的數據結構_。設計算法和設計數據結構這兩件工作是緊密聯系的。 ### 習題 1、修改本節的程序，要求從起點到終點正向打印路線。你能想到幾種辦法？ 2、本節程序中`predecessor`這個數據結構占用的存儲空間太多了，改變它的存儲方式可以節省空間，想想該怎么改。 3、上一節我們實現了一個基于堆棧的程序，然后改寫成遞歸程序，用函數調用的棧幀替代自己實現的堆棧。本節的DFS算法也是基于堆棧的，請把它改寫成遞歸程序，這樣改寫可以避免使用`predecessor`數據結構，想想該怎么做。 ## 4.?隊列與廣度優先搜索 隊列也是一組元素的集合，也提供兩種基本操作：Enqueue（入隊）將元素添加到隊尾，Dequeue（出隊）從隊頭取出元素并返回。就像排隊買票一樣，先來先服務，先入隊的人也是先出隊的，這種方式稱為FIFO（First In First Out，先進先出），有時候隊列本身也被稱為FIFO。 下面我們用隊列解決迷宮問題。程序如下： **例?12.4.?用廣度優先搜索解迷宮問題** ``` #include <stdio.h> #define MAX_ROW 5 #define MAX_COL 5 struct point { int row, col, predecessor; } queue[512]; int head = 0, tail = 0; void enqueue(struct point p) { queue[tail++] = p; } struct point dequeue(void) { return queue[head++]; } int is_empty(void) { return head == tail; } int maze[MAX_ROW][MAX_COL] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; void print_maze(void) { int i, j; for (i = 0; i < MAX_ROW; i++) { for (j = 0; j < MAX_COL; j++) printf("%d ", maze[i][j]); putchar('\n'); } printf("*********\n"); } void visit(int row, int col) { struct point visit_point = { row, col, head-1 }; maze[row][col] = 2; enqueue(visit_point); } int main(void) { struct point p = { 0, 0, -1 }; maze[p.row][p.col] = 2; enqueue(p); while (!is_empty()) { p = dequeue(); if (p.row == MAX_ROW - 1 /* goal */ && p.col == MAX_COL - 1) break; if (p.col+1 < MAX_COL /* right */ && maze[p.row][p.col+1] == 0) visit(p.row, p.col+1); if (p.row+1 < MAX_ROW /* down */ && maze[p.row+1][p.col] == 0) visit(p.row+1, p.col); if (p.col-1 >= 0 /* left */ && maze[p.row][p.col-1] == 0) visit(p.row, p.col-1); if (p.row-1 >= 0 /* up */ && maze[p.row-1][p.col] == 0) visit(p.row-1, p.col); print_maze(); } if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) { printf("(%d, %d)\n", p.row, p.col); while (p.predecessor != -1) { p = queue[p.predecessor]; printf("(%d, %d)\n", p.row, p.col); } } else printf("No path!\n"); return 0; } ``` 運行結果如下： ``` 2 1 0 0 0 2 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 0 0 0 0 0 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 0 0 0 2 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 0 0 2 1 1 1 0 0 0 0 1 0 ********* 2 1 0 0 0 2 1 0 1 0 2 2 2 0 0 2 1 1 1 0 2 0 0 1 0 ********* 2 1 0 0 0 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 0 0 1 0 ********* 2 1 0 0 0 2 1 2 1 0 2 2 2 2 0 2 1 1 1 0 2 2 0 1 0 ********* 2 1 0 0 0 2 1 2 1 0 2 2 2 2 2 2 1 1 1 0 2 2 0 1 0 ********* 2 1 2 0 0 2 1 2 1 0 2 2 2 2 2 2 1 1 1 0 2 2 0 1 0 ********* 2 1 2 0 0 2 1 2 1 0 2 2 2 2 2 2 1 1 1 0 2 2 2 1 0 ********* 2 1 2 0 0 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 0 ********* 2 1 2 2 0 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 0 ********* 2 1 2 2 0 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 0 ********* 2 1 2 2 0 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 2 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 2 ********* 2 1 2 2 2 2 1 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 2 ********* (4, 4) (3, 4) (2, 4) (2, 3) (2, 2) (2, 1) (2, 0) (1, 0) (0, 0) ``` 其實仍然可以像[例?12.3 “用深度優先搜索解迷宮問題”](ch12s03.html#stackqueue.dfs)一樣用`predecessor`數組表示每個點的前趨，但我想換一種更方便的數據結構，直接在每個點的結構體中加一個成員表示前趨： ``` struct point { int row, col, predecessor; } queue[512]; int head = 0, tail = 0; ``` 變量`head`和`tail`是隊頭和隊尾指針，`head`總是指向隊頭，`tail`總是指向隊尾的下一個元素。每個點的`predecessor`成員也是一個指針，指向它的前趨在`queue`數組中的位置。如下圖所示： **圖?12.3.?廣度優先搜索的隊列數據結構**  為了幫助理解，我把這個算法改寫成偽代碼如下： ``` 將起點標記為已走過并入隊; while (隊列非空) { 出隊一個點p; if (p這個點是終點) break; 否則沿右、下、左、上四個方向探索相鄰的點 if (和p相鄰的點有路可走，并且還沒走過) 將相鄰的點標記為已走過并入隊，它的前趨就是剛出隊的p點; } if (p點是終點) { 打印p點的座標; while (p點有前趨) { p點 = p點的前趨; 打印p點的座標; } } else 沒有路線可以到達終點; ``` 從打印的搜索過程可以看出，這個算法的特點是沿各個方向同時展開搜索，每個可以走通的方向輪流往前走一步，這稱為廣度優先搜索（BFS，Breadth First Search）。探索迷宮和隊列變化的過程如下圖所示。 **圖?12.4.?廣度優先搜索**  廣度優先是一種步步為營的策略，每次都從各個方向探索一步，將前線推進一步，圖中的虛線就表示這個前線，隊列中的元素總是由前線的點組成的，可見正是隊列先進先出的性質使這個算法具有了廣度優先的特點。廣度優先搜索還有一個特點是可以找到從起點到終點的最短路徑，而深度優先搜索找到的不一定是最短路徑，比較本節和上一節程序的運行結果可以看出這一點，想一想為什么。 ### 習題 1、本節的例子直接在隊列元素中加一個指針成員表示前趨，想一想為什么上一節的[例?12.3 “用深度優先搜索解迷宮問題”](ch12s03.html#stackqueue.dfs)不能采用這種方法表示前趨？ 2、本節例子中給隊列分配的存儲空間是512個元素，其實沒必要這么多，那么解決這個問題至少要分配多少個元素的隊列空間呢？跟什么因素有關？ ## 5.?環形隊列 比較[例?12.3 “用深度優先搜索解迷宮問題”](ch12s03.html#stackqueue.dfs)的棧操作和[例?12.4 “用廣度優先搜索解迷宮問題”](ch12s04.html#stackqueue.bfs)的隊列操作可以發現，棧操作的`top`指針在Push時增大而在Pop時減小，棧空間是可以重復利用的，而隊列的`head`、`tail`指針都在一直增大，雖然前面的元素已經出隊了，但它所占的存儲空間卻不能重復利用。在[例?12.4 “用廣度優先搜索解迷宮問題”](ch12s04.html#stackqueue.bfs)的解法中，出隊的元素仍然有用，保存著走過的路徑和每個點的前趨，但大多數程序并不是這樣使用隊列的，一般情況下出隊的元素就不再有保存價值了，這些元素的存儲空間應該回收利用，由此想到把隊列改造成環形隊列（Circular Queue）：把`queue`數組想像成一個圈，`head`和`tail`指針仍然是一直增大的，當指到數組末尾時就自動回到數組開頭，就像兩個人圍著操場賽跑，沿著它們跑的方向看，從`head`到`tail`之間是隊列的有效元素，從`tail`到`head`之間是空的存儲位置，如果`head`追上`tail`就表示隊列空了，如果`tail`追上`head`就表示隊列的存儲空間滿了。如下圖所示： **圖?12.5.?環形隊列**  ### 習題 1、現在把迷宮問題的要求改一下，只要求程序給出最后結論就可以了，回答“有路能到達終點”或者“沒有路能到達終點”，而不需要把路徑打印出來。請把[例?12.4 “用廣度優先搜索解迷宮問題”](ch12s04.html#stackqueue.bfs)改用環形隊列實現，然后試驗一下解決這個問題至少需要分配多少個元素的隊列空間。