JavaScriptデータ構造——スタック

スタック スタックは後入先出(LIFO、全称Last In First Out)に従うデータ構造であり、演算制限された線形表であり、その制限は表の一端のみで動作することを許可し、この一端はスタックトップと呼ばれる.
スタックは後入先の特徴を持っているので、スタックの一番上にない要素はアクセスできません.もしスタックの底にある要素にアクセスするなら、先に上の要素を除去しなければなりません.
スタックの実現 JavaScriptでは、配列席格納データの下のデータ構造を採用している.
スタック構造関数を定義するfunction Stack(){    this.items = [];    this.top=0;// ， }スタックには以下の方法があります.
push()進スタックpop()キャンセルサイズempty()はスタックが空かどうか判断します.peek()はスタックトップ要素に戻る.
クリーン倉庫プッシュする スタックに新しい要素を押し込む時、要素は現在のスタックトップポインタに対応する位置にあり、押し込んだ後、スタックトップポインタは次の位置を指すべきです.function push(item){    this.items[this.top++] = item;}ポップ popはpush方法とは逆で、スタックトップ要素に戻り、topの値は1を減算します.function pop(){    if(this.top===0) return;    var item = this.items[this.top-1]    this.items.length = --this.top;    return item;}size sizeメソッドは、スタック内の要素の個数を返します.function size(){    return this.top;}empty スタックが空かどうかチェックして、空の場合はtrueに戻ります.そうでなければfalseに戻ります.function empty(){    return this.top === 0;}peek スタックの一番上の要素を返しますfunction peek(){    return this.items[this.top-1];}clear クリアスタック内のすべての要素function clear(){    this.items = [];    this.top = 0;}スタックの追加方法 上記の方法をプロトタイプでスタックコンストラクタに追加します.Stack.prototype = {    constructor:Stack,    push:push,    pop:pop,    size:size,    empty:empty,    peek:peek,    clear:clear,}スタックの実用的な応用 以下は再帰関数で、数字の階乗を計算します.function factorial(n) {    if (n === 0) {        return 1;    } else {        return n * factorial(n - 1);    }}この関数を使って5の階乗を計算します.factorial(5) // 120スタックを使ってアナログ計算をするなら5!の過程で、5から1を順番にスタックに押し込んで、数字を順番に掛けて、計算結果を得ることができます.function factorial2(n){    var s = new Stack(),        result = 1;    while(n>1){        s.push(n--)    }    while(s.size()>0){        result*= s.pop()    }    return result;}この関数を使って5の階乗を計算します.factorial(5) // 120