特点:先进先出(也叫FIFO:First In First Out)
结构图:
这跟我们生活中的排队买票很像:谁先排在前面,谁先买票 .
队列常见的操作
- enqueue(el) : 向队列尾部添加一个新的项。
- dequeue(): 移除队列的第一项,并返回被移除的元素。
- front() :返回队列中的第一个元素,队列不做任何变动。
- isEmpty() :如果队列中不包含任何元素返回 true,否则返回 false。
- size() :返回队列包含的元素个数。
- toString(): 将队列中的内容转成字符串形式。
代码实现
class Queue {
constructor() {
this.items = [];
}
// 入队
enqueue(item) {
this.items.push(item);
}
// 出队
dequeue(item) {
return this.items.shift();
}
//队列第一个元素
front() {
return this.items[0];
}
// 队列是否空
isEmpty() {
return this.items.length === 0
}
//队列大小
size() {
return this.items.length;
}
//队列内容
toString() {
let result = '';
for (let item of this.items) {
result += item + " ";
}
return result;
}
}
const queue = new Queue();
测试
//测试代码
// enqueue()
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
console.log(queue.items); //["a", "b", "c", "d"]
// dequeue()
queue.dequeue();
queue.dequeue();
console.log(queue.items); //["c", "d"]
// front()
console.log(queue.front()); // c
// isEmpty()
console.log(queue.isEmpty()); // false
// size()
console.log(queue.size()); // 2
// toString()
console.log(queue.toString()); //c d
队列应用:实现小游戏–击鼓传花。
想要的效果:
const names = ['lily', 'lucy', 'tom', 'tony', 'jack'];
const targetIndex = passGame(names, 4);
console.log('击鼓传花', names[targetIndex]); //--> lily
实现思路:
传入一组数据集合和设定的数字 number,循环遍历数组内元素,遍历到的元素为指定数字 number 时将该元素删除,如果不是 number 时,将number 数字之前的人重新放入到队尾,直至数组剩下一个元素。
实现代码:
function passGame(nameList, number) {
const queue = new Queue();
// 先组成一个队列
for (let name of nameList) {
queue.enqueue(name);
}
console.log("原始数组:", queue.items); //['lily']
// 开始数数
while (queue.size() > 1) {
// 不是 number 时,重新加入到队尾
// 是 number 时,将其删除
for (let i = 0; i < number - 1; i++) {
// 即把队头删除的元素,重新加入到队尾中
queue.enqueue(queue.dequeue());
console.log("非number加入队尾", queue.items);
}
queue.dequeue()
console.log(`删除${number}后`, queue.items);
}
console.log("最终数组:", queue.items); //['lily']
// 获取最后剩下的那个人
const endName = queue.front();
return nameList.indexOf(endName);
}
// passGame() 测试
const names = ['lily', 'lucy', 'tom', 'tony', 'jack'];
const targetIndex = passGame(names, 4);
console.log('击鼓传花最终赢家是:', names[targetIndex]); //lily
过程说明(一看这个就懂了):