Javascript スタック

概要: このチュートリアルでは、JavaScript のスタックデータ構造について紹介し、配列をスタックとして使用する方法を説明します。

スタックデータ構造の紹介

スタックは、要素のリストを保持するデータ構造です。スタックは LIFO 原則、つまり後入れ先出しに基づいて動作します。これは、最後に追加された要素が最初に削除される要素であることを意味します。

スタックには、スタックの先頭でのみ発生する 2 つの主要な操作があります。プッシュとポップです。プッシュ操作はスタックの先頭に要素を配置し、ポップ操作はスタックの先頭から要素を削除します。

JavaScript Stack: A Stack of books analogy

スタックという名前は、DVD ディスクや書籍など、物理的なアイテムを互いの上に積み重ねた状態との類似性に由来しています。

スタックには多くのアプリケーションがあります。たとえば、最も単純な例は単語を反転することです。これを行うには、単語を文字ごとにスタックにプッシュし、スタックから文字をポップします。

スタックの他のアプリケーションは、テキストエディタの「元に戻す」メカニズム、構文解析、関数呼び出し、および式変換（中置記法から後置記法、中置記法から前置記法、後置記法から中置記法、および前置記法から中置記法）です。

JavaScript の配列型は、配列をスタックとして使用できるようにする `push()` および `pop()` メソッドを提供します。

push() メソッド

`push()` メソッドを使用すると、配列の末尾に 1 つ以上の要素を追加できます。 `push()` メソッドは、配列内の要素数を指定する `length` プロパティの値を返します。

配列をスタックと見なすと、`push()` メソッドはスタックの先頭に 1 つ以上の要素を追加します。次の例では、`stack` という名前の空の配列を作成し、`stack` 配列の末尾に 5 つの数値を 1 つずつ追加します。これは、各数値をスタックの先頭にプッシュするようなものです。

let stack = [];

stack.push(1);
console.log(stack); // [1]

stack.push(2);
console.log(stack); // [1,2]

stack.push(3);
console.log(stack); // [1,2,3]

stack.push(4);
console.log(stack); // [1,2,3,4]

stack.push(5);
console.log(stack); // [1,2,3,4,5]Code language: JavaScript (javascript)

次の図は、上記のスクリプトの各手順を示しています。

最初は、スタックは空です。毎回、`push()` メソッドを呼び出してスタックに数値を追加します。5 回呼び出した後、スタックには 5 つの要素があります。

`push()` メソッドでは、一度に複数のアイテムを配列の末尾に追加することもできます。

pop() メソッド

`pop()` メソッドは、配列の末尾にある要素を削除し、その要素を呼び出し元に返します。配列が空の場合、`pop()` メソッドは undefined を返します。

次の例は、`pop()` メソッドを使用してスタックの先頭から要素をポップする方法を示しています。

console.log(stack.pop()); //  5
console.log(stack); // [1,2,3,4];

console.log(stack.pop()); //  4
console.log(stack); // [1,2,3];

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

console.log(stack.pop()); //  2
console.log(stack); // [1];

console.log(stack.pop()); //  1
console.log(stack); // []; -> empty

console.log(stack.pop()); //  undefinedCode language: JavaScript (javascript)

下の図は、スクリプトの各手順を示しています。

最初は、スタックには 5 つの要素があります。 `pop()` メソッドは、配列の末尾、つまりスタックの先頭にある要素を一度に 1 つずつ削除します。5 回の操作の後、スタックは空になります。

JavaScript スタックを使用して文字列を反転する

次の例は、スタックを使用して文字列を反転する方法を示しています。

function reverse(str) {
    let stack = [];
    // push letter into stack
    for (let i = 0; i < str.length; i++) {
        stack.push(str[i]);
    }
    // pop letter from the stack
    let reverseStr = '';
    while (stack.length > 0) {
        reverseStr += stack.pop();
    }
    return reverseStr;
}
console.log(reverse('JavaScript Stack')); //kcatS tpircSavaJCode language: JavaScript (javascript)

スクリプトの動作方法。

`reverse()` 関数は文字列引数を受け取り、次のロジックで反転したバージョンを返します

まず、`str` をループして各文字を `stack` 配列にプッシュします。
次に、スタックから各文字をポップして、反転した文字列を構築します。

このチュートリアルでは、プッシュとポップの 2 つの主要な操作を持つ JavaScript スタックデータ構造として配列を使用する方法を説明しました。

このチュートリアルは役に立ちましたか？