JavaScriptで学ぶデータ構造：スタックの基本と実践的な実装📚

はじめに (対象読者・この記事でわかること)

この記事は、JavaScriptの基本的な構文は理解しているものの、データ構造の概念にまだ馴染みのないプログラミング初学者の方、またはスタックというデータ構造についてJavaScriptでどのように表現し活用できるかを知りたい方を対象としています。

この記事を読むことで、データ構造の一つである「スタック」の基本的な概念、後入れ先出し（LIFO）の原則、そしてJavaScriptの配列やクラスを活用した具体的なスタックの実装方法を深く理解することができます。さらに、スタックがどのような場面で役立つのか、実際のプログラミングでの応用例についても学ぶことができるため、あなたのコード設計の幅が広がる一助となるでしょう。データ構造を学ぶ第一歩として、ぜひ読み進めてみてください。

前提知識

この記事を読み進める上で、以下の知識があるとスムーズです。 - JavaScriptの基本的な構文（変数、関数、配列、オブジェクトなど） - クラスの基本的な概念（ES6以降）

スタックとは？後入れ先出し（LIFO）の原則を理解する

スタック（Stack）は、コンピューターサイエンスにおける基本的なデータ構造の一つで、「後入れ先出し（Last In, First Out）」、略してLIFOの原則に基づいています。これは、データが追加された順番とは逆の順番で取り出されることを意味します。日常生活の例で考えると、積み重ねられたお皿の山が最もわかりやすいでしょう。一番上に置いたお皿が最初に取り出され、一番下のお皿は最後に取り出されます。

スタックには主に以下の操作があります。

• Push (プッシュ): スタックの最上部（Top）に新しい要素を追加します。
• Pop (ポップ): スタックの最上部から要素を取り除きます。取り除かれた要素が返されます。スタックが空の場合にPopを試みると、エラーになるか、特別な値を返します。
• Peek (ピーク) / Top (トップ): スタックの最上部にある要素を確認しますが、取り除きません。
• isEmpty (イズエンプティ): スタックが空かどうかを判定します。
• Size (サイズ): スタックに含まれる要素の数を返します。

スタックは、関数の呼び出し管理（コールスタック）、Webブラウザの「戻る」ボタンの履歴、プログラムのUndo/Redo機能、深さ優先探索（DFS）アルゴリズムの実装など、多岐にわたる場面で利用されています。LIFOの原則を理解することが、スタックの活用方法を考える上で非常に重要です。

JavaScriptでスタックを実装する：配列とクラスを用いた具体的な方法

ここからは、JavaScriptで実際にスタックを実装する方法を、2つのアプローチで見ていきましょう。

配列を使った簡易的なスタック実装

JavaScriptの配列は、push() メソッドと pop() メソッドを持っているため、LIFOの原則を持つスタックを簡単に表現できます。

Javascript

/**
 * 配列を使用した簡易スタックの実装例
 */
class ArrayStack {
    constructor() {
        this.items = []; // 内部的にJavaScriptの配列を使用
    }

    /**
     * 要素をスタックの最上部に追加します。
     * @param {*} element - 追加する要素
     */
    push(element) {
        this.items.push(element);
        console.log(`Push: ${element}. 現在のスタック: [${this.items.join(', ')}]`);
    }

    /**
     * スタックの最上部から要素を取り除き、返します。
     * スタックが空の場合はnullを返します。
     * @returns {*} 取り除かれた要素、またはnull
     */
    pop() {
        if (this.isEmpty()) {
            console.warn("Pop: スタックが空です。");
            return null;
        }
        const popped = this.items.pop();
        console.log(`Pop: ${popped}. 現在のスタック: [${this.items.join(', ')}]`);
        return popped;
    }

    /**
     * スタックの最上部の要素を返しますが、取り除きません。
     * スタックが空の場合はnullを返します。
     * @returns {*} 最上部の要素、またはnull
     */
    peek() {
        if (this.isEmpty()) {
            console.warn("Peek: スタックが空です。");
            return null;
        }
        const peeked = this.items[this.items.length - 1];
        console.log(`Peek: ${peeked}.`);
        return peeked;
    }

    /**
     * スタックが空かどうかを判定します。
     * @returns {boolean} スタックが空ならtrue、そうでなければfalse
     */
    isEmpty() {
        return this.items.length === 0;
    }

    /**
     * スタックに含まれる要素の数を返します。
     * @returns {number} 要素の数
     */
    size() {
        const currentSize = this.items.length;
        console.log(`Size: ${currentSize}.`);
        return currentSize;
    }

    /**
     * スタックのすべての要素をクリアします。
     */
    clear() {
        this.items = [];
        console.log("Clear: スタックがクリアされました。");
    }

    /**
     * スタックの内容を文字列で表現します。
     * @returns {string} スタックの文字列表現
     */
    toString() {
        return this.items.toString();
    }
}

// 使用例
console.log("\n--- 配列を使ったスタックの使用例 ---");
const arrayStack = new ArrayStack();
console.log(`スタックは空ですか？ ${arrayStack.isEmpty()}`); // true

arrayStack.push(10);
arrayStack.push(20);
arrayStack.push(30);

arrayStack.peek(); // 30
arrayStack.size(); // 3

arrayStack.pop(); // 30
arrayStack.pop(); // 20

console.log(`スタックは空ですか？ ${arrayStack.isEmpty()}`); // false
arrayStack.pop(); // 10
arrayStack.pop(); // スタックが空です。

arrayStack.peek(); // スタックが空です。
console.log(`スタックは空ですか？ ${arrayStack.isEmpty()}`); // true

この配列を用いた方法は非常に直感的で、簡単なスクリプトであれば十分な機能を果たします。しかし、items プロパティが外部から直接アクセス可能であるため、誤って items.shift() などと呼び出してしまい、スタックのLIFO原則が崩れる可能性があります。より堅牢で抽象度の高い実装を目指す場合は、クラスによるカプセル化が有効です。

クラスを使った本格的なスタック実装（プライベートプロパティも考慮）

JavaScriptのクラス構文と、ES2022から導入されたプライベートクラス機能（#プレフィックス）を使用することで、内部的なデータ構造を外部から隠蔽し、スタックの操作をより安全にカプセル化できます。

Javascript

/**
 * クラスを使用したより堅牢なスタックの実装例
 */
class Stack {
    #items; // プライベートプロパティとして内部配列を定義

    constructor() {
        this.#items = []; // 外部から直接アクセスできないようにする
    }

    /**
     * 要素をスタックの最上部に追加します。
     * @param {*} element - 追加する要素
     */
    push(element) {
        this.#items.push(element);
        console.log(`Push: ${element}. 現在のスタック: [${this.#items.join(', ')}]`);
    }

    /**
     * スタックの最上部から要素を取り除き、返します。
     * スタックが空の場合はnullを返します。
     * @returns {*} 取り除かれた要素、またはnull
     */
    pop() {
        if (this.isEmpty()) {
            console.warn("Pop: スタックが空です。");
            return null;
        }
        const popped = this.#items.pop();
        console.log(`Pop: ${popped}. 現在のスタック: [${this.#items.join(', ')}]`);
        return popped;
    }

    /**
     * スタックの最上部の要素を返しますが、取り除きません。
     * スタックが空の場合はnullを返します。
     * @returns {*} 最上部の要素、またはnull
     */
    peek() {
        if (this.isEmpty()) {
            console.warn("Peek: スタックが空です。");
            return null;
        }
        const peeked = this.#items[this.#items.length - 1];
        console.log(`Peek: ${peeked}.`);
        return peeked;
    }

    /**
     * スタックが空かどうかを判定します。
     * @returns {boolean} スタックが空ならtrue、そうでなければfalse
     */
    isEmpty() {
        return this.#items.length === 0;
    }

    /**
     * スタックに含まれる要素の数を返します。
     * @returns {number} 要素の数
     */
    size() {
        const currentSize = this.#items.length;
        console.log(`Size: ${currentSize}.`);
        return currentSize;
    }

    /**
     * スタックのすべての要素をクリアします。
     */
    clear() {
        this.#items = [];
        console.log("Clear: スタックがクリアされました。");
    }

    /**
     * スタックの内容を文字列で表現します。
     * @returns {string} スタックの文字列表現
     */
    toString() {
        return this.#items.toString();
    }
}

// 使用例
console.log("\n--- クラスを使ったスタックの使用例 ---");
const myStack = new Stack();
console.log(`スタックは空ですか？ ${myStack.isEmpty()}`); // true

myStack.push("A");
myStack.push("B");
myStack.push("C");

myStack.peek(); // C
myStack.size(); // 3

myStack.pop(); // C
myStack.pop(); // B

console.log(`スタックは空ですか？ ${myStack.isEmpty()}`); // false
myStack.pop(); // A
myStack.pop(); // スタックが空です。

myStack.peek(); // スタックが空です。
console.log(`スタックは空ですか？ ${myStack.isEmpty()}`); // true

// これはエラーになります（プライベートプロパティへの直接アクセスは不可）
// console.log(myStack.#items);

このクラスを使った実装では、#items をプライベートプロパティとして宣言することで、スタックの内部実装が外部から隠蔽され、push や pop といった定義されたメソッドを介してのみデータが操作されるようになります。これにより、コードの堅牢性、保守性、再利用性が向上します。

スタックの応用例

スタックは、非常に多くの場面で活用されています。

1. 関数の呼び出し管理（コールスタック）: JavaScriptエンジンを含むほとんどのプログラミング言語では、関数が呼び出されるたびにその情報（引数、ローカル変数など）がコールスタックに積まれ、関数が実行を終えるとスタックから取り除かれます。これにより、関数の実行順序や戻り値の管理が効率的に行われます。
2. ブラウザの「戻る」「進む」機能: Webブラウザの閲覧履歴は、内部的に2つのスタック（「戻る」履歴用と「進む」履歴用）を使って管理されることがあります。「戻る」ボタンを押すと、現在のページが「進む」スタックにプッシュされ、「戻る」スタックから前のページがポップされて表示されます。
3. 括弧の整合性チェック: 数式やコード内で括弧 (), [], {} が正しく対応しているかを確認するためにスタックが使われます。開き括弧が現れたらスタックにプッシュし、閉じ括弧が現れたらスタックからポップして対応する開き括弧と一致するか確認します。
4. 電卓の逆ポーランド記法（RPN）計算: 演算子が後から来る記法（例: 3 4 + -> 7）を計算する際、数値はスタックにプッシュされ、演算子が現れるとスタックから必要な数の数値がポップされて計算されます。

これらの例からわかるように、スタックは単なるデータ格納庫ではなく、特定のロジックや処理フローを効率的に実現するための強力なツールなのです。

ハマった点やエラー解決

スタックの実装や使用でよくあるハマりどころは、主に以下の2点です。

1. スタックが空なのに Pop や Peek を実行してしまう: スタックが空の状態で pop() や peek() を呼び出すと、JavaScriptの配列の pop() は undefined を返しますが、これはデータ構造として「スタックが空である」という状態を明確に示しません。本記事の実装例では、このケースで null を返し、警告メッセージを出すことでハンドリングしています。
2. LIFO原則を崩してしまう操作: 特に配列を使ってスタックを実装する場合、items.shift()（配列の先頭を取り除く）や items.unshift()（配列の先頭に追加する）といったメソッドを誤って使ってしまうと、スタックのLIFO原則が崩れてしまいます。スタックの操作は push() と pop() (またはそれに相当する機能) に限定すべきです。

解決策

• pop() や peek() を呼び出す前に、必ず isEmpty() メソッドでスタックが空でないかを確認する習慣をつけましょう。これにより、意図しないエラーや undefined の返却を防ぐことができます。
• スタックを実装する際は、そのデータ構造の特性（LIFO）を意識し、内部的な配列の操作は push() と pop() のみに限定する、あるいは本記事のクラス実装のように、外部から直接内部データに触れさせない設計を心がけましょう。これにより、コードの意図が明確になり、バグの発生を未然に防ぐことができます。

まとめ

本記事では、JavaScriptにおけるデータ構造「スタック」の基本概念、後入れ先出し（LIFO）の原則、そして配列とクラスを用いた具体的な実装方法 を解説しました。

• スタックはLIFO（後入れ先出し）の原則に基づくデータ構造 であり、push、pop、peek、isEmpty、sizeといった主要な操作を持ちます。
• JavaScriptでは、配列の push() と pop() メソッドを活用することで簡易的にスタックを表現できます。これは手軽な反面、内部構造が外部に公開されやすいという特徴があります。
• クラスとプライベートプロパティを用いたスタックの実装は、カプセル化により堅牢性と再利用性が向上します。これにより、スタックのLIFO原則がより厳密に保たれます。
• スタックは関数のコールスタック、ブラウザの履歴、括弧の整合性チェックなど、多岐にわたる場面で応用されます。

この記事を通して、データ構造の基礎であるスタックが、単なる概念ではなく、実際のプログラミングにおいてどのように設計され、どのように役立つのかを理解していただけたことと思います。データ構造を学ぶことは、より効率的で堅牢なプログラムを書くための重要なステップです。 今後は、スタックと対照的な「キュー（Queue）」や、より複雑なデータ構造である「連結リスト」「木構造」などについても記事にする予定ですので、ぜひ続けて学習してみてください。

参考資料

• MDN Web Docs: Array
• MDN Web Docs: Classes
• GeeksforGeeks: Stack Data Structure (英語)
• データ構造とアルゴリズム（書籍など） (一般的なデータ構造の書籍を参照)