5.5 練習¶

5.5.1 知識鞏固¶

準備一個空堆疊 S 和一個空佇列 Q，分別對它們執行下面同一組操作：

步驟 1：加入 A；步驟 2：加入 B；步驟 3：移除一個元素並記錄；步驟 4：加入 C；步驟 5：不斷移除並記錄，直到容器為空。

請分別寫出 S 和 Q 中元素被移除的順序，並用“先入後出”或“先入先出”解釋差異。

參考答案

堆疊 S 的移除順序是 B、C、A：加入 A、B 後先彈出最近加入的 B，再加入 C，此後依次彈出 C、A，體現“先入後出”。

佇列 Q 的移除順序是 A、B、C：加入 A、B 後先移除最早加入的 A，再加入 C，此後依次移除 B、C，體現“先入先出”。

用長度為 5 的環形陣列實現佇列，陣列索引為 0～4。當前 front = 3、size = 2，佇列中的 A、B 分別位於索引 3、4。

參考答案

新元素的位置為 (front + size) % 5 = (3 + 2) % 5 = 0，所以 C 放在索引 0。入列後 size = 3。
出列彈出當前佇列首 A。新的佇列首索引為 (3 + 1) % 5 = 4，因此 front = 4、size = 2。
有效元素的邏輯順序為 B、C，其中 B 位於索引 4，C 位於索引 0。出列時只需移動 front 並修改 size，環形陣列用取餘讓索引回到開頭，因此無須把其他元素整體向前移動。

這裡規定：push_first 表示從佇列首加入，push_last 表示從佇列尾加入， pop_first 表示從佇列首彈出，pop_last 表示從佇列尾彈出。

對一個空的雙向佇列 deq 依次執行：

參考答案

前三步後，雙向佇列從佇列首到佇列尾為 [C, A, B]。

pop_last() 彈出 B；加入 D 後佇列為 [C, A, D]， pop_first() 再彈出 C。
最後剩下 [A, D]。
只允許在佇列尾新增、在佇列首刪除的佇列不能完成全部操作：第 3 步 push_first(C) 要求從佇列首加入，第 4 步 pop_last() 要求從佇列尾刪除，都超出了這種佇列的操作範圍。雙向佇列的兩端都可以新增和刪除，因此能夠完成這 6 步操作。

給定一個只包含 ()、[]、{} 這三類括號的字串 s，請使用堆疊判斷它是否合法。

合法序列須同時滿足：每個右括號都必須與最近一個尚未配對的左括號型別匹配，並且走訪結束後沒有未配對的左括號。返回布林值表示判斷結果。

解題提示