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

このレッスンでは、スタックとキューという2つの基本的なデータ構造の違いを学び、目的に応じて使い分けられるようになることを目標にします。「JavaScript スタック キュー 違い」「JavaScript push pop shift」で調べている方向けです。

スタックは「最後に入れたものを最初に取り出す(後入れ先出し)」、キューは「最初に入れたものを最初に取り出す(先入れ先出し)」データ構造です。「積み重ねた本」と「行列」の違いをイメージすると分かりやすいです。JavaScriptでは配列のメソッドを使ってどちらも簡単に再現できます。

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

初心者がよくつまずくのが、.pop()と.shift()の違いです。どちらも配列から要素を1つ取り除きますが、popは末尾から、shiftは先頭から取り除く点が異なります。この違いを理解していないと、意図した順番でデータを取り出せません。またshiftは配列全体を詰め直すため、popより計算コストが高い点も覚えておくとよいでしょう。

実際の開発現場では、ブラウザの「戻る」機能はスタック、印刷待ちの処理やタスクの順番待ちはキューというように、身近な仕組みの裏側でもよく使われている基本的なデータ構造です。アルゴリズムを学ぶ最初のステップとして、多くの教科書で取り上げられる基本の考え方です。

JavaScriptの配列には、スタックとキューのどちらとしても使える汎用的なメソッドが揃っているため、専用のライブラリを使わなくても手軽にこれらのデータ構造を再現できるのが大きな利点です。