スタックとキューとは?

コンピューターにおけるデータの管理、構造の話をするときに、スタックとキューという言葉が出てきます。

情報処理やプログラミング言語などを勉強すると、一番最初に出てくる言葉のひとつです。

  • スタック・・・縦に積み重ねたイメージ、後入先出
  • キュー・・・横に並べたイメージ、先入先出

スタック

stack スタックとは、積み重ねるの意味。トレイや皿をイメージします。

たくさんのトレイが重なっていて、取ることができるのは、一番上のものです。

スタック

後に入れたものが 先に取り出されます。後入先出。LIFO(Last In Farst Out)ライフォ。

データを一番上に積むこと、追加することをプッシュ、取り出すことをポップといいます。

キュー

queue キューとは、順番待ちの列の意味。待ち行例をイメージします。

単純に順番通りです。先に並んでいる人が、入場したり乗車します。

キュー

先に入れたものが 先に取り出されます。先入先出。FIFO(Farst In Farst Out)ファイフォ。

データを追加、挿入することをエンキュー、取り出すことをデキューといいます。

身近なところだと、プリンターの印刷です。各パソコンから複数の出力があった場合、順番待ちで印刷されます。

両端キュー

両端からエンキューとデキューを行うことができるキューを、両端キューといいます。

両端キュー

スタックとキューを合わせたような構造です。

優先度付きキュー

優先度の値が付加されたキュー。値が小さい、大きいなどで優先度を決めます。例えば、値が小さいほど優先度が高いとします。

優先度付きキュー

優先度付きキューでは、データを挿入した順番ではなく、優先度の高いものからデータが取り出されます。

身近なところだと、OSのプログラム管理(プロセス管理)で使われています。