スタックとキュー(データ構造の基本)

このレッスンでは、スタックとキューという2つの基本的なデータ構造の違いを学び、Rubyでの実現方法を理解することを目標にします。「Ruby スタック キュー 実装」で調べている方向けの内容です。

スタックは「最後に入れたものを最初に取り出す(後入れ先出し)」、キューは「最初に入れたものを最初に取り出す(先入れ先出し)」データ構造です。「積み重ねた本」と「行列」の違いをイメージすると分かりやすいです。

サンプルコードでは、.pushで末尾に追加し.popで末尾から取り出すことでスタックを、.pushで末尾に追加し.shiftで先頭から取り出すことでキューを再現しています。同じ配列のメソッドでも、取り出す位置を変えるだけで全く違うデータ構造として振る舞う点に注目してみましょう。

初心者がよくつまずくのが、.popと.shiftの違いです。どちらも配列から要素を1つ取り除きますが、popは末尾から、shiftは先頭から取り除く点が異なります。この違いを理解していないと、意図した順番でデータを取り出せません。

どちらのデータ構造を選ぶかで、処理の順序やアルゴリズムの効率が大きく変わってきます。積み重ねた本と行列の違いをイメージすると、それぞれの動作の違いが分かりやすくなります。