JavaScriptでスタックとキューを理解する

この記事は以下の方を対象に書いています。

スタックとキューについて、基礎から学びたい
JavaScriptでスタックまたはキューの仕組みを実装したい

スタックとキューについて
1. スタックとは？
2. キューとは？
スタックの実装例
キューの実装例
最後に

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

スタックとキューとは、簡単に言うと値の出し入れに特化したデータ構造のことです。

このデータ構造は、コンビニだったり、お皿のしまい方など、現実世界でもよく目にします。

今回は、JavaScriptを使って、スタックとキューについて解説していきます。

スタックとは？

まず、スタックについて説明します。

スタック（Stack）とは、後入れ先出し（LIFO：Last In First Out）のデータ構造です。

アプリでよくある取消機能は、一連の操作を履歴に保存し、一番新しい操作を取り消すことで

取り消しの操作を成立させることが可能です。

現実世界では、ハイチューを想像すると分かりやすいかもです。

キューとは？

キュー（Queue）とは、先入れ先出し（FIFO：First In First Out）のデータ構造のことです。

先に入れたものから、先に出ていくのがキューです。

コンビニのレジに並ぶ時を想像すると、分かりやすいかもです。

スタックの実装例

では、JavaScriptでスタックの実装をしてみます。

class Stack {
  constructor() {
    this.items = [];
  }

  // 要素の追加
  push(element) {
    this.items.push(element);
  }

  // 要素の取り出し
  pop() {
    if (this.items.length === 0) return 'スタックは空です。';
    return this.items.pop();
  }
}

const stack = new Stack();

console.log(stack.pop()); // スタックは空です。

// スタックに要素を追加
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop()); // 3 最新の要素を取り出して表示
console.log(stack.pop()); // 2 最新の要素を取り出して表示 ※3は消えているので2が表示される

// 実行結果
// スタックは空です。
// 3
// 2

これで、後入れ先出し（LIFO）の実現ができました。

キューの実装例

次は、キューの実装をしてみます。

class Queue {
  constructor() {
    this.items = [];
  }

  // 要素の追加
  enqueue(element) {
    this.items.push(element);
  }

  // 要素の取り出し
  dequeue() {
    if (this.items.length === 0) return 'キューは空です。';
    return this.items.shift();
  }
}

const queue = new Queue();

console.log(queue.dequeue()); // キューは空です。

// キューに要素を追加
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue()); // 1 最初の要素を取り出して表示
console.log(queue.dequeue()); // 2 最初の要素を取り出して表示 ※1は消えているので2が表示される

// 実行結果
// キューは空です。
// 1
// 2

これでキューの実装もできました。

JavaScriptには、配列を操作するために便利なメソッドがあるので、他の言語より比較的簡単です。

詳しくは、以下の記事でも解説していますので、良ければ！