MENU
  1. ホーム
  2. JavaScript
  3. JavaScriptでの配列を使ったスタックとキューの実装方法

JavaScriptでの配列を使ったスタックとキューの実装方法

JavaScript

JavaScriptはウェブ開発において最も広く使われているプログラミング言語の一つであり、その中でスタックとキューは非常に重要なデータ構造です。スタックは「後入れ先出し（LIFO）」の原則に従い、最後に追加された要素が最初に取り出されます。一方、キューは「先入れ先出し（FIFO）」の原則に従い、最初に追加された要素が最初に取り出されます。これらのデータ構造は、アルゴリズムの実装や問題解決において非常に役立ちます。本記事では、JavaScriptの配列を使ってスタックとキューをどのように実装するかを詳しく解説します。また、それぞれのメソッドの使い方や応用例についても紹介し、実際の開発に役立つ知識を提供します。

目次

スタックとは何か

スタックはデータ構造の一つで、「後入れ先出し（LIFO: Last In, First Out）」の原則に基づいて動作します。これは、最後に追加された要素が最初に取り出されることを意味します。スタックの典型的な使用例としては、関数呼び出しの管理やブラウザの履歴機能があります。

スタックの特徴

スタックの主な特徴には以下のものがあります。

  • 後入れ先出し：最後に追加された要素が最初に取り出されます。
  • 一端操作：要素の追加（プッシュ）と削除（ポップ）はスタックの一端で行われます。
  • メモリ管理：関数の呼び出しとリターンに使用されることが多いです。

スタックの主な使用例

  • 関数呼び出しの管理：プログラムが関数を呼び出すと、現在の実行状態をスタックに保存し、関数の実行が終了するとスタックから実行状態を復元します。
  • ブラウザの履歴機能：ユーザーが閲覧したページをスタックに保存し、「戻る」ボタンを押すとスタックからページを取り出します。
  • テキストエディタのアンドゥ機能：編集履歴をスタックに保存し、アンドゥ操作で直前の状態に戻します。

これにより、スタックはさまざまな場面で効率的なデータ管理を可能にします。

JavaScriptでのスタック実装

JavaScriptでは、配列を使ってスタックを簡単に実装することができます。配列のメソッドであるpushとpopを活用することで、スタックの基本操作を実現できます。

スタックの実装手順

以下のステップで、JavaScriptの配列を使ってスタックを実装します。

1. スタッククラスの作成

まず、スタックのクラスを作成します。このクラスには、スタックの操作を行うメソッドを定義します。

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

2. 要素を追加するメソッド（push）の実装

スタックに要素を追加するためのpushメソッドを実装します。これは配列のpushメソッドを利用します。

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

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

3. 要素を削除するメソッド（pop）の実装

スタックから要素を削除するためのpopメソッドを実装します。これは配列のpopメソッドを利用します。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

4. スタックの状態を確認するメソッドの実装

スタックが空かどうかを確認するisEmptyメソッドを追加します。これにより、スタックが空の状態でpopを実行しようとした場合にエラーを防ぐことができます。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

    peek() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items[this.items.length - 1];
    }
}

これで、JavaScriptを使った基本的なスタックの実装が完了です。スタックのpush、pop、isEmpty、peekメソッドを使用して、スタックの操作が可能になります。次のセクションでは、これらのメソッドの詳細について説明します。

スタックのメソッド

スタックを操作するために使用する主なメソッドについて詳しく説明します。これらのメソッドを理解することで、スタックの基本操作が可能になります。

pushメソッド

pushメソッドは、スタックに新しい要素を追加するために使用されます。JavaScriptの配列においては、このメソッドは配列の末尾に要素を追加します。

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

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

// 使用例
let stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.items); // [1, 2]

popメソッド

popメソッドは、スタックの一番上にある要素を削除し、その要素を返します。スタックが空の場合、このメソッドは適切なメッセージを返します。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

// 使用例
let stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2
console.log(stack.items); // [1]

isEmptyメソッド

isEmptyメソッドは、スタックが空かどうかを確認するために使用されます。スタックが空の場合はtrueを、それ以外の場合はfalseを返します。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

// 使用例
let stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(1);
console.log(stack.isEmpty()); // false

peekメソッド

peekメソッドは、スタックの一番上にある要素を削除せずに返します。スタックが空の場合、このメソッドは適切なメッセージを返します。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

    peek() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items[this.items.length - 1];
    }
}

// 使用例
let stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 2
console.log(stack.items); // [1, 2]

これらのメソッドを組み合わせることで、スタックの基本操作を効率的に行うことができます。次のセクションでは、キューについて詳しく説明します。

キューとは何か

キューは、データ構造の一つで、「先入れ先出し（FIFO: First In, First Out）」の原則に基づいて動作します。これは、最初に追加された要素が最初に取り出されることを意味します。キューの典型的な使用例としては、プリンターのジョブ管理やタスクスケジューリングがあります。

キューの特徴

キューの主な特徴には以下のものがあります。

  • 先入れ先出し：最初に追加された要素が最初に取り出されます。
  • 両端操作：要素の追加（エンキュー）はキューの一端で行われ、削除（デキュー）は反対側の端で行われます。
  • 順序管理：タスクやプロセスの順序管理に適しています。

キューの主な使用例

  • プリンターのジョブ管理：プリンターはジョブを受け付けた順に処理します。これにより、ジョブが公平に処理されることを保証します。
  • タスクスケジューリング：オペレーティングシステムは、タスクやプロセスをキューに入れて順番に処理します。
  • ネットワークパケット管理：ルーターやスイッチは、ネットワークパケットをキューに入れて順次処理します。

これらの特徴により、キューはさまざまな場面で効率的なデータ管理を可能にします。次のセクションでは、JavaScriptを使ってキューをどのように実装するかについて説明します。

JavaScriptでのキュー実装

JavaScriptでは、配列を使ってキューを簡単に実装することができます。配列のメソッドであるpushとshiftを活用することで、キューの基本操作を実現できます。

キューの実装手順

以下のステップで、JavaScriptの配列を使ってキューを実装します。

1. キュークラスの作成

まず、キューのクラスを作成します。このクラスには、キューの操作を行うメソッドを定義します。

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

2. 要素を追加するメソッド（enqueue）の実装

キューに要素を追加するためのenqueueメソッドを実装します。これは配列のpushメソッドを利用します。

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

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

3. 要素を削除するメソッド（dequeue）の実装

キューから要素を削除するためのdequeueメソッドを実装します。これは配列のshiftメソッドを利用します。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

4. キューの状態を確認するメソッドの実装

キューが空かどうかを確認するisEmptyメソッドを追加します。これにより、キューが空の状態でdequeueを実行しようとした場合にエラーを防ぐことができます。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

    front() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items[0];
    }
}

これで、JavaScriptを使った基本的なキューの実装が完了です。キューのenqueue、dequeue、isEmpty、frontメソッドを使用して、キューの操作が可能になります。次のセクションでは、これらのメソッドの詳細について説明します。

キューのメソッド

キューを操作するために使用する主なメソッドについて詳しく説明します。これらのメソッドを理解することで、キューの基本操作が可能になります。

enqueueメソッド

enqueueメソッドは、キューに新しい要素を追加するために使用されます。JavaScriptの配列においては、このメソッドは配列の末尾に要素を追加します。

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

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

// 使用例
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.items); // [1, 2]

dequeueメソッド

dequeueメソッドは、キューの最前にある要素を削除し、その要素を返します。キューが空の場合、このメソッドは適切なメッセージを返します。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

// 使用例
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 1
console.log(queue.items); // [2]

isEmptyメソッド

isEmptyメソッドは、キューが空かどうかを確認するために使用されます。キューが空の場合はtrueを、それ以外の場合はfalseを返します。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

// 使用例
let queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue(1);
console.log(queue.isEmpty()); // false

frontメソッド

frontメソッドは、キューの最前にある要素を削除せずに返します。キューが空の場合、このメソッドは適切なメッセージを返します。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

    front() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items[0];
    }
}

// 使用例
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.front()); // 1
console.log(queue.items); // [1, 2]

これらのメソッドを組み合わせることで、キューの基本操作を効率的に行うことができます。次のセクションでは、スタックとキューの違いと用途の比較について説明します。

スタックとキューの比較

スタックとキューはどちらも重要なデータ構造ですが、それぞれ異なる特性と用途を持っています。このセクションでは、スタックとキューの違いを明確にし、それぞれの用途について比較します。

スタックとキューの基本的な違い

スタックとキューは、要素の追加と削除の順序が異なります。

スタックの特徴

  • LIFO（後入れ先出し）：最後に追加された要素が最初に取り出されます。
  • 一端操作：要素の追加と削除はスタックの同じ端で行われます。

キューの特徴

  • FIFO（先入れ先出し）：最初に追加された要素が最初に取り出されます。
  • 両端操作：要素の追加はキューの一端で、削除は反対側の端で行われます。

用途の比較

それぞれのデータ構造は、異なる状況での使用に適しています。

スタックの用途

  • 関数呼び出しの管理：関数の呼び出し元に戻る際にスタックを使用します。これにより、呼び出し元の状態を保持できます。
  • ブラウザの履歴管理：ユーザーが閲覧したページをスタックに保存し、戻るボタンで直前のページに戻ります。
  • アンドゥ機能：テキストエディタなどで、直前の操作を取り消すために使用されます。

キューの用途

  • プリンターのジョブ管理：プリンターはジョブを受け付けた順に処理します。これにより、ジョブが公平に処理されます。
  • タスクスケジューリング：オペレーティングシステムは、タスクやプロセスをキューに入れて順番に処理します。これにより、すべてのタスクが適切な順序で実行されます。
  • ネットワークパケット管理：ルーターやスイッチは、ネットワークパケットをキューに入れて順次処理します。これにより、パケットの順序が保たれます。

視覚的な比較

以下の表は、スタックとキューの特徴をまとめたものです。

特徴スタックキュー
データ構造のタイプLIFOFIFO
操作場所一端両端
主な用途関数呼び出し、履歴管理、アンドゥ機能ジョブ管理、タスクスケジューリング、パケット管理

これにより、スタックとキューの特性と用途の違いが明確になります。次のセクションでは、スタックの具体的な応用例としてブラウザの履歴管理の実装例を紹介します。

応用例：ブラウザの履歴管理

スタックの実用的な応用例として、ブラウザの履歴管理の実装を紹介します。ユーザーがウェブページを閲覧するとき、ブラウザはページの履歴をスタックに保存します。「戻る」ボタンを押すと、スタックの最上部からページが取り出され、直前のページに戻ります。

ブラウザ履歴管理の実装

JavaScriptを使って、ブラウザの履歴管理をスタックでシミュレートする方法を説明します。

1. 履歴管理クラスの作成

まず、ブラウザの履歴を管理するためのクラスを作成します。このクラスには、ページの訪問履歴を保存するためのスタックを定義します。

class BrowserHistory {
    constructor() {
        this.historyStack = new Stack();
        this.currentPage = null;
    }

    visit(page) {
        if (this.currentPage !== null) {
            this.historyStack.push(this.currentPage);
        }
        this.currentPage = page;
        console.log(`訪問: ${this.currentPage}`);
    }

    back() {
        if (this.historyStack.isEmpty()) {
            console.log("履歴がありません");
            return;
        }
        this.currentPage = this.historyStack.pop();
        console.log(`戻る: ${this.currentPage}`);
    }

    current() {
        return this.currentPage;
    }
}

2. スタッククラスの再利用

前述のスタッククラスを再利用して、履歴管理に必要なpush、pop、isEmptyメソッドを提供します。

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

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

    pop() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items.pop();
    }

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

    peek() {
        if (this.isEmpty()) {
            return "スタックは空です";
        }
        return this.items[this.items.length - 1];
    }
}

3. 使用例

ブラウザ履歴管理クラスを使って、ページの訪問と戻る機能をシミュレートします。

let browserHistory = new BrowserHistory();

browserHistory.visit("ページ1");
browserHistory.visit("ページ2");
browserHistory.visit("ページ3");
console.log(`現在のページ: ${browserHistory.current()}`); // ページ3

browserHistory.back(); // 戻る: ページ2
console.log(`現在のページ: ${browserHistory.current()}`); // ページ2

browserHistory.back(); // 戻る: ページ1
console.log(`現在のページ: ${browserHistory.current()}`); // ページ1

browserHistory.back(); // 履歴がありません
console.log(`現在のページ: ${browserHistory.current()}`); // ページ1

このように、スタックを使用することで、ブラウザの履歴管理機能を簡単に実装できます。次のセクションでは、キューの具体的な応用例としてプリンターのジョブ管理の実装例を紹介します。

応用例：プリンターのジョブ管理

キューの実用的な応用例として、プリンターのジョブ管理の実装を紹介します。プリンターは、ジョブを受け付けた順番に処理する必要があります。このFIFO（先入れ先出し）特性は、キューを使って実装するのに適しています。

プリンタージョブ管理の実装

JavaScriptを使って、プリンターのジョブ管理をキューでシミュレートする方法を説明します。

1. ジョブ管理クラスの作成

まず、プリンターのジョブを管理するためのクラスを作成します。このクラスには、ジョブを保存するためのキューを定義します。

class PrinterQueue {
    constructor() {
        this.jobQueue = new Queue();
    }

    addJob(job) {
        this.jobQueue.enqueue(job);
        console.log(`ジョブ追加: ${job}`);
    }

    processJob() {
        if (this.jobQueue.isEmpty()) {
            console.log("ジョブはありません");
            return;
        }
        const job = this.jobQueue.dequeue();
        console.log(`ジョブ処理中: ${job}`);
    }

    currentJob() {
        if (this.jobQueue.isEmpty()) {
            return "ジョブはありません";
        }
        return this.jobQueue.front();
    }
}

2. キュークラスの再利用

前述のキュークラスを再利用して、ジョブ管理に必要なenqueue、dequeue、isEmpty、frontメソッドを提供します。

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

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

    dequeue() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items.shift();
    }

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

    front() {
        if (this.isEmpty()) {
            return "キューは空です";
        }
        return this.items[0];
    }
}

3. 使用例

プリンタージョブ管理クラスを使って、ジョブの追加と処理をシミュレートします。

let printerQueue = new PrinterQueue();

printerQueue.addJob("ジョブ1");
printerQueue.addJob("ジョブ2");
printerQueue.addJob("ジョブ3");
console.log(`現在のジョブ: ${printerQueue.currentJob()}`); // ジョブ1

printerQueue.processJob(); // ジョブ処理中: ジョブ1
console.log(`現在のジョブ: ${printerQueue.currentJob()}`); // ジョブ2

printerQueue.processJob(); // ジョブ処理中: ジョブ2
console.log(`現在のジョブ: ${printerQueue.currentJob()}`); // ジョブ3

printerQueue.processJob(); // ジョブ処理中: ジョブ3
console.log(`現在のジョブ: ${printerQueue.currentJob()}`); // ジョブはありません

printerQueue.processJob(); // ジョブはありません

このように、キューを使用することで、プリンターのジョブ管理機能を簡単に実装できます。次のセクションでは、読者が学んだ内容を実践できるような演習問題を提示します。

演習問題

読者がスタックとキューの基本的な概念とJavaScriptでの実装を深く理解できるように、いくつかの演習問題を用意しました。これらの問題に取り組むことで、スタックとキューの操作に慣れることができます。

演習1: スタックの実装と操作

以下の手順に従って、スタックを実装し、基本的な操作を行ってください。

  1. 前述のスタッククラスをコピーして新しいファイルに貼り付けてください。
  2. スタックに以下の要素を順番に追加してください: 10, 20, 30, 40, 50
  3. スタックから3つの要素を取り出し、取り出した要素をコンソールに表示してください。
  4. スタックが空かどうかを確認し、結果をコンソールに表示してください。
let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);

console.log(stack.pop()); // 50
console.log(stack.pop()); // 40
console.log(stack.pop()); // 30

console.log(stack.isEmpty()); // false

演習2: キューの実装と操作

以下の手順に従って、キューを実装し、基本的な操作を行ってください。

  1. 前述のキュークラスをコピーして新しいファイルに貼り付けてください。
  2. キューに以下のジョブを順番に追加してください: “ジョブA”, “ジョブB”, “ジョブC”
  3. キューから2つのジョブを取り出し、取り出したジョブをコンソールに表示してください。
  4. キューが空かどうかを確認し、結果をコンソールに表示してください。
let queue = new Queue();
queue.enqueue("ジョブA");
queue.enqueue("ジョブB");
queue.enqueue("ジョブC");

console.log(queue.dequeue()); // ジョブA
console.log(queue.dequeue()); // ジョブB

console.log(queue.isEmpty()); // false

演習3: 応用問題

スタックとキューの特性を利用して、次の問題に取り組んでください。

  1. スタックを利用して、与えられた文字列が回文（前から読んでも後ろから読んでも同じ文字列）かどうかを判定する関数を作成してください。
  2. キューを利用して、タクシー待ち行列をシミュレートしてください。タクシーが到着するたびに待っている乗客を順番に乗車させてください。
// 回文判定関数
function isPalindrome(str) {
    let stack = new Stack();
    for (let char of str) {
        stack.push(char);
    }

    for (let char of str) {
        if (char !== stack.pop()) {
            return false;
        }
    }
    return true;
}

console.log(isPalindrome("radar")); // true
console.log(isPalindrome("hello")); // false

// タクシー待ち行列シミュレーション
let taxiQueue = new Queue();
taxiQueue.enqueue("乗客1");
taxiQueue.enqueue("乗客2");
taxiQueue.enqueue("乗客3");

console.log(`乗車: ${taxiQueue.dequeue()}`); // 乗客1
console.log(`乗車: ${taxiQueue.dequeue()}`); // 乗客2
console.log(`乗車: ${taxiQueue.dequeue()}`); // 乗客3

これらの演習問題を解くことで、スタックとキューの基本的な使い方を実践し、理解を深めることができます。次のセクションでは、本記事の内容をまとめます。

まとめ

本記事では、JavaScriptにおけるスタックとキューの基本概念とそれぞれの実装方法について詳しく解説しました。スタックは後入れ先出し（LIFO）を特徴とし、関数呼び出しの管理やブラウザの履歴機能などで使用されます。一方、キューは先入れ先出し（FIFO）を特徴とし、プリンターのジョブ管理やタスクスケジューリングなどで使用されます。

スタックの実装では、配列のpushとpopメソッドを利用し、キューの実装ではpushとshiftメソッドを利用しました。また、それぞれのデータ構造を利用した具体的な応用例として、ブラウザの履歴管理とプリンターのジョブ管理を紹介しました。さらに、読者が理解を深めるための演習問題も提供しました。

スタックとキューの理解は、効率的なアルゴリズムの設計や問題解決に役立ちます。これらの基本的なデータ構造をマスターすることで、より高度なプログラミングスキルを身につけることができるでしょう。

JavaScript
プログラミング スタック キュー JavaScript

コメント

コメントする

目次