队列和栈非常相似。但是使用的是FIFO(First In First Out,先进先出)原则。在尾部添加元素,在顶部移除元素。
计算机科学中,最常见的就是打印机的打印队列。
'现在用js创建一个队列吧。要求实现以下方法:
实现队列的封装过程也是相当简单:
class Queue {
constructor(arr = []) {
this.arr = arr;
}
// 从尾部进队
enqueue(item) {
this.arr.push(item)
}
// 从头部出队,返回第一个元素
dequeue() {
return this.arr.shift()
}
// 返回第一个元素
front() {
return this.arr[0]
}
// 返回队列尾部的元素
bottom(){
return this.arr[this.arr.length-1]
}
// 是否为空
isEmpty() {
return this.arr.length == 0;
}
// 返回元素个数
size() {
return this.arr.length
}
// 打印队列
print() {
console.log(this.arr)
}
}
在优先队列中,元素添加和移除是基于优先级的。比如说登机时:头等舱的乘客优先级要更高。又比如说,医院里急诊要优先于门诊。
实现优先队列 PriorityQueue
的原则:
// 优先队列
class PriorityQueue{
constructor(){
this.arr=[];
// 创建一个特殊队列,用来储存元素(包括优先级)
this.QueueElement=function(item, priority){
this.item=item;
this.priority=priority;
}
}
// 移入元素,接收元素和优先级
enqueue(item, priority){
let QueueElement=this.QueueElement;
let queueElement=new QueueElement(item, priority)
let isAdded=false;
for(let i=0;i<this.arr.length;i++){
// 若有较高优先级,插入进去。
if(queueElement.priority<this.arr[i].priority){
this.arr.splice(i,0,queueElement);
isAdded=true;
break;
}
}
// 如果优先级最小,push上去吧
if(!isAdded){
this.arr.push(queueElement)
}
}
// 出队,按正常出队即可
dequeue(item,priority){
return this.arr.shift()
}
// 是否空
isEmpty(){
return this.arr.length==0;
}
// 打印
print(){
for(let i=0;i<this.arr.length;i++){
console.log(`${this.arr[i].item}-${this.arr[i].priority}`)
}
}
}
//测试用例
var aaa=new PriorityQueue();
aaa.enqueue('djtao',2)
aaa.enqueue('dangjingtao',1)
aaa.enqueue('djt',1)
aaa.print();
和原生队列相比,优先队列在实现上的区别在于:
最小优先队列
击鼓传花游戏(Hot Protato)是一个典型的循环队列:一群人绕圈排排坐。花尽快传给下一个人,如此往复。当某时刻停止,花在手上的人就出列。到最后还留在圈子里的人,就是胜者。
// 击鼓传花
const hotProtato = (nameList, num) => {
const queue = new Queue();
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
let eliminated = '';
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
// 典型的蛇咬自己尾巴
queue.enqueue(queue.dequeue())
}
// 每次减1
eliminated = queue.dequeue()
console.log(eliminated + `在击鼓传花中被淘汰`);
}
return queue.dequeue();
}
//测试用例
let names = ['djtao', 'dangjingtao', 'djt', 'dangjt', 'taotao'];
let winner = hotProtato(names, 9);
console.log(`胜者是${winner}`)
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后 [1] 结果+1即为原问题的解。
现有一个数组 a=newArray(100)
,存放了0-99的所有数,要求每隔两个数删掉一个数,到末尾时从头继续。求最后一个被删掉的数。
分析:
// 约瑟夫环
const cycle = () => {
// 创建队列
const queue = new Queue();
for (let i = 0; i < 100; i++) {
queue.enqueue(i);
}
let index = 0;
while (queue.size() > 1) {
let dequeue = queue.dequeue()
index += 1;
if (index % 3 != 0) {
queue.enqueue(dequeue)
}
}
return queue.dequeue();
}
let a = cycle()
console.log(a)
答案为90。
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子队列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
问题背景:斐波拉契计算用递归做相当无脑:
// F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)
const fib=(n)=>{
if(n==1||n==2){
return 1;
}
return fib(n-2)+fib(n-1);
}
//测试用例
for(let i=1;i<11;i++){
console.log(fib(i))
}// 1,1,2,3,5,8,13,21,34,55
console.log(fib(20)/fib(21))//约0.618
却也是及其耗内存。比如说以下测试用例就通过不了:
console.log(fib(100)/fib(101))//计算量太大算不出来了!
需求:不使用递归,而使用队列的方法求斐波拉契数列的第N项。
思考:其实用栈来做是可以的。但是这里用队列更省内存。我们能获取的的就是队列的底部和队列的头部。那么可以这样构造:
[1,1]
。每次计算时只考虑头部和底部,也就是说队列保留2个元素即可!
const fib=(n)=>{
if(n==1||n==2){
return 1
}
const queue=new Queue([1,1]);
for(let i=0;i<n-2;i++){
// 从头部获取较小的a
let a=queue.front();
// 从尾部获取较大的b,它将作为下次循环的头部
let b=queue.bottom();
// 弹出a
queue.dequeue();
// 加入a+b
queue.enqueue(a+b);
}
return queue.bottom()
}
// 测试用例
for(let i=1;i<11;i++){
console.log(fib(i))
}// 1,1,2,3,5,8,13,21,34,55
console.log(fib(100)/fib(101))//0.6180339887498949
如题。二者的数据管理模式是相反的。
class Stack{
constructor(arr=[]){
this.queue=new Queue(arr);
}
push(item){
this.queue.enqueue(item);
// if(this._queue.isEmpty){
// this._queue.enqueue(item);
// }
}
// 从头部删除
pop(){
const _queue=new Queue();
for(let i=0;i<this.queue.size();i++){
let item=this.queue.dequeue();
_queue.enqueue(item);
}
let result=this.queue.dequeue();
this.queue=_queue;
return result
}
// 取栈顶,实际上取的是队列的bottom
top(){
return this.queue.bottom()
}
}
//测试用例
var a=new Stack();
a.push(1);
a.push(2);
a.push(3);
console.log(a.pop())//3
a.push(4)
console.log(a.pop())//4
console.log(a.top())//2
那么栈的基本方法都实现了。
通过console打印如图的三角排列。
const yangHui = (n) => {
let queue = new Queue([1, 1]);
// 打印第n行数据
const print = (_n) => {
const _queue = new Queue();
for (let i = 0; i < _n; i++) {
// 判断边界
if (i == 0 || i == _n - 1) {
_queue.enqueue(1);
} else {
let a = queue.dequeue();
let b = queue.front();
_queue.enqueue(a + b);
}
}
//存放新的队列
queue = _queue;
queue.print()
}
// 调用
for (let i = 1; i < n + 1; i++) {
print(i);
}
}
yangHui(10)
方法也是比较简单。注意判断边界为1的情况。
当打开浏览器新的标签页,就会创建一个新的任务队列。每个标签都是单线程处理任务,这被称为事件循环。
逐层打印一棵树的节点,socket的实现。用的也是队列。