javascript数据结构与算法——队列
javascript数据结构和算法——队列
在写队列的相关的算法之前需要明白队列的相关的性质——先进先出
<!DOCTYPE html>
<html lang="cn">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function Quene() {
// 1、构造初始化变量
this.items = [];
}
// 1、设置加入元素
Quene.prototype.enQuene = function (element) {
this.items.push(element);
}
// 2、设置删除元素
Quene.prototype.deQuene = function () {
this.items.shift();
}
// 3、设置查找第一个元素
Quene.prototype.front = function () {
return this.items[0];
}
// 4、查看队列长度
Quene.prototype.size = function () {
return this.items.length;
}
// 5、查看队列是否为空
Quene.prototype.isEmpty = function () {
return Boolean(this.items.length);
}
// 6、将队列设置成数组
Quene.prototype.toString = function () {
let result = " ";
for (let i = 0; i < this.items.length; i++) {
result += this.items[i] + " ";
}
return result;
}
let quene = new Quene();
quene.enQuene("aaa");
quene.enQuene("bbb");
quene.enQuene("ccc");
quene.enQuene("ddd");
quene.enQuene("eee");
console.log(quene.items);
quene.deQuene();
quene.deQuene();
console.log(quene.items);
console.log(quene.front());
console.log(quene.isEmpty());
console.log(quene.size());
console.log(quene.toString());
</script>
</body>
</html>
以上便是队列数据结构的实现。 下面通过使用队列实现击鼓传花的功能： 规则：规定一组人，并且规定一个数字，从头开始数，数到这个数字所对应的人，将其去除，然后再依次数，最终将没有数到的同学输出 算法实现：
<script>
// 这里是队列
function Quene() {
this.item = [];
}
Quene.prototype.enquene = function (element) {
this.item.push(element)
}
Quene.prototype.dequene = function () {
return this.item.shift();
}
Quene.prototype.front = function () {
return this.item[0];
}
Quene.prototype.isEmity = function () {
return !Boolean(this.item.length)
}
Quene.prototype.size = function () {
return this.item.length;
}
Quene.prototype.toString = function () {
let result = "";
for (let i = 0; i < this.item.length; i++) {
result += this.item[i] + " ";
}
return result;
}
// 这里是击鼓传花的算法
function passQuene(arrList, num) {
let quene = new Quene();
for (let i = 0; i < arrList.length; i++) {
quene.enquene(arrList[i]);
}
while (quene.size() > 1) {
for (let j = 0; j < num-1; j++) {
quene.enquene(quene.dequene());
}
quene.dequene();
}
return quene.front();
}
let result = passQuene(["张三",李四,王五,赵六,刘能],3);
console.log(result);
</script>