リストは、Webページをリンクで繋ぐのと同様の考え方でデータを管理します。自分のページに友達のページへリンクを張ると、自分のページから友達のページへたどることができます。リストは、データとデータをリンクで接続して、順番にデータを辿れるようにしたものです。
スタックは、直近のデータから古い順にさかのぼってデータを取り出していきたいときに利用します。直近(最後)に入れたデータを最初に取り出せるので、後入先出(Last In First Out:LIFO)のデータ構造であると言います。
キューは、データを格納した順に取り出したいときに利用します。最初に入れたデータを最初に取り出せるので、先入先出し(First IN First Out:FIFO)のデータ構造であると言います。
1:リスト(線形リスト)
リストを構成する一つ一つのデータをリストの要素と言います。
リストの要素は、レコード型の変数です。データを入れる項目と、自分の次の要素のアドレスを入れる項目を持っています。基本情報技術者試験では、要素のアドレスとして配列の要素番号が使われることが多いです。CやJavaなどのプログラムでは、要素のアドレスとしてメモリの番地やオブジェクトへの参照を使うこともあります。なお、リストの末尾要素の.next部分には、NULL(未定義の値)や−1を入れ、次がないことを表します。
リストでデータを扱うと、リンクの繋ぎ換えをするだけで、途中にデータを挿入したり、途中からデータを削除したりすることができ、多くのデータがある時でも少ない手間で挿入・削除処理を行えます。
2:スタック
スタックは、データを積み重ねて管理するイメージです。積み重ねてある部分が「スタック」です。スタックにデータを格納することをプッシュ(PUSH)、スタックからデータを取り出すことをポップ(POP)と言います。データをPUSHすると、スタックの一番上に置かれます。POPすると、スタックの一番上からデータを取り出します。スタックの途中からデータを取り出すことはできません。
3:キュー
キューは、データを行列に並べて管理するイメージです。キューにデータを格納することをエンキュー(ENQUEUE)、キューからデータを取り出すことをでキュー(DEQUEUE)と言います。エンキューをENQ、でキューをDEQと省略して書くことも多いです。データをENQすると、行列の最後尾に置かれます。DEQすると、行列のセントからデータを取り出します。キューの途中からデータを取り出すことができません。