スタックとキュー — 積む山と、並ぶ行列
プログラムの世界には「データを一時的にためておいて、あとで取り出す」場面が無数にあります。そのとき必ず問われるのが、どの順番で取り出すか。代表的な答えが2つあります — 本を積み上げて上から取るスタックと、行列の先頭から抜けるキューです。
言葉で覚えるより、触ったほうが早いです。下の図1で「荷物を追加」を何回か押してから、それぞれの「取り出す」を押してみてください。同じ順番で入れたのに、出てくる順番が逆になります。
STACK — 積み上げる山(LIFO)
まだ空っぽ
出てきた順: —
QUEUE — 並ぶ行列(FIFO)
出口→
まだ空っぽ
出てきた順: —
図1 — 同じ順で入れて、出てくる順を比べる
「あとから来たのが先」か、「先に来たのが先」か
スタックはLIFO(Last In, First Out)。最後に積んだ本がいちばん上にあるので、取り出すのも最後に入れたものからです。一方キューはFIFO(First In, First Out)。レジの行列と同じで、先に並んだ人から順に処理されます。仕組みはこれだけですが、この「順番の性格」の違いが、使われる場面をきれいに分けます。
スタックが向いているのは「直前の状態に戻りたい」場面です。エディタのUndo(直前の操作から取り消す)、ブラウザの戻るボタン、関数呼び出しの記録(コールスタック)— どれも「新しいものから巻き戻す」動きです。
キューが向いているのは「来た順に公平に処理したい」場面です。プリンタの印刷待ち、メッセージの配送、Webサーバーへのリクエスト処理 — 先に頼んだ人を追い越さないことが大事な場面では、必ずキューが使われています。
用語ミニ辞書
- push / pop
- スタックに積む操作と、いちばん上から取る操作。
- enqueue / dequeue
- キューの最後尾に並べる操作と、先頭から取る操作。
- コールスタック
- 関数が関数を呼ぶたびに積まれ、終わると上から降ろされる記録帳。スタックの代表例。
まとめ
スタックとキューの違いは、たった1つ — 取り出す側がどっちかです。入れた側から取るのがスタック(LIFO)、反対側から取るのがキュー(FIFO)。「巻き戻したいならスタック、順番を守りたいならキュー」。この一言を覚えておけば、データ構造の選択で迷うことはぐっと減ります。