データ構造-スタックとキューのまとめ
2960 ワード
「JavaScriptデータ構造とアルゴリズムを勉強します」(第2版)の第3章、4章の内容を見終わって、スタックと行列のこの2種類のデータ構造の内容に関わって、以下は簡単なメモの整理と抜粋です.
1、スタックデータ構造
1.1スタックの定義スタックは後進先出(LIFO、Last In First Out、後進先出)の順序付きセットである.
1.2スタックを作成するjavascriptの構造関数(クラス)は、スタックを表すコードを作成することができます.
キューの作成はスタックと似ていますが、原則は異なります.2.1キューの定義キューは、
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