Rubyでスタックを使用して問題を解決する方法

CS（Computer Science）の学位を持っていない場合は、何かを見逃しているように感じるかもしれません…

または、CSが抽象的すぎて役に立たないと感じるかもしれません…

または、Rubyがすでにすべてのハードワークを実行している…

どちらの方法でも…

ハッシュ、スタック、キューなどのデータ構造の基本を理解しておくと役立ちます。

この投稿で ：

Rubyでスタックを使用する方法を学びます。

今すぐ実践できる実用的なコンピュータサイエンスの概念！

Rubyのスタックについて

Rubyのスタックとは何ですか？

スタックは、「やること」リストとして使用できるデータ構造です。スタックから要素を取り出し、スタックが空になるまで処理し続けます。

これが視覚的な表現です。

5を空のスタックにプッシュします ：

5

3をスタックにプッシュします ：

3
5

9をスタックにプッシュします ：

9
3
5

スタックから1つのアイテムを取得します ：

3
5

ここで注目すべき重要な点は、新しいアイテムがスタックの一番上に追加されることです。 。 「後入れ先出し」（LIFO）方式。つまり、スタックからアイテムを取得（ポップ）すると、そのアイテムが最後にプッシュされたアイテムになります。

これがどのように機能するかを視覚化する別の方法は、プレートのスタックについて考えることです。あるプレートを別のプレートの上に置くと、最初にトッププレートを取り出さないとボトムプレートを取り出せません。

スタックを使って、物事を一番上に押したり、飛び出したりするのはこれだけです。 インデックスはありません 。

これをどのように使用できるかについて、いくつかのコード例を見てみましょう。

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

スタックの典型的な例は、それらを使用して配列をフラット化することです。つまり、多次元配列を1次元配列に変換します。

ここに例があります ：

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

arr.flatten

Rubyには、これを行うflattenメソッドがあります。しかし、この方法がなかったらどうなるでしょうか。そして、この方法はどのように機能しますか？

これがスタックの出番です！

Rubyはプッシュ＆ポップメソッドを実装しています 、配列をスタックのように扱うことができます。

注：両方のpush ＆<< 同じ方法です。 <<を使用します 私のコード例では。

アイデアは、すべての要素を調べて、それが配列か何か他のものかどうかを確認することです。配列の場合は、push この配列内の要素をスタックに戻します。

何が起こるかというと、配列レイヤー（タマネギのような）がなくなるまで削除し続けるということです。これにより、フラット化されたアレイが残ります。

コードは次のとおりです ：

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]

popを使用しているので 今では、eachを使用する代わりに、 そのことを実行すると、フラット化された配列が正しい順序で取得されます...しかし逆になります。

これにより、スタックの興味深い特性が明らかになります。 ：

入力したもののリストが何であれ、同じ順序で逆に戻ります。

ヒント：Array#flatten methodは引数を取ります。これにより、削除するネストのレイヤーの数を定義できます（デフォルトではすべてのレイヤー）。

バランス括弧問題の解決

これは別の例です。これを行うための同等の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

結論

何か新しいことを学び、スタックを使用してプログラミングの課題を解決する方法を探し始めていただければ幸いです。

この投稿を共有することを忘れないでください より多くの人がこれを読むことができます！