データ構造-スタックとキューのまとめ

2960 ワード

「JavaScriptデータ構造とアルゴリズムを勉強します」(第2版)の第3章、4章の内容を見終わって、スタックと行列のこの2種類のデータ構造の内容に関わって、以下は簡単なメモの整理と抜粋です.
1、スタックデータ構造
1.1スタックの定義スタックは後進先出(LIFO、Last In First Out、後進先出)の順序付きセットである.
1.2スタックを作成するjavascriptの構造関数(クラス)は、スタックを表すコードを作成することができます.
//ES5  
function Stack(){
  let items = [];
  //       
  this.push = function(element){
    items.push(element);
  },
  //      
  this.pop = function(){
    return items.pop();
  },
  //      
  this.peek = function(){
    return items[items.length-1];
  },
  //     
  this.size = function (){
    return items.length;
  },
  //       
  this.isEmpty = function(){
    return items.length == 0;
  },
  //     
  this.clear = function(){
    items = [];
  },
  //     
  this.print = function(){
    console.log(items.toString());
  }
}
1.3スタック1.2節の構造関数を使用してスタックを完全に作成し、次にスタックの方式を使用する.
let stack = new Stack();
console.log(stack.isEmpty())  //true,  `stack`   ,   true
console.log(stack.push(5))
console.log(stack.print())  //5
2.キューデータ構造
キューの作成はスタックと似ていますが、原則は異なります.2.1キューの定義キューは、FIFO(First In First Out、先入先出)原則に従う順序付けられたセットである.2.2キューを作成する方法は、上記のスタックを作成する方法と同様であり、唯一の違いは、dequeue方法とfont方法は、キューの原理が異なるためである.コードは以下の通りです
//ES5  

function Queue() {
  //     ,        
  let items = [];
  //       
  this.enqueue = function(e){
    items.push(e)
  }
  //       
  this.dequeue = function(){
    return items.shift()
  },
  //       
  this.front = function(){
    return items[0]
  },
  //      
  this.size = function (){
    return items.length;
  },
  //      
  this.isEmpty = function(){
    return items.length == 0;
  },
  //      
  this.print = function(){
    console.log(items.toString())
  }
}
let queue = new Queue();
console.log(queue.isEmpty())  //true

---   ---

//ES6    
let Queue2 = (function () {

  const items = new WeakMap();

  class Queue2 {
    constructor () {
      items.set(this, []);
    }
    enqueue(element) {
      let q = items.get(this);
      q.push(element);
    }
    dequeue() {
      let q = items.get(this);
      let r = q.shift();
      return r;
    }
    //    
  }
  return Queue2;
})();
2.3キューの使用
let queue = new Queue();
console.log(queue.isEmpty()); //  true
ES 6文法で作成されたクラスQueue2も使用でき、出力されたテスト結果は同じ2.4列のアプリケーションはキューベースのアプリケーションが優先キューである.
function PriorityQueue() {
  let items = [];
  function QueueElement (element, priority){ 
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function(element, priority){
    let queueElement = new QueueElement(element, priority);

    let added = false;
    for (let i=0; i