JavaScript でスタックを実装する方法

この記事では、JavaScript を使用してスタックを実装する方法を主に紹介します。必要な友人はそれを参照できるようにします。

スタック? 後入れ先出し (LIFO) 原則に従った順序付けされたコレクション。
新しく追加された要素、または削除される要素はスタックの最後に格納されます。これをスタックの最上位と呼び、もう一方の端をスタックの最下位と呼びます。
スタックでは、新しい要素はスタックの一番上に近く、古い要素はスタックの一番下に近くなります
実際の例

また、世の中のスタックの例をたくさん見つけることができます。たとえば、キッチンに積み重ねられたプレートのうち、入力ボックスの内容が削除されるときは常に一番上に積み重ねられたものが最初に使用され、マガジン内の弾は常に最初に発射されます。 ....

スタックを手動で実装します

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

function Stack () { }

スタックに要素を保存するにはデータ構造を選択する必要があります。配列を選択できます

function Stack(){
    var items = [];     //用来保存栈里的元素
}

次に、スタックメソッド

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素，同时返回被移除的元素
peek();             //返回栈顶的元素，不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true，否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

にいくつかを追加します。実装する必要がある最初のメソッドは push です。新しい要素をスタックに追加するために使用されますが、非常に重要なことが 1 つあります。このメソッドはスタックの最後であるスタックの先頭にのみ追加します。したがって、次のように書くことができます:

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

配列のpushメソッドを使用して、スタックの一番上の最後に新しい要素を追加できます。

push。用来往栈里添加新元素，有一点很重要：该方法只添加到栈顶，也就是栈的末尾。所以，可以这样写：

this.pop = function () {
    return items.pop();
}

利用数组的push方法，就可以实现在栈顶末尾添加新的元素了。

接着，来实现pop方法，用来实现移除栈里的元素。栈遵从LIFO（后进先出）原则。移出去的是最后添加进去的元素。因此，可以使用数组的pop方法。

this.peek = function () {
    return items[items.length-1];
}

这样一来，这个栈自然就遵从了LIFO原则

现在，再来为这个栈添额外的辅助方法。

如果想知道栈里最后添加的元素是什么，可以用peek方法。这个方法将返回栈顶的元素

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

因为类内部是用数组保存元素的，所以这里访问数组最后一个元素用length-1

下一个要实现的方法是isEmpty,如果栈为空的话，就返回true，否则返回false：

this.size = function () {
    return items.length;
}

使用isEmpty方法，就能简单地判断栈内部是否为空。

类似于数组地length属性，我们也可以实现栈地length。

this.clear = function () {
    items = [];
}

因为栈地内部使用数组保存元素，所以数组地length就是栈的长度。

实现clear方法，clear方法用来清空栈中所有的元素。最简单的实现方法是：

this.print = function () {
    console.log(items.toString());
}

其实多次调用pop方法也可以，但是没有这个方法来的简单快捷。

最后，为了检查栈里的内容，还需要实现一个辅助方法：print次に、pop メソッドを実装して、スタックから要素を削除します。スタックは LIFO (後入れ先出し) の原則に従います。削除されるのは、最後に追加された要素です。したがって、配列の Pop メソッドを使用できます。

function Stack(){

    var items = [];     //用来保存栈里的元素

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

    this.pop = function () {
        return items.pop();
    }

    this.peek = function () {
        return items[items.length-1];
    }

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

    this.size = function () {
        return items.length;
    }

    this.clear = function () {
        items = [];
    }

    this.print = function () {
        console.log(items.toString());
    }
}

このように、このスタックは自然に LIFO 原則に従いますそれでは、このスタックに追加の補助メソッドを追加してみましょう。

スタックに追加された最後の要素を知りたい場合は、peek メソッドを使用できます。このメソッドはスタックの最上位にある要素を返します

var stack = new Stack();
console.log(stack.isEmpty());         //控制台输出true

クラスは要素の保存に配列を使用するため、配列の最後の要素にアクセスするには、length-1 を使用します

次に実装されるメソッドは isEmpty です。スタックが空の場合は true を返し、そうでない場合は false を返します。

stack.push(5);
stack.push(8);

isEmpty メソッドを使用すると、スタックが空かどうかを簡単に判断できます。

配列の長さプロパティと同様に、スタックの長さも実装できます。

console.log(stack.peek());            //控制台输出8

スタックは要素を格納するために内部で配列を使用するため、配列の長さがスタックの長さになります。

clear メソッドを実装します。clear メソッドは、スタック内のすべての要素をクリアするために使用されます。最も単純な実装方法は次のとおりです:

stack.push(11);
console.log(stack.size());            //控制台输出3

実際、pop メソッドを複数回呼び出すこともできますが、このメソッドほど単純かつ高速ではありません。

最後に、スタックの内容を確認するには、補助メソッド print を実装する必要があります。スタック内のすべての要素がコンソールに出力されます:

stack.push(15);

この時点で、

スタック

が完全に作成されました!

スタックの完全なコード

stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]

Stackクラスの使用

スタックは作成したので、テストしてみましょう

まず、Stack クラスを初期化します。次に、スタックが空かどうかを確認します

function pideBy2 (decNumber) {

    var remStack = new Stack(),
    rem,
    binaryString = '';

    while (decNumber>0) {  //{1}
        rem = Math.floor(decNumber % 2);  //{2}
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / 2);  //{4}
    }

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

次に、スタックに要素を追加します:

console.log(pideBy2(520));      //输出1000001000
console.log(pideBy2(10));       //输出1010
console.log(pideBy2(1000));     //输出1111101000

Peak メソッドを呼び出すと、スタックの一番上の要素であるため、明らかに 8 が出力されます:

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

別の要素を追加:

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

スタックにさらに 11 個追加しました。 size メソッドが呼び出された場合、スタック上に 3 つの要素 (5、8、11) があるため、出力は 3 になります。この時点で isEmpty メソッドを呼び出すと、偽の出力が表示されます (この時点ではスタックが空ではないため)。最後に、別の要素を追加します:

rrreee

次に、pop メソッドを 2 回呼び出して、スタックから 2 つの要素を削除します: 🎜rrreee🎜 この時点で、スタック全体の機能テストが完了します。 🎜🎜スタックを使用して問題を解決します🎜🎜スタックを使用して 16 進数の変換を完了します。 🎜🎜実生活では主に 10 進数を使用しますが、コンピューター内のすべての内容は 2 進数 0 と 1 で表されるため、計算科学では 2 進数が非常に重要です。大学のコンピュータ授業ではまず基数変換を教えます。バイナリを例に挙げます: 🎜🎜🎜🎜rrreee🎜 このコードでは、結果が 2 で均等に除算される条件を満たす場合 (行 {1})、現在の結果と 2 の余りを取得し、次のようにします。それをスタック上に置きます (行 {2}、{3})。次に、結果を 2 で均等に除算します (行 {4})。🎜🎜注: JavaScript には数値型がありますが、整数と浮動小数点数は区別されません。したがって、Math.floor 関数を使用して、除算演算で整数部分のみを返すようにします。 🎜🎜最後に、pop メソッドを使用してスタックからすべての要素を削除し、ポップされた要素を文字列に連結します (行 {5})。 🎜🎜テストしてみましょう: 🎜rrreee🎜 次に、10 進数を任意の基数に変換できるように、上記のアルゴリズムを簡単に変更できます。 10 進数と 2 で割り切れる数を 2 進数に変換することに加えて、次のアルゴリズムのように、他の任意の基数をパラメーターとして渡すこともできます。

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

    while (decNumber>0) {  
        rem = Math.floor(decNumber % base);
        remStack.push(rem);  //{3}
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行{6}、{7}）。

来测试一下输出结果：

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！

相关推荐：

如何利用js fetch实现ping效果

Node.js使用superagent模拟GET/POST的请求

以上がJavaScript でスタックを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。