如果你沒有 CS（電腦科學）學位，你可能覺得錯過了什麼……
或者你覺得 CS 太抽象不實用……
或者 Ruby 已經幫你做完所有苦工……
無論如何……
了解資料結構基礎像雜湊、stacks 和 queues 是有幫助的。
這篇文章：
你將發現如何在 Ruby 使用 stacks。
一個你現在就能開始實踐的實用電腦科學概念！
理解 Ruby 中的 Stacks
Ruby 中的 stack 是什麼？
Stack 是一個資料結構，你可以當作「待辦事項」清單用。你不斷從 stack 取元素並處理，直到 stack 空了。
這裡是視覺化表示。
Push 5 進空 stack：
5
Push 3 進 stack：
3
5
Push 9 進 stack：
9
3
5
從 stack 取一個項目：
3
5
要注意的重點是新項目加在 stack 的頂端。以「後進先出」（LIFO）方式。意思是當你取（pop）項目時，會是最後被 push 進去的項目。
另一種視覺化方式是想像一疊盤子。如果你把一個盤子疊在另一個上，不拿掉最上面的盤子就拿不出底下的盤子。
這就是 stack 全部在做的事，把東西推到頂端或彈出。沒有索引。
來看一些程式碼範例怎麼用。
如何用 Stack 攤平陣列
Stack 的經典例子是用它們攤平陣列。換句話說，把多維陣列轉成一維陣列。
例子：
arr = [1,2,3,[4,5],6] arr.flatten
在 Ruby 我們有 flatten 方法幫你做這事。但如果你沒有這個方法？這方法怎麼運作？
這就是 stack 派上用場的地方！
Ruby 實作了 push 和 pop 方法，所以我們可以把陣列當 stack 用。
注意：
push和<<是同一個方法。我會在程式碼範例用<<。
想法是遍歷每個元素檢查它是陣列還是其他東西。如果是陣列，我們把這陣列裡的元素 push 回 stack。
發生的事是我們不斷移除陣列層（像洋蔥）直到沒有為止。這留給我們攤平的陣列。
程式碼：
arr = [1,2,3,[4,5],6] flat = [] arr.each do |thing| if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [1, 2, 3, 6, 4, 5] 你會注意到這程式碼沒有 pop 方法呼叫。
這是因為我讓 each 做從 stack 取項目並餵給演算法的苦工。也注意這樣做元素順序不保持。
另一個用 until 和 empty? 的版本：
until arr.empty? thing = arr.pop if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [6, 5, 4, 3, 2, 1] 既然用 pop，不讓 each 做事，我們得到正確順序的攤平陣列... 但反轉了。
這揭示了 stack 的一個有趣屬性：
你放進去的任何東西清單，會以相同順序但反轉回來。
提示：
Array#flatten方法接受一個參數，讓你定義想移除多少層巢狀（預設全移除）。
解決平衡括號問題
這裡有另一個例子，Ruby 沒有對等方法幫你做！
這也是電腦科學的經典問題……
名字是：
配對平衡括號。
想法是給你一個字串，你需要驗證括號是否有效。
例如，假設你在寫數學評估程式。你想在處理前確保輸入有效。
例子（有效輸入）：
input = "1 + (4 + 6) * 2"
例子（無效輸入）：
input = "1 + (4 + 6 * 2"
你可以用 stack 追蹤在輸入中找到的任何括號，然後當你找到新括號時檢查 stack 頂端確保它符合閉合括號。
如果沒有匹配，代表輸入無效。
例子：
PARENS = { "(" => ")", "{" => "}", "[" => "]" } OPENING_PARENS = PARENS.keys CLOSING_PARENS = PARENS.values def valid_parentheses(string) stack = [] string.each_char do |ch| if OPENING_PARENS.include?(ch) stack << ch elsif CLOSING_PARENS.include?(ch) ch == PARENS[stack.last] ? stack.pop : (return false) end end stack.empty? end p valid_parentheses("(){}[]") # true p valid_parentheses("[(])") # false 另一件事你會注意到是我用 stack.empty? 結束 valid_parentheses 方法。那是為了確保我們不會以未閉合的括號結束。
如果所有括號都正確閉合，stack 應該是空的 🙂
範例 3（方向）
再一個例子確保你懂怎麼應用這個。
這種情況我們得到一組方向，被告知需要優化以節省旅行者時間。
這裡是範例集：
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
你會注意到如果你往北再往南會回到同樣地方（假設距離相同）。這就是我們要優化的，用 stack 可以做到。
例子：
input = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"] directions = [] opposites = { "NORTH" => "SOUTH", "SOUTH" => "NORTH", "EAST" => "WEST", "WEST" => "EAST" } input.each do |dir| opposites[dir] == directions.last ? directions.pop : directions << dir end p directions 結論
希望你學到新東西，開始找方法用 stacks 解決程式挑戰。
別忘了 分享這篇文章 讓更多人讀到！
