[プログラミング] スタックとキューの違い

プログラマーと話をしていると、「スタックする」と「キューに入れる」を本当に理解しているのか？と思う時がある。 何より自分も、これらをちゃんと理解できていなかったので、仕様について設計をする際に、混乱しないように、 ちゃんと知識をスタック・・・いや。キューして、記憶を整理しておきたいと思います。

スタックとキューについて

スタックとキューは、どちらもデータを一時的に保持する処理の事を言います。 一般的な知識としての説明を書きます。

Stack : スタック

LIFO (Last In First Out) 後入れ先出し。 データを後ろから入れて（push)、 最後のデータから取り出す(pop)。 下記の順番に処理する。 [ A , B , C ] ← D D → C → B → A

Queue : キュー

FIFO(First In First Out) 先入れ先出し。 データを追加（Enqueue : エンキュー）して、 データを取り出す(Dequeue : デキュー)すして処理する。 下記の順番に処理する。 [ A , B , C ] ← D A → B → C → D

用途での使い分け

Stack : スタック

スタックは、パソコン操作のUNDOや、ブラウザ履歴のような、最後に行った操作を再現する時に利用します。 コールスタック プログラム関数の呼び出しの際に、戻り値を一旦スタックに積んで、戻すときに、逆順にする処理 A() -> B() -> C() => C() -> B() -> A() 再帰処理や深さ優先探索（DFS） 木構造やグラフ探索で、次に探索すべきノードをスタックに積む。 例：迷路探索やコンパイラの構文解析など。

Queue : キュー

キューは、順番待ち処理として、複数処理を順番に登録した順にこなしていく時に使われます。

タスクの順番処理

ジョブキュー、プリントキュー、メッセージキューなど。 幅優先探索（BFS） グラフ探索で、次に訪れるノードをキューに追加し、先頭から取り出して探索。 例：最短経路探索（ダイクストラ法など）。 非同期処理のイベント待ち JavaScript のイベントループや、Node.js のイベントキューが代表例。 CPUのプロセススケジューリング ラウンドロビン方式などで、処理待ちタスクをキューで管理。 通信データの送受信バッファ ネットワークやストリーム処理で、データの順序を維持したまま処理。

あとがき

普通に処理をする感覚は、キューで処理するのがいいけど、 一時的に直前処理を優先的に使う、アンドゥーのような場合に、スタックを使うという感覚が理解できれば、 スタックとキューを使い分けられるようになります。 単語と使用イメージを理解できました？