JavaScriptでスタックとキューをマスターしよう！初心者向けチュートリアル

2024-04-18

JavaScriptでスタックとキューを実装する方法

スタックとキューは、コンピュータサイエンスにおいて重要なデータ構造です。それぞれ異なる動作を持ち、様々な場面で利用されています。

このチュートリアルでは、JavaScriptを使って、スタックとキューをどのように実装できるのかを解説します。

スタックは、**後入れ先出し（LIFO）**と呼ばれる動作を持ちます。つまり、最後に追加された要素が最初に取り出される構造です。

イメージとしては、お皿の積み重ねに似ています。一番上に置いたお皿から順番に取り出していくようなものです。

スタックの操作

スタックには、以下の基本的な操作があります。

  • push: スタックに要素を追加します。
  • pop: スタックから最後の要素を取り出します。
  • isEmpty: スタックが空かどうかを確認します。
class Stack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(stack.isEmpty()); // false

イメージとしては、行列に似ています。最初に並んだ人が最初に順番に処理されるようなものです。

キューの操作

  • enqueue: キューに要素を追加します。
  • front: キューの最初の要素を取得します。
class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue()); // 1
console.log(queue.front()); // 2
console.log(queue.isEmpty()); // false

応用例

スタックとキューは、様々な場面で利用されています。以下に、いくつかの例を紹介します。

  • ブラウザの履歴: ブラウザの履歴は、スタックを使って実装することができます。新しいページに移動するたびに、現在のページをスタックに追加します。戻るボタンを押すと、スタックから最後のページを取り出して表示します。
  • タスク管理: タスク管理システムでは、キューを使ってタスクを管理することができます。新しいタスクが追加されると、キューの末尾に追加されます。タスクを処理する際には、キューの先頭のタスクを取り出して処理します。
  • 深さ優先探索: 深さ優先探索と呼ばれるグラフ探索アルゴリズムでは、スタックを使って探索履歴を管理することができます。

スタックとキューは、基本的なデータ構造ですが、様々な場面で利用されています。JavaScriptを使って、これらのデータ構造を自分で実装することで、動作原理を理解し、応用力を身につけることができます。

  • [【JavaScript】Arrayオブジェクト(スタック


スタック

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

  push(item) {
    this.items.push(item);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(stack.isEmpty()); // false

キュー

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

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue()); // 1
console.log(queue.front()); // 2
console.log(queue.isEmpty()); // false
  • push と enqueue は、それぞれスタックとキューに要素を追加するメソッドです。

これらのメソッドを使って、スタックとキューを様々な用途で利用することができます。

このサンプルコードはあくまでも基本的な例です。

実際の利用状況に合わせて、様々な機能を追加することができます。

例えば、以下のような機能を追加することができます。

  • スタックとキューの要素の型を制限する
  • スタックとキューをシリアル化/デシリアライズする

これらの機能を追加することで、より汎用性の高いスタックとキューを実装することができます。



JavaScriptでスタックとキューを実装するその他の方法

Generator を用いると、スタックとキューの操作をより簡潔に記述することができます。

例：

function* stack() {
  let items = [];

  yield function push(item) {
    items.push(item);
  };

  yield function pop() {
    if (items.length === 0) {
      return undefined;
    }
    return items.pop();
  };

  yield function peek() {
    if (items.length === 0) {
      return undefined;
    }
    return items[items.length - 1];
  };

  yield function isEmpty() {
    return items.length === 0;
  };
}

const stackGen = stack();
const stackPush = stackGen.next().value.push;
const stackPop = stackGen.next().value.pop;
const stackPeek = stackGen.next().value.peek;
const stackIsEmpty = stackGen.next().value.isEmpty;

stackPush(1);
stackPush(2);
stackPush(3);

console.log(stackPop()); // 3
console.log(stackPeek()); // 2
console.log(stackIsEmpty()); // false

ES6 シンボルを用いると、より直感的な名前でスタックとキューの操作を定義することができます。

class Stack {
  constructor() {
    this._items = [];
    this[Symbol.iterator] = function* () {
      for (let item of this._items) {
        yield item;
      }
    };
  }

  push(item) {
    this._items.push(item);
  }

  pop() {
    if (this._items.length === 0) {
      return undefined;
    }
    return this._items.pop();
  }

  peek() {
    if (this._items.length === 0) {
      return undefined;
    }
    return this._items[this._items.length - 1];
  }

  isEmpty() {
    return this._items.length === 0;
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(...stack); // [3, 2, 1]
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(stack.isEmpty()); // false

第三者ライブラリを用いた実装

Underscore.js や Ramda.js などのライブラリは、スタックとキューを含む様々なデータ構造を効率的に扱うためのユーティリティを提供しています。

const _ = require('underscore');

const stack = _.stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(_.isEmpty(stack)); // false

これらの方法は、それぞれ異なる利点と欠点を持っています。

  • Generator: 簡潔で分かりやすいコード記述が可能だが、パフォーマンス面で劣る場合がある。
  • ES6 シンボル: 直感的な名前で操作を定義できるが、比較的新しい機能であり、古いブラウザではサポートされない可能性がある。
  • 第三者ライブラリ: 汎用性が高く、パフォーマンスも良好だが、ライブラリの追加読み込みが必要となる。

状況に応じて最適な方法を選択することが重要です。


javascript data-structures stack

【超便利】JavaScript 関数存在チェック：Optional Chainingでスマートに

typeof演算子は、オペランドのデータ型を返します。関数が存在する場合は "function" が返されます。in演算子は、プロパティまたはキーがオブジェクトに存在するかどうかを確認するために使用されます。関数オブジェクトは、関数に関する情報を提供します。関数オブジェクトが存在する場合は、関数が定義されていることになります。...

 
javascript reflection 【超便利】JavaScript 関数存在チェック：Optional Chainingでスマートに

初心者でも安心！jQueryでドロップダウンリストの選択値を変更する3つのコツ

JavaScriptの基本的な知識jQueryライブラリの理解上記のサンプルコードでは、以下の方法でドロップダウンリストの選択値を変更しています。特定の値を選択する$("#my-select").val("2")このコードは、my-select IDを持つドロップダウンリストの選択値を "2" に設定します。...

 
javascript jquery asp.net 初心者でも安心！jQueryでドロップダウンリストの選択値を変更する3つのコツ

【進化版】クライアントサイドとサーバーサイドの連携：API、WebSockets、SSE、WebRTCで実現する高度なウェブアプリケーション

クライアントサイドプログラミングは、ユーザーのブラウザ上で直接実行されるコードを指します。HTML、CSS、JavaScriptが代表的な言語で、主に以下の役割を担います。ユーザーインターフェース（UI）の表示と操作: ボタンのクリック、フォームの入力、アニメーションなど、ユーザーがウェブページとインタラクションする際の動作を制御します。...

 
javascript php client side 【進化版】クライアントサイドとサーバーサイドの連携：API、WebSockets、SSE、WebRTCで実現する高度なウェブアプリケーション

【初心者向け】JSXでコンポーネントを別のファイルで利用する方法: "export default" 完全ガイド

デフォルトエクスポートとはJavaScriptでは、モジュールから複数の値をエクスポートできます。その方法には、デフォルトエクスポートと名前付きエクスポートの2種類があります。デフォルトエクスポート: モジュールから1つの値のみをエクスポートする...

 
javascript reactjs 【初心者向け】JSXでコンポーネントを別のファイルで利用する方法: "export default" 完全ガイド

npm競合でプロジェクトが止まる前に！ 原因と解決策をわかりやすく解説

Node. js プロジェクトで npm を使用する場合、package. json と package-lock. json という 2 つの重要なファイルが生成されます。package. json は、プロジェクトに必要な依存関係とそのバージョンを宣言します。...

 
javascript node.js npm npm競合でプロジェクトが止まる前に！ 原因と解決策をわかりやすく解説

SQL SQL SQL SQL Amazon で見る