javascriptデータ構造とアルゴリズム読書ノート>第四章スタック

1.スタックの操作
スタックは特殊なリストであり、スタック中の要素はリストの端だけでアクセスできます.すなわちスタックトップです.積み重ねられた皿のように、最後に上に置くしかないです.最初に訪問できます.
私たちが言っている後入先出ということです.
スタックには主にスタックpush、スタックpop、スタックトップ元素peek、三つの方法があります.
2.スタックの実現
基本的な構造は以下の通りです. 

function Stack(){

    this.dataStore = [];

    this.top = 0;

    this.push = push;

    this.pop = pop;

    this.peek = peek;
　　 this.length = length;
    this.clear = clear;
}

 
スタックの操作について:

function push(obj){

     this.dataStore[this.top++] = obj;

}

スタック:

function pop(){
　　if(this.top!=0){

       return this.dataStore[--this.top];
   }else{
       return undefined;
   }

}

スタックトップ要素を取得:

function peek(){

    return this.dataStore[this.top-1];

}

取得長:

function length(){

    return this.top;

}

クリア:

function clear(){

     this.top = 0;

}

3スタッククラスを使う
 　  a)デジタル間の相互変換
スタックを利用して10進から2～9進への操作ができます.
方法は以下の通りです.一つの十進数a、進数b
1>a%bをスタックに押し込む
2>a/bをa/bに置き換える
3>aが0より大きい場合は、1>に繰り返して当たります.
0より小さい場合は、ジャンプ
4>スタックの要素を一度にイジェクトして、新しい文字を構成します.
例を挙げます.
10を2進に変換:
10%2=0 ——倉庫に入る——0
5%2=1——チェックイン——1,0
2%2=0——チェックイン——0,1,0
1%2=1——スタックに入る——1,0,1,0
最後の出荷順は1010です.
コードは以下の通りです.

function mulNum(num, base){

    var stack = new Stack();   

    //       

    while(num>0){

        //       

        stack.push(num%base);

        //       （     ）

        num = Math.floor(num/base);

    }   

    var rs = '';

    for(stack.length>0){

         rs += stack.pop();

   }

   return rs;

}

   b)回文
　　

function isPalindromic(str){

    var stack = new Stack();

    for(var i=0;i<str.length;i++){

         stack.push(str[i]);

    }

    var revStr;

    while(stack.length()>0){

        revStr += stack.pop();   

    }

    if(revStr === str){

        return true;

    }else{

        return false;

    }

}

 
スタンクで反転操作をしました.
 
c)再帰的デモ
第一章では再帰的に階乗を求める方法について述べましたが、ここではstackを使って階乗を求め、再帰的に模擬します.
 

function(num){

    var rs = 1;

    var stack = new Stack();

    while(num>1){

       stack.push(num--);

    }

    while(stack.length>0){

       rs *= stack.pop();

    }

    return rs;

}