JavaScriptデータ構造スタックの使用例

この記事の内容は JavaScript データ構造スタックの使用例についてです。必要な方は参考にしていただければ幸いです。あなた。

スタック

最初に質問を見てみましょう

Leetcode 32 最長有効括弧

与えられた文字列に ' のみが含まれる場合(' および ')' は、有効な括弧を含む最長の部分文字列の長さを見つけます。

例 1:

入力: "(()"
出力: 2
説明: 最も長い有効な括弧部分文字列は、"()"

例 2:

入力: ")()())"
出力: 4
説明: 有効な括弧部分文字列の中で最も長いものは、"()()"

この問題は動的プログラミングを使用して解決することも、簡潔で明確なスタックを使用して解決することもできます。

スタックとは何ですか?

スタックは先入れ後出し (LIFO) 順序のコレクションであり、新しく追加された要素がスタックの一番上にあり、古い要素がスタックの一番下にあります。

次の図は例です。1、2、3、4、5、6、7 が順番にスタックにプッシュされます。

スタックの作成

スタックを表すクラスを作成します:

class Stack {
    // 初始化类，创建数组 items 存放入栈元素
    constructor() {
        this.items = [];
    }
    // push 方法进行元素入栈（可同时入栈一或多个元素），无返回值
    push() {
        this.items.push(...arguments);
    }
    // pop 方法出栈一个元素，返回出栈元素
    pop() {
        return this.items.pop();
    }
    // peek 方法返回栈顶元素，不对栈本身做任何操作
    peek() {
        return this.items[this.items.length-1];
    }
    // size 方法返回栈内元素个数
    size() {
        return this.items.length;
    }
    // isEmpty 方法查看栈是否为空，返回布尔值
    isEmpty() {
        return this.items.length == 0;
    }
    // clear 方法清空栈，无返回值
    clear() {
        this.items = [];
    }
    // print 方法打印栈内元素
    print() {
        console.log(this.items.toString());
    }
}

// 测试 
let stack = new Stack();
stack.push(1,2,3,4);
stack.print(); // 1,2,3,4
stack.isEmpty(); // false
stack.size(); // 4
stack.pop(); // 4
stack.peek(); // 3
stack.clear();

Note

プライベート メンバーは JavaScript クラスで一時的に定義できないため、スタック要素を格納する配列項目はこの操作は非常に 危険です。

stack.items; // [1, 2, 3, 4]

これを回避するには、

closure と IIFE を使用します。これは非常に無力な方法です:

let Stack = (function () {
    // 使用 WeakMap 存储数组（数组存放进栈元素）
    let items = new WeakMap();
    class Stack {
        constructor() {
            items.set(this, []);
        }
        push() {
            items.get(this).push(...arguments);
        }
        // 其他方法
    }
    return Stack;
})();

let s = new Stack();
// 无法访问到 items
s.items; // undefined

WeakMap : WeakMap は Map と同様のキーと値のペアのコレクションですが、参照がない限り、WeakMap のキーは弱参照です。ガベージ コレクション メカニズムは、占有メモリをリサイクルすることは、手動削除ではなく自動削除と同等です。

スタックを使用して問題を解決する

アイデア:

1. 変数

   start有効な括弧の開始添字 を格納します。 maxLen 最大長を格納します。

2. スタックは左括弧の添字のみを格納します。

3. 右括弧が見つかったとき、その時点でスタックが空であれば、このループをスキップして

   start を更新します。スタックが空でない場合は、スタックの先頭要素をポップします。 ;

4. スタックの最上位要素がポップされた後、スタックが空の場合は、現在の添字と

   start の間の距離を計算し、 を更新します。 maxLen;

5. スタックの最上位要素がポップされた後、スタックが空でない場合は、現在の添字とその最上位に格納されている添字の間の距離を計算します。

   maxLen;

6. 最後までループします。

うわー

以上がJavaScriptデータ構造スタックの使用例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。