SOURCE

class Queue {
  constructor() {
    // 存储数据
    this.items = [];
  }
  enqueue(item) {
    // 入队
    this.items.push(item);
  }

  dequeue() {
    // 出队
    return this.items.shift();
  }

  head() {
    // 获取队首的元素
    return this.items[0];
  }

  tail() {
    // 获取队尾的元素
    return this.items[this.items.length - 1];
  }

  clear() {
    // 清空队列
    this.items = [];
  }

  size() {
    // 获取队列的长度
    return this.items.length;
  }

  isEmpty() {
    // 判断队列是否为空
    return this.items.length === 0;
  }

}

// 约瑟夫环问题
// 有一个数组存放了 100 个数据 0-99，要求每隔两个数删除一个数，到末尾时再循环至开头继续进行，求最后一个被删除的数字。

// 创建队列，将 0 到 99 的数字入队；
// 循环队列，依次出列队列中的数字，对当前出队的数字进行计数 index + 1；
// 判断当前出列的 index % 3 是否等于 0，如果不等于 0 则入队；
// 直到队列的长度为 1，退出循环，返回队列中的数字。
function ring(arr) {
    const queue = new Queue();
    arr.forEach(v => queue.enqueue(v));
    let index = 0;
    while(queue.size() > 1) {
        // 依次把第一个元素出队，若该元素不是第三个（(index+1)%3!=0），则依次放到队末,
        // 如此循环直至队列只剩下1个元素
        const item = queue.dequeue();
        if (++index % 3 !== 0) {
            queue.enqueue(item);
        }
    }
    return queue.head();
}

console.log(ring([1,2,3,4,5,6,7]))
console.log(ring([1,2,6]))


//斐波那契数列
// 斐波那契数列（Fibonacci sequence），又称黄金分割数列，
// 因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，
// 故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
// 在数学上，斐波那契数列以如下被以递推的方法定义：
// F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

function fiboSequence(num) {
    if (num < 2) return num;
    const queue = [];
    queue.push(0);
    queue.push(1);
    for(let i = 2; i < num; i++) {
        const len = queue.length;
        queue.push(queue[len - 2] + queue[len  - 1]);
    }
    return queue;
}

console.log(fiboSequence(12))