スタックとキューの意味と例、覚え方

基本的なデータ構造である、スタックとキューについて解説します。

スタックとは

スタックとは、後に入れたデータを先に取り出すようなデータ構造です。
スタックの意味

Aを入れる
→Bを入れる
→取り出せるのは、後に入れたデータであるB

・スタックにデータを追加することをプッシュと言います。
・スタックからデータを取り出すことをポップと言います。

スタックの例

スタックの身近な例としては、
・食堂で山積みになっているトレイ
・カップスタック(カップを決められた形に積み上げていく競技)
・奥行きのある靴箱
などが挙げられます。全て、取り出せるのは一番最後に入れたもの(置いたもの)です。

スタックは新しいものから処理していくイメージです。深さ優先探索の実装に使われたりします。

なお、後入れ先出しのことを、LIFO(Last In First Out)と表現することがあります。後入れ先出しは、先入れ後出しとも言えるので、FILO(First In Last Out)と表現することもあります。

キューとは

キューとは、先に入れたデータを先に取り出すようなデータ構造です。
キューの例

Aを入れる
→Bを入れる
→取り出せるのは、先に入れたデータであるA

・キューにデータを追加することをエンキューと言います。
・キューからデータを取り出すことをデキューと言います。

キューの例

キューの身近な例としては、
・レジなどの待ち行列
・スーパーの、飲み物などの陳列(裏から新しいものを補充して、お客さんは手前から取っていく)
・ロケット鉛筆
などが挙げられます。いずれも、取り出せるのは一番最初に入れたものです。

キューは古いものから処理していくイメージです。幅優先探索の実装に使われたりします。

なお、先入れ先出しのことを、FIFO(First In First Out)と表現することがあります。

スタックとキューの覚え方

スタックと、キューは混同しがちなので、私は以下のように覚えています。

・スタックの例には、カップスタックがある。(カップを積み重ねていく。新しいものから取る)
→ スタックは後入れ先出し

・ビリヤードで使う棒のことをキューと言う。ビリヤードは玉突き(一番古いものが飛び出してくる)のイメージがある。
→ キューは先入れ先出し

ちなみに、ビリヤードのキューは、英語で cue ですが、データ構造のキューは、queue なので、別の単語です。

次:グラフを表すデータ構造(隣接行列と隣接リスト)
前:小数点つき10進数を2進数に変換する方法とツール

スポンサーリンク

スポンサーリンク

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る