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

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

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

サンプルコードでは、array_push()で末尾に追加しarray_pop()で末尾から取り出すことでスタックを、array_push()で末尾に追加しarray_shift()で先頭から取り出すことでキューを再現しています。

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

どちらのデータ構造を選ぶかで、処理の順序やアルゴリズムの効率が大きく変わってきます。SplStackやSplQueueという専用のクラスも標準ライブラリに用意されており、より本格的な実装ではこちらが使われることもあります。