【スタック】

ここからの章(スタック・キュー)では、初めて「データ構造らしいデータ構造」を扱います。といっても、新しい文法は出てきません。スタックもキューも、配列の使い方に制限をかけて、名前をつけたものだからです。「制限をかける」ことがなぜ価値になるのか、それがこの章の裏テーマです。

スタックとは(LIFO)

スタック(stack)は、データを積み上げて、上からしか出し入れしない構造です。本を机に積むところを想像してください。新しい本は一番上に置く。取るときも一番上から。3冊積んだら、最初に取れるのは最後に置いた本です。

この「最後に入れたものが、最初に出てくる」性質を LIFO(Last In, First Out: 後入れ先出し)と呼びます。スタックの定義はこれだけです。操作は2つです。

push: 一番上に積む

pop: 一番上から取り出す

見覚えのある名前ですよね。配列のメソッドそのままです。つまりJavaScript/TypeScriptでは、配列をスタックとして使えます。専用のクラスもライブラリも要りません。

▶ 実行してみよう

popが返すのは "3冊目"、最後にpushしたものです。そしてpopは取り出した要素を配列から取り除くので(破壊的メソッド)、残りは ["1冊目", "2冊目"]。push と pop を末尾だけで繰り返す、これがスタックの全てです。

なお、「一番上に何があるかを、取り出さずに見たい」こともよくあります。これはpeekと呼ばれる操作で、stack[stack.length - 1] または stack.at(-1) で読むだけです(取り除かない)。

ちなみに、push も pop も末尾の操作なので O(1)です。配列の得意な場所だけを使っています。先頭をいじるunshift/shiftのような引っ越しコストは発生しません。スタックは「配列の速い操作だけで成立する構造」でもあるのです。

身の回りはスタックだらけ

この単純な構造が、ソフトウェアの至るところで動いています。

ブラウザの「戻る」ボタン。 ページを開くたびに履歴がpushされ、「戻る」でpopされる。最後に見たページに戻るのは、履歴がスタックだからです。

エディタのUndo(Ctrl+Z)。 操作をするたびに「操作の記録」がpushされ、Undoで最新の操作がpopされて取り消される。「最後にやったことから順に取り消す」。LIFOそのものです。