Rubyでスタックを活用して問題を解決する方法【実践コード例付き】

コンピュータサイエンス(CS)の学位を持っていないと、「何か重要な知識を逃しているのではないか」と感じることがあるかもしれません。

あるいは、「CSは抽象的すぎて実務では役に立たない」と思っているかもしれません。

もしくは、「Rubyがすでに面倒な処理はすべてやってくれる」と考えているかもしれません。

どの考え方であっても…

ハッシュ、スタック、キューといった基本的なデータ構造の仕組みを理解しておくことは、エンジニアにとって大きな武器になります。

この記事で学べること:

Rubyでスタックを活用する具体的な方法を解説します。今すぐ実践に取り入れられる、実用的なコンピュータサイエンスの概念です!

Rubyにおけるスタックの基礎知識

Rubyにおけるスタックとは何でしょうか?

スタックとは、「やることリスト」のように使えるデータ構造です。スタックから要素を1つずつ取り出しては処理し、これを空になるまで繰り返します。

以下はその動作イメージです。

空のスタックに5をプッシュ(push)する:

5

スタックに3をプッシュする:

3
5

スタックに9をプッシュする:

9
3
5

スタックから要素を1つ取り出す(pop):

3
5

ここで注目すべきポイントは、新しい要素が常にスタックの一番上(先頭)に追加されるという点です。これは「Last-In First-Out(LIFO:後入れ先出し)」方式と呼ばれます。つまり、スタックから要素を取り出す(pop)とき、取り出されるのは最後に追加された要素だということです。

別の捉え方として、お皿の積み重ねを思い浮かべると分かりやすいでしょう。皿を1枚ずつ上に重ねていく場合、一番下の皿を取り出すには、まず上の皿をすべて取り除く必要があります。

スタックで行う操作は、要素を一番上に追加する(push)か、一番上から取り出す(pop)かのどちらかだけです。インデックスによるアクセスはできません。

それでは、実際のコード例を見ていきましょう。

スタックを使って配列をフラット化する方法

スタックの定番の応用例として、多次元配列を1次元配列に変換する「フラット化」があります。

例:

arr = [1,2,3,[4,5],6]

arr.flatten

Rubyにはflattenメソッドが用意されており、これだけで配列を平坦化できます。しかし、もしこのメソッドが存在しなかったら?そして、このメソッドは内部でどのように動作しているのでしょうか?

ここでスタックの出番です!

Rubyの配列にはpushメソッドとpopメソッドが実装されているため、配列をそのままスタックとして扱えます。

補足:pushと<<は同じメソッドです。以降のコード例では<<を使用します。

考え方はシンプルです。すべての要素を順番に調べて、それが配列かどうかを判定します。もし配列なら、その中身の要素をスタックに押し戻します。

こうすることで、玉ねぎの皮を剥くように配列の階層を1つずつ取り除いていき、最終的に完全に平坦化された配列が得られます。

実際のコード:

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に任せているためです。また、この方法では要素の順序が維持されない点にも注意してください。

次に、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]

今回はeachではなくpopで明示的に要素を取り出しているため、結果の順序が変わります。元の順序どおり…ですが、逆順になっていますね。

ここからスタックの興味深い性質が見えてきます。

スタックに入れた要素のリストは、同じ順序で、しかし逆順になって取り出されるのです。

ヒント:Array#flattenメソッドは引数を受け取ります。削除したいネスト(入れ子)の階層数を指定でき、デフォルトではすべての階層を削除します。

括弧の整合性チェック問題を解く

もう1つの例を紹介します。こちらにはRubyの標準メソッドで代用できるものがありません!

しかも、コンピュータサイエンスにおけるもう1つの古典的問題でもあります。

その名も「対応する括弧のマッチング(バランスド・パレンセス)」です。

文字列が与えられ、その括弧が正しく対応しているかどうかを検証するという問題です。

たとえば、数式評価プログラムを作っているとしましょう。処理を行う前に、入力が正しい形式かどうかを確認したいはずです。

例(正しい入力):

input = "1 + (4 + 6) * 2"

例(不正な入力):

input = "1 + (4 + 6 * 2"

スタックを使えば、入力内で見つけた開き括弧を記録していき、閉じ括弧を見つけたタイミングでスタックの先頭と照合できます。

一致しなければ、それは不正な入力だということになります。

例:

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

もう1つ注目すべき点は、valid_parenthesesメソッドの最後をstack.empty?で終えていることです。これは、閉じられていない括弧が残っていないかを確認するためです。

すべての括弧が正しく閉じられていれば、スタックは空になっているはずです 🙂

応用例3:移動方向の最適化

理解を深めるために、もう1つ例を見てみましょう。

今回は、旅行者の移動方向のリストが与えられ、無駄な移動を省いて時間を節約するよう最適化する課題です。

入力例は以下のとおりです。

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

北に行った直後に南へ移動しても、結局は元の場所に戻るだけです(両方向とも同じ距離と仮定)。この無駄を省くのが最適化の目的で、スタックを使えばスマートに実現できます。

例:

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

まとめ

本記事では、Rubyにおけるスタックの基本概念を学び、配列のフラット化、括弧の整合性チェック、移動方向の最適化という3つの実践例を通じてその使い方を確認しました。

今後プログラミングの課題に直面したときは、「スタックで解決できないか?」と一度立ち止まって考えてみてください。きっと新しい解法が見つかるはずです。

この記事が役に立ったら、ぜひシェアして、より多くの人に読んでもらいましょう!