はじめに
キューとスタックは格納したデータの取り出し方に特徴をもつデータ構造である。
詳しくは割愛。以下はキューとスタックに詳しい記事。
その取り出し方からキューについてFIFO(First-In, First-Out)またはLILO(Last-In, Last-Out)、スタックについてFILO(First-In, Last-Out)またはLIFO(Last-In, First-Out)と呼ぶことがあるが、
「キューってFIFO, LILOどっちだっけ？」
または
「スタックってFILO, LIFOどっちだっけ？」
と混乱してしまうことがしばしばある。
同じことで何度も迷いたくないので、FIFO/LILO, FILO/LIFOのそれぞれ、どちらを使うべきかについて本記事で結論を出したい。
アプローチ
下記2つの方法で調査し、その結果を総合して判断する。
- 辞書の記載を調査する
- 技術記事で使われる頻度を調査する
1. 辞書の記載を調査する
各ワードが辞書にどう記載されているかを確認するため、IT用語辞典で検索した。
結果、以下のページがヒットした。
FIFOとは、複数の対象を取り扱う順序を表した用語で、最初に入れたものを最初に取り出す（先に入れたものを先に出す）方式のこと。
LIFOとは、複数の対象を取り扱う順序を表した用語で、最初に入れたものを最後に取り出す（先に入れたものを後に出す）方式のこと。会計の分野では「後入先出法」と呼ぶ。
ページが存在するのはFIFO, LIFOで、LILO, FILOはそれぞれの別名として記載されている。つまり、例えばキューはFIFOと呼んでもLILOと呼んでも問題ないということのようだ。
しかし、FIFO, LIFOだけが立項されているということは、何か優先度の違いがあるのかもしれない。
2. 技術記事で使われる頻度を調査する
技術記事で使われる頻度が多い方が、技術者に受け入れられているワードであると推測できる。各ワードについてQiitaで検索し、ヒットした記事数を記録した。
| ワード | 検索ヒット数 |
|---|---|
| FIFO | 957 |
| LIFO | 243 |
| FILO | 39 |
| LILO | 33 |
(2022/3/5時点の検索結果)
どのワードも使われている記事は存在するが、その頻度には差がある。
結果を解釈するために2種類の観点でマトリクスを作成する。
Inの表し方に注目したマトリクス
| データ構造 \ Inの表し方 | First-In | Last-In |
|---|---|---|
| キュー | 957 | 33 |
| スタック | 39 | 243 |
キューでよく使われるのはFirst-In、スタックでよく使われるのはLast-Inである。
Outの表し方に注目したマトリクス
| データ構造 \ Outの表し方 | First-Out | Last-Out |
|---|---|---|
| キュー | 957 | 33 |
| スタック | 243 | 39 |
キュー、スタックに共通してFirst-Outがよく使われ、Last-Outはあまり使われない。
「In」よりも「Out」の違いの方が、使用頻度に強く影響しているといえる。
考察
1で辞書の記載を確認した結果では、キューはFIFO, スタックはLIFOが立項されていた。
2でQiitaの記事数の調査では、First-Outがよく使われる傾向にあることが分かった。
両者の結果は一致したが、この結果についてデータ構造のどんな特徴に興味があるのかで考えれば説明できるのではないだろうか。
各ワードの興味とは、
First-Inなら「最初に入れたデータがいつ取り出されるのか」
Last-Inなら「最後に入れたデータがいつ取り出されるのか」
First-Outなら「次に取り出されるのはいつ入れたデータか」
Last-Outなら「最後に取り出されるのはいつ入れたデータか」
というところにある。どの見方で考えてもキューやスタックの特徴を表すことはできるが、実際にキューやスタックを使う場面を考えると、「次に取り出されるのはいつ入れたデータか」で考えるのが最も自然だと思われるため、First-Outがよく使われるのではないだろうか。
まとめ
FIFO/LILO, FILO/LIFOはどちらを使ってもよいが、First-Out(次に取り出されるのはいつ入れたデータか)に注目するのが自然と考えて
キューはFIFO スタックはLIFO
を使えば、大勢の感覚に合っているといえよう。