図 1: スタックへのプッシュ
仮にあなたがたくさんの本を管理を引き受けたとします。あなたはそのたくさん本をどのように管理しますか。これは人によっていろいろ違った方法を用いるでしょう。例えば、本の ISBN コード (本の裏表紙などに表示してある本の固有番号) 順に管理する人もいるでしょうし、本のジャンルごとに管理する人もいるでしょう。この場合、特に正解はないのですが、本の出し入れを依頼された際に便利、不便の差が出るでしょう。例えば、「コンピュータ関連」の「ネットワーク関連」の「よくわかるインターネット」という本を取り出す依頼があったとき、ISBN コードで管理していた場合、探し出すのに大変苦労するでしょう。しかしジャンルで管理していた場合にはこれは大変都合が良いです。では次のパターンはどうでしょうか。「チューニングの全て」という本を管理してくださいという依頼があったとき、これをジャンルで区別するとします。さて、これはどんなジャンルの本でしょうか。あなたはこの本のジャンルを確認するために、わざわざ本の内容を読まなければなりません。これでは時間がかかって仕方ないでしょう。もし ISBN コードで管理していればこれは簡単です。本に表示されている ISBN コードを確かめるだけであとは何も必要ありません。このように本の管理方法はどのような形で依頼があるかによって、最適な方法が変わってきます。これはコンピュータにデータを保存する時も同様で、そのデータの使われ方によって様々なデータの格納方法が存在します。このデータの格納方法のことをデータ構造 (Data structure)と呼びます。データ構造にはよく利用される基本となる構造がいくつかあります。
本の集まりの中から特定の本を指定したい時、通常はその順番、場所や題名などを指定します。例えば、左から 7 番目の本とか、机の上の本とか、または「図解コンピュータ」という題名の本のようにです。それはコンピュータでデータの集まりの中から、特定のデータを指定する時にも同様です。前から 7 番目のデータ、メモリアドレス 17 番地のデータ、「book」という名前を付けたデータというような具合です。さて、基本的なデータ構造にスタック (Stack) とキュー (Queue) というものがあります。これらはデータの出し入れに関して、特定のデータを指し示すような情報 (例で言えば順番や場所など) を必要としません。データを取り出す際には「取り出す」という指示だけ与えれば、ある決まったデータを取り出すことができます。これは一体どのように実現されているのでしょうか。実はスタックとキューは、データを入れる順番によって、取り出されるデータの順番が決まるという仕組みを持っています。具体的には、スタックでは後に入れたデータが先に取り出されます。一方、キューでは先に入れたデータが先に取り出されます。
スタックでは後に入れたデータが先に取り出されます。これは次のような状況を考えてみると良いでしょう。例えば、机の上に本を 1 冊ずつ積んでいきます。次に本を 1 冊ずつ取り出すとします。普通に考えれば上から、つまり最後に積んだ本から取り出すでしょう (わざわざ下から取り出すという意地悪はなしです)。これがスタックの考え方です。用語としてスタックにデータを入れることをプッシュ (Push)、データを取り出すことをポップ (Pop) といいます。ではここでもう少し詳しく見ていくことにしましょう。A、B、C というデータをスタックに出し入れするとします。
図 1 では順に、A をプッシュ、B をプッシュ、C をプッシュしています。データを下から積み上げるようなイメージです。では次にポップしてみましょう。
図 2 ではポップを 3 回行っています。スタックでは後に入れたデータが先に取り出されるのですから、積み上げられた山の上から順に取り出されていくようなイメージになります。このように後入れ先出しすることを LIFO (Last In First Out) といいます。ではスタックは一体どのような場面で使われているのでしょうか。実は一般的にコンピュータでは常にスタックが使われていて、数え切れないくらいのプッシュとポップが行われています。これはコンピュータの頭脳である CPU はスタックを利用して動いているからです (ほとんどの CPU はスタックを利用する前提で設計されています)。CPU では多くのデータを使用して処理をしますが、このデータの一時的な保管場所としてスタックを利用しています。この時、優先しなければならない処理のデータが上に積まれていくため、最後に積まれたデータを先に取り出すスタックはとても都合が良いのです。
キューでは先に入れたデータが先に取り出されます。これは現実によくある状況と似ています。例えば受付を待つ人が並んでいるとします。当然ですが、先に並んだ人は先に列から抜けて受付をしてもらえます。これがキューの考え方です。用語としてキューにデータを入れることをエンキュー (Enqueue)、取り出すことをデキュー (Dequeue) といいます。ではここでもう少し詳しく見ていくことにしましょう。A、B、C というデータをキューに出し入れするとします。前述のスタックと比べながら見ていくと良いでしょう。
図 3 では順に、A をエンキュー、B をエンキュー、C をエンキューしています。ここまでのイメージはスタックの場合と同じです。次にデキューしてみましょう。
図 4 ではデキューを 3 回行っています。キューでは先に入れたデータが先に取り出されるのですから、スタックの場合とは逆で、積み上げられた山の下から順に取り出されていくようなイメージになります。このように先入れ先出しすることを FIFO (First In First Out) といいます。ではキューは一体どのような場面で使われているのでしょうか。スタックと同様にキューもコンピュータで頻繁に使われています。その一例として、ネットワークでの通信処理があります。例えば、データを作成する処理がデータを作成して一時的な保管場所としてキューに入れます。そしてデータを送信する処理がキューからデータを取り出して送信していきます。これによりデータは正しい順番で送信することができます (仮にこれがキューではなくスタックだった場合、最初に作成されたデータは最後まで送信されずに残ってしまいます)。このようにキューは 2 つの処理 (例ではデータを作成する処理とデータを送信する処理) の間のデータの受け渡しによく使われます。
これまで見てきたように、スタックとキューを扱うために必要な指示は、データを「入れる」、データを「取り出す」という最低限の指示だけで済んでしまいます。この単純さ、扱いやすさが大きな特徴となっています。