看完《学习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
用ES6语法创建的类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<items.length; i++){
if (queueElement.priority < items[i].priority){
items.splice(i,0,queueElement);
added = true;
break;
}
}
if (!added){
items.push(queueElement);
}
};
this.print = function(){
for (let i=0; i<items.length; i++){
console.log(`${items[i].element} -
${items[i].priority}`);
}
};
//其他方法和默认的Queue实现相同
}
let priorityQueue = new PriorityQueue()
//测试代码
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print(); // 结果Jack1 , Camila 1, John 2
