スタック
スタックとは
積み重なった本のなかから、目的の本を探す場合、通常上から順に探していくことになります。上にある本ほど、最近積んだ本であることから、このような状況で目的の本を探すと、新しく積まれたものから探すことになります。
このように、要素の挿入と削除がリストの先頭だけで行われるようなデータ構造を、スタックと言います。「最後に入れたものを最初の取り出す」データ構造であることから、LIFO(Last In, First Out)のデータ構造と言います。
ワープロは表計算ソフトなどのように、操作を「元に戻す」で、取り消すことができるようなものがあります。ここで使われているデータの仕組みこそ、まさしくこのスタックなのです。(図2-1.)
図2-1.スタック構造
プッシュとポップ
スタックに データを積むことをプッシュ(push)，スタックからデータを取り出すことをポップ (pup)と呼びます。スタックの途中のデータを取り出すことは許されません。
プログラミング言語による実装
スタックの、各言語による実装は、以下の通りです。
キュー
キューとは
スタックの正反対の概念がキューです。典型的な例が行列で、例えば人気のレストランなどで客が行列を作ると、先に並んだ客ほど早く店内に入れます。事実、このキューという言葉自体、行列を意味する言葉なのです。
このように、最初に入れたデータが、最初に取り出せるようなデータ構造のことを、FIFO(First In First Out)と呼びます。スタックとは正反対の概念であることがわかります。（図2-2.）
図2-2.キュー構造
リングバッファ
FIFOを続けていると、すぐにメモリーの端に到達し，データの追加が出来なくなってしまいます。そこで、データを追加したり取り出したりする毎に，データの列を移動させることも考えらます。しかし、それでは計算量が増加して効率的ではありません。そこで、これを防ぐために，リングバッファと言うものが考えられました。
これは、キューの配列の先頭と末尾を結びつけ、あたかもひとつの環（リング）であるかのような構造にし、キューの使用回数を無制限にするための工夫です。(図2-3.)
図2-3.リングバッファ
プログラミング言語による実装
キューの、各言語による実装は、以下の通りです。
 |  |  |
