スタック

JSが資料構造を実現する前の接続リストに続いて2回目である.
1.スタックとは
スタックはデータを置く、減らすことができるデータ構造であり、データを先に置く、データを後に置くという概念である.

FILOとも呼ばれ、First In Last Outという意味です.
ブラウザで[戻る](Back)キーで前のページに移動するのもスタックアクセスと言えます.
2.スタックの基本演算
スタックには基本的にサポートされている演算と機能があり、代表的な演算を見てみましょう.
2.1 pushpush演算はその名の通り押し込むという意味です.上から下へ積み重ねるときはpush演算を使用します.
2.2 pop
次の演算はpopであり、pushとは異なり、データは1つずつ取り出される.
2.3 getTop
デフォルトでは、スタックは下から上への構造であるため、クラスとして実装されると、一番上のデータを指すTopというメンバー変数があります.
その値の演算を知る.
2.4 getSize
スタック内のデータの合計数を表します.
3.実施
JSでスタックを実現する方法はいろいろあります.

JSで提供されるデフォルトのシナリオ

を使用

接続リストを使用して

を実装する方法
共に2種類を実現する.
3.1アレイによる実装

const stackObj = {
  stack: [],

  push(value) {
    this.stack.push(value);
  },
  pop() {
    this.stack.pop();
  },
  top() {
    return this.stack[this.stack.length - 1];
  },
  size() {
    return this.stack.length;
  },
};

stackObj.push(1);
stackObj.push(2);
stackObj.push(3);
stackObj.push(4);
stackObj.push(5);
console.log(stackObj.stack); // [1,2,3,4,5]
console.log(stackObj.top()); // 5
stackObj.pop();
console.log(stackObj.stack); // [1,2,3,4]

こんなに簡単に実現できます.
3.2接続リストによる実施
まず、接続リストで実装されているように、ノードクラスを宣言します.ノードは一般に、メンバー変数としてnextおよびvalueである.

class Node {
	constructor(value) {
      this.value = value;
      this.next = null;
    }
}

接続リストでスタックを実現するのは触れられないかもしれませんが、接続リストの実現を簡単にイメージ図のように立てば、より感じやすくなります.

まず、Stackクラスは、スタックの最上位値topと、データ個数を表すsizeとを表すメンバー変数である.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
}

次に示すのはpushです.
まず,新しく生成されたvalueをパラメータとしてノードを生成し,ノードのnextはtopを指す.次に、topをリッチタイムノードに置き換えます.

push(newValue) {
    const node = new Node(newValue);
    node.next = this.top;
    this.top = node;
    this.size += 1;
}

次はpopです.popの方法は、一番上のtopを取り出し、topを交換し、size 1を減らすことで完了します.

pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.size -= 1;
    return value;
}

getTopとgetSizeは、既存の値を返すだけで完了します.

getTop() {
  return this.top;
}

getSize() {
  return this.size; 
}

最終コード
最終コードには、traverseメソッドのループ値が追加されました.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  //push
  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.size += 1;
  }

  pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.size -= 1;
    return value;
  }

  getTop() {
    return this.top;
  }

  getSize() {
    return this.size;
  }

  traverse() {
    let currNode = this.top;
    while (currNode) {
      console.log(currNode.value);
      currNode = currNode.next;
    }
  }
}