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

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

スタックは「最後に入れたものを最初に取り出す(後入れ先出し)」、キューは「最初に入れたものを最初に取り出す(先入れ先出し)」データ構造です。「積み重ねた本」と「行列」の違いをイメージすると分かりやすいです。Pythonではリストのappend()とpop()でスタックを、collections.dequeでキューをそれぞれ効率よく実現できます。

サンプルコードでは、リストの.append()で末尾に追加し.pop()で末尾から取り出すことでスタックを、dequeの.append()と.popleft()でキューを再現しています。dequeは「両端キュー」の略で、リストより先頭からの取り出しが高速に行える専用のデータ構造です。

初心者がよくつまずくのが、リストでキューを実現しようとして.pop(0)を使ってしまうことです。これは動作こそしますが、データ量が多いと処理が遅くなるため、キューにはdequeを使うのが実務での定石です。どちらのデータ構造を選ぶかで、処理の順序やアルゴリズムの効率が大きく変わってきます。

ブラウザの「戻る」機能はスタック、印刷待ちの処理やタスクの順番待ちはキューというように、身近な仕組みの裏側でもよく使われている基本的なデータ構造です。