队列
队列中我们主要实现两种：
1. 常规队列
2. 优先队列（实际应用中的排队加急情况等）
常规队列的实现方法如下：
// 常规队列
function Queue () {
this.queue = [];
this.enqueue = enqueue; // 入队
this.dequeue = dequeue; // 出队
this.front = front; // 返回队首
this.back = back; // 返回队尾
this.toString = toString; // 返回队列
this.empty = empty; // 队列是否为空
this.count = count; // 显示当前队列的元素数量 function enqueue (ele) {
this.queue.push(ele)
} function dequeue () {
return this.queue.shift();
} function front () {
return this.queue[0];
} function back () {
return this.queue[this.queue.length-1]
} function toString () {
var que = ""
for (var i=0; i<this.queue.length; i++) {
que += (this.queue[i] + "\n" )
} return que;
} function empty () {
if (this.queue.length === 0) {
return true;
}else{
return false;
}
} function count () {
return this.queue.length;
}
}
常规队列的应用之，队伍匹配（需要node环境）：
// 队伍匹配example
const fs = require("fs")
var dancerList = fs.readFileSync("dancer.txt", "utf-8").split("\r\n");
var female = new Queue();
var male = new Queue();
var finalList = dancerList.map(function(item){
return {
sex: item.split(" ")[0],
name: `${item.split(" ")[1]} ${item.split(" ")[2]}`
}
})
finalList.forEach(function(item){
if(item.sex==="F"){
female.enqueue(item);
}else{
male.enqueue(item);
}
})
function dance (female, male) {
while (!female.empty() && !male.empty()) {
console.log("the next dancers are：");
console.log(`${female.dequeue().name} & ${male.dequeue().name}\n`)
}
if (!female.empty()) {
console.log(`${female.front().name} is waiting !!`)
}
if (!male.empty()) {
console.log(`${male.front().name} is waiting to dance......`)
}
}
dance(female, male);
优先队列中主要增加了权重的比对，实现方法如下：
// 优先队列
// 入队者需要有priority属性，属性值范围为1 - this.queue.length-1
function PriorQueue () {
this.queue = [];
this.enqueue = enqueue; // 入队
this.dequeue = dequeue; // 出队
this.front = front; // 返回队首
this.back = back; // 返回队尾
this.toString = toString; // 返回队列
this.empty = empty; // 队列是否为空
this.count = count; // 显示当前队列的元素数量 function enqueue (ele) {
this.queue.push(ele)
} function dequeue () {
var priorityNum;
if(this.queue[0].priority){
priorityNum = this.queue[0].priority;
}
for(var i=1; i<this.queue.length; ++i){
console.log(i);
if (this.queue[i].priority < priorityNum ) {
priorityNum = i;
}
}
return this.queue.splice(priorityNum, 1);
} function front () {
return this.queue[0];
} function back () {
return this.queue[this.queue.length-1]
} function toString () {
var que = ""
for (var i=0; i<this.queue.length; i++) {
que += (this.queue[i] + "\n" )
} return que;
} function empty () {
if (this.queue.length === 0) {
return true;
}else{
return false;
}
} function count () {
return this.queue.length;
}
}
优先队列的使用方法如下：
var priority = new PriorQueue();
priority.enqueue({name: "leo", priority: 3});
priority.enqueue({name: "tate", priority: 4});
priority.enqueue({name: "kate", priority: 1});
priority.enqueue({name: "kevin", priority: 2});
console.log(priority.dequeue());
console.log(priority.dequeue());
栈
栈是一种先进后出的结构，js中使用数组进行模拟
栈的实现方法如下：
function Stack () {
this.stack = [];
this.top = 0;
this.push = push; // 栈顶添加元素
this.pop = pop; // 栈顶删除元素，并返回
this.peek = peek; // 返回栈顶元素
this.length = length // 获取栈内元素数量
this.clear = clear // 清空栈
function push (ele) {
this.stack[this.top++] = ele;
}
function pop () {
return this.stack[--this.top]
}
function peek () {
return this.stack[this.top-1];
}
function length () {
return this.top;
}
function clear () {
this.top = 0;
}
}