ざっくりん雑記

プログラミングで忘れそうなことをひたすらメモる

Ruby - 配列を列として扱う

配列は列としてみなすことができる

まわりくどいので、ズバッと言うとキュースタックというデータ構造としてみなすこともできる。 このキューやスタックは対等的なデータ構造と言えるが、どちらも

  • 要素を追加し
  • 追加した要素を取り出す

といった操作は共通している。

これをArrayクラスはメソッドとして持っている。

キュー

キューは、最初に格納した要素が、一番最初に取り出される、つまりFIFO(First-in First-out)なデータ構造。

はじめに、キューメソッドとして用意されているのは要素を追加する、要素を取り出すのみなのを意識すると理解しやすいです。

具体的に説明すると、

f:id:azuuun:20160413005731p:plain

まずこのような配列があったとします。 既に要素としてAから順番にDまで格納されています。

ここに、新たに要素を格納するとします。

f:id:azuuun:20160413005740p:plain

するとこのように、Dの後ろに新たな要素がINします(追加されます)。

今度はデータを取り出してみます。 FIFOの原則として、最初に格納したものを最初に取り出す、が前提なので、何が取り出されるかというと、

f:id:azuuun:20160413005743p:plain

このようにAがOUTします(Aが取り出されます)。

最終的には以下の様な配列になります。

f:id:azuuun:20160413005746p:plain

これが、キューです。

スタック

キューの対等的なスタックは、最後に入れたものが最初に取り出される、つまりLIFO(Last-in First-out)なデータ構造です。

これも図でみるとわかりやすいです。

まず、先程と同様にAから順にDまで追加したスタックがあります。原則として、一番上のものしか取れない構造になっていることに注意して下さい。

f:id:azuuun:20160413011036p:plain

ここに新たに要素をINします(追加します)。

f:id:azuuun:20160413011039p:plain

すると一番上に、新たな要素であるEが積み上がる形になります。

f:id:azuuun:20160413011042p:plain

次にデータを取り出してみたいと思います。LIFOの原則なので、ここでは一番最後に追加したEが最初に取り出されます。

f:id:azuuun:20160413011045p:plain

キューとスタックまとめ

キュー

f:id:azuuun:20160413012337p:plain

スタック

f:id:azuuun:20160413012340p:plain

Rubyでどう書くか

キュー

sushi = %w(まぐろ サーモン いくら とびっこ)
p sushi.push('うに')    # うにをIN
p sushi.first                # 最初に入れた要素を参照する
p sushi.shift              # 最初の要素(まぐろ)を取り出す
p sushi
["まぐろ", "サーモン", "いくら", "とびっこ", "うに"]
"まぐろ"
"まぐろ"
["サーモン", "いくら", "とびっこ", "うに"]

スタック

sushi = %w(まぐろ サーモン いくら とびっこ)
p sushi.push('うに')   # うにをIN
p sushi.last                # 最後に入れた要素を参照する
p sushi.pop               # 最後に入れた要素(うに)を取り出す
p sushi
["まぐろ", "サーモン", "いくら", "とびっこ", "うに"]
"うに"
"うに"
["まぐろ", "サーモン", "いくら", "とびっこ"]

参考

たのしいRuby 第5版

たのしいRuby 第5版