[データ構造]スタックとキューJavaScript

13356 ワード
データ構造 js テキストリンク

スタックとキュー


効率的なプログラミングを行うためには,資料構造概念が非常に必要であると考えられる.
スタックとキューはJavaScriptでよく使われる概念です.
通常、Arrayメソッドpush、pop、unshiftなどが使用され、これはスタックおよびキューにおいても適用される.
よく理解してから行きましょう.

スタック


スタッキング
スタックは本のようにデータを蓄積する構造です.
プログラミングの観点から,データ(資料)の入出力は一方向の構造である.

  • 最上位:現在のデータ基準の最上位
    ex)上図判断によるx->1->2->1
    info)すべてのデータ演算はTopで完了する.

  • Push:データを追加する演算.
    ex)上部で積み重ね続ける構造(1->2->3->...)
    info)JS内蔵メソッドプッシュなどの機能.

  • Pop:データを削除する演算.
    ex)topを基準としてデータを1つずつ削除する.(3->2->1->x)
    info)JS内蔵メソッドPopのような機能です.

    • JavaScriptでの実装

    class Stack {
  constructor(){
    this.storage = {};
    this.top = 0;
  }
  
  size() {
    return this.top
  }
  
  push(element){
    this.top ++;
    return (this.storage[this.top] = element);
  }
  
  pop(){
    if(this.top != 0){
      let data = this.storage[this.top];
      delete this.storage[this.top];
      this.top--;
      return data;
    }
  }
}

var test= new Stack
test.push('가')//storage: { '1': '가'}
test.push('나')//storage: { '1': '가', '2': '나' }
test//storage: { '1': '가', '2': '나' },
test.pop()//storage: { '1': '가'}
test.size()//1
    後入線出口グループ.
    後押しの「私」は先にポップアップする仕組みです.

    キュー


    Queue=並びます.
    キューは、データの入力と出力を1つの場所で管理するスタックとは異なります.
    In&Outをそれぞれ実行します.
  • Rear:データ入力部
  • Front:データ抽出部
  • Enqueue:実行データ入力
  • Dequeue:デート抽出の実行

    • JavaScriptでの実装

    class Queue {
  constructor(){
    this.storage ={};
    this.front = 0;
    this.rear = 0;
  }
  
  size(){
    return this.front;
  }
  
  enqueue(element){
    if( this.front === 0){
      this.storage[this.front] = element;
      this.front++;
      return
    }
    this.front++;
    let values = Object.values(this.storage)
    values.unshift(element);
    this.storage = {};
    for(let z = values.length -1; z>=0; z--){
      this.storage[z] = values[z]
    }
  }
  
  dequeue() {
    if(this.front !== 0){
      let data = this.storage[this.front - 1];
      delete this.storage[this.front -1];
      this.front --;
      return data;
    }
  }
}

var test2 = new Queue
test2.enqueue('가')//storage: { '0': '가'}
test2
test2.enqueue('나')//storage: { '0': '나', '1': '가' }
test2
test2.dequeue()//storage: { '0': '나'}
test2
    最初に入力したデータ「すでに」は、削除操作時に消去されます.
    (注意)DJANGOプロジェクト3(pipenvのインストールと使用)
    コーディングテスト練習-失敗率