配列を使ったキューとスタック

はじめに

この記事は書籍「プロを目指す人のためのRuby入門」に掲載できなかったトピックを著者自らが紹介するアドベントカレンダーの7日目です。
本文に出てくる章番号や項番号は書籍の中で使われている番号です。

この記事では配列を使ったキューとスタックを説明していきます。

必要な前提知識

「プロを目指す人のためのRuby入門」の第4章まで読み終わっていること。

配列を使ったキューとスタック

配列はキューやスタックとして使うこともできます。

キュー

キューは最初に入れたデータを最初に取り出すデータ構造です。このデータ構造はFIFO（First In First Out、先入れ先出し）と呼ばれることもあります。イメージ的には遊園地の入り口に並んだお客さんが順番に中へ入っていく様子を想像するとわかりやすいかもしれません。

配列をキューとして使う場合は、要素の追加にpushメソッドを（<<でも可）、要素の取得と削除にshiftメソッドを使います。

queue = []

# 要素を末尾に追加する
queue.push '田中'
queue.push '鈴木'
queue #=> ["田中", "鈴木"]

# 先頭の要素を取得して削除する
queue.shift #=> "田中"
queue.shift #=> "鈴木"
queue       #=> []

スタック

スタックは最後に入れたデータを最初に取り出すデータ構造です。このデータ構造はLIFO（Last In First Out、後入れ先出し）と呼ばれることもあります。イメージ的には洗ったお皿を棚にしまい、そのお皿を棚から出す様子を想像するとわかりやすいかもしれません。

配列をスタックとして使う場合は、要素の追加にpushメソッドを（<<でも可）、要素の取得と削除にpopメソッドを使います。

stack = []

# 要素を末尾に追加する
stack.push '大きい皿'
stack.push '小さい皿'
stack #=> ["大きい皿", "小さい皿"]

# 末尾の要素を取得して削除する
stack.pop #=> "小さい皿"
stack.pop #=> "大きい皿"
stack     #=> []

なお、配列の先頭に要素を追加したい場合はunshiftメソッドを使います。

fruits = ['melon', 'orange']
fruits.unshift 'apple'
fruits #=> ["apple", "melon", "orange"]

参考：prependとappend（Ruby 2.5）

Ruby 2.5ではunshift/pushのエイリアスメソッドとしてprepend/appendが追加されました。
Ruby 2.5以降であればこちらを使っても構いません。

array = [3, 4]
array.prepend(1, 2) #=> [1, 2, 3, 4]
array               #=> [1, 2, 3, 4]

array = [1, 2]
array.append(3, 4)  #=> [1, 2, 3, 4]
array               #=> [1, 2, 3, 4]

• サンプルコードでわかる！Ruby 2.5の主な新機能と変更点 - Qiita

次回予告

次回は配列の便利メソッドをあれこれ紹介します。