前回、科目Bに戻り、クイックソート・マージソートの仕組みを整理しました。今回は、同じくデータ構造の基本として、「スタック」と「キュー」を整理します。
スタックとキューとは
スタックとキューは、どちらもデータを一列に並べて管理する仕組みですが、「どの順番でデータを取り出すか」というルールが異なります。
スタック(後入れ先出し)
スタックは、最後に入れたデータを、最初に取り出す、というルールで管理されます。この考え方を「後入れ先出し(LIFO:Last In First Out)」と呼びます。
イメージとしては、積み重ねた本の山に近いものです。新しい本を積むときは一番上に置き、取り出すときも一番上から取っていきます。下のほうにある本を先に取り出すことはできません。
スタックへのデータの追加は「push(プッシュ)」、取り出しは「pop(ポップ)」と呼ばれます。
キュー(先入れ先出し)
キューは、最初に入れたデータを、最初に取り出す、というルールで管理されます。この考え方を「先入れ先出し(FIFO:First In First Out)」と呼びます。
イメージとしては、レジに並ぶ行列に近いものです。先に並んだ人から順番に処理されていき、あとから並んだ人は、自分の前の人がすべて処理されるまで待つことになります。
キューへのデータの追加は「enqueue(エンキュー)」、取り出しは「dequeue(デキュー)」と呼ばれます。
トレースするときの注意点
スタックとキューのトレース問題では、「今、どんな順番でデータが並んでいるか」を、追加・取り出しのたびに書き出すようにしています。
特に間違えやすいのが、スタックとキューを混同してしまうことです。「後入れ先出し」と「先入れ先出し」という言葉だけでは覚えにくいので、自分は「スタックは本の山」「キューはレジの行列」というイメージに置き換えて、混同しないようにしています。
具体例で確認する
例えば、「１、２、３」という順番でデータを追加した場合を考えます。
- スタックの場合:取り出す順番は「３、２、１」(最後に入れたものが先に出る)
- キューの場合:取り出す順番は「１、２、３」(最初に入れたものが先に出る)
同じ順番でデータを入れても、取り出す順番がまったく逆になる、という点が、この単元でいちばん間違えやすいポイントだと感じています。
学習してみた感想
スタックとキューは、言葉だけで覚えようとすると混同しやすいのですが、「本の山」と「レジの行列」という身近なイメージに結びつけたことで、迷わず判断できるようになりました。用語を無理に暗記するのではなく、自分の生活の中にある具体例に置き換えることの効果を、改めて実感しています。
次回は、①に戻り、OSの仮想記憶・ページング方式を整理します。
