データ構造とアルゴリズム-スタック編(js実装)

詳細
スタックの特徴:
スタック内の要素はリストの一端からしかアクセスできません.この一端はスタックトップと呼ばれます.

先入後出.スタックの上部にない要素はアクセスできません.スタックの下部にある要素を得るには、上の要素

を先に取り除く必要があります.
現実のスタック:
カフェ内の皿の積み重ねは、現実世界でよく見られるスタックの例です.一番上からお皿を取るしかなく、お皿を洗った後も、積み重ねるしかありません
この皿の一番上にあります.
 
スタックの主なメソッドとプロパティ:

がスタックに入ります.pushメソッド;

はスタックを出ます.Popメソッド;

はスタックトップ要素にアクセスします.peekメソッド;

すべてのスタック内の要素をクリアします.clearメソッド;

スタックトップ位置を記録します.topプロパティ;

スタック内に要素が存在するかどうかを判断します.lengthメソッド;

スタックの実装:
stackコンストラクション関数の定義から開始

function Stack() {
　this.dataStore = [];//      
　this.top = 0;
}

スタックに対する様々な操作

Stack.prototype={
   push:function push(element) {
          this.dataStore[this.top++] = element;//        top+1
        },
   peek:function peek() {
          return this.dataStore[this.top-1];//      
        },
   pop:function pop() {
          return this.dataStore[--this.top];//        top-1
       },
   clear:function clear() {
           this.top = 0;// top 0
         },
   length:function length() {
            return this.top;//         
          }
}

テスト:

var lk=new Stack();
lk.push("likeke");
lk.push("zhangsan");
lk.push("wangwu");
lk.peek();//"wangwu"
lk.length();3
lk.pop();//"wangwu"
lk.peek();//"zhangsan"
lk.clear();
lk.peek();//undefind
lk.length();0

スタックの使用:
　1.10進数を2~9進数に変換

function mulBase(num, base) {
　var s = new Stack();
　do {
　　　s.push(num % base);
　　　num = Math.floor(num /= base);
　} while (num > 0);
　var converted = "";
　while (s.length() > 0) {
　　　converted += s.pop();
　}
　return converted;
}
mulBase(12,2);//"1100"
mulBase(19,5);//"34"
mulBase(19,3);//"201"

    2.指定された文字列が返信であるかどうかを判断する

function isPalindrome(word) {
　var s = new Stack();
　for (var i = 0; i < word.length; ++i) {
　　　s.push(word[i]);
　}
　var rword = "";
　while (s.length() > 0) {
　　　rword += s.pop();
　}
　if (word == rword) {
　　　return true;
　}
　else {
　　　return false;
　}
}
isPalindrome("likeke");//false
isPalindrome("lkijikl");//true

 　3.任意の数値の階乗を計算する

//              
function factorial(n) {
　if (n === 0) {
　　　return 1;
　}
　else {
　　　return n * factorial(n-1);
　}
}

//    Stack  ，           
function fact(n) {
　var s = new Stack();
　while (n > 1) {
　　　s.push(n--);
　}
　var product = 1;
　while (s.length() > 0) {
　　　product *= s.pop();
　}
　　　return product;
　}
factorial(5); // 120
fact(5); //  120

もちろん,以上の進数変換や返信文を判断する機能関数を実現したいだけであれば,より簡便な方法で実現できるが,ここではこのデータ構造の特徴を説明するためにこれらの例を用いただけである.