队列的面试题.md

实现击鼓传花

给定一个数组arr，给定一个数字n，每数1个数，队列头部的元素就出列，并立即重新入列成为最后尾部元素，每当到n 时，此时数到的元素从数组中移除，并不进行入队操作，直到数组中只剩下一个元素，并最终返回该元素。

// 07.ts
import ArrayQueue from "./01";

function fn(names:string[], num:number){
    if(names.length === 0) return -1
    const queue = new ArrayQueue<string>();
    for(const name of names) queue.enqueue(name);
    while(queue.size() > 1){
        for(let i=0;i<3;i++){
            const name = queue.dequeue();
            if(name) queue.enqueue(name)
        }
        queue.dequeue()
    }
    
    return queue.dequeue();
}

const arr = ['a','b','c','d','e'];
const res = fn(arr, 3);
console.log(res)

约瑟夫环问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

// 08.js
import ArrayQueue from "./01";

function fn(numbers:number, num:number){
    const queue = new ArrayQueue<number>();
    for (let index = 0; index < numbers; index++) {
       queue.enqueue(index);
    }
    while(queue.size() > 1){
        for(let i=1;i<num;i++){
            queue.enqueue(queue.dequeue()!);
        }
        queue.dequeue()
    }
    
    return queue.dequeue();
}

console.log(fn(10, 17))