【近日力扣】斐波那契数列+用两个栈实现队列+从尾到头打印链表

斐波那契数列（简单）

• 动态规划

var fib = function(n) {
    if (n === 0 || n === 1) return n
    let n1 = 0, n2 = 1, res = 0
    for (let i = 1; i < n; i++) {
        res = (n1 + n2) % 1000000007
        n1 = n2
        n2 = res
    }
    return res
};

用两个栈实现队列（简单）

JS 的栈使用起来非常方便，因为其用数组即可实现栈，数组的方法很多

• 首先，入栈也就相当于入队了，push 即可实现。但如何将一个栈中先进去的元素（底部）移到顶部删除（出队）呢？栈，先进后出；队列，先进先出。可以想到将一个栈中的元素再入到另一个栈中，所有元素排序则倒过来了，底部的元素到了顶部，然后再出栈即实现出队

var CQueue = function() {
    this.stack1 = []
    this.stack2 = []
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
	// 此处用了解构赋值，为何不直接使用 this，说实话我也没想通，且那样无法通过
    let [outStack, inStack] = [this.stack2, this.stack1]
    if (!outStack.length) {
        while(inStack.length) outStack.push(inStack.pop())
    }
    return outStack.pop() || -1;
};

从尾到头打印链表（简单）

思考：从尾到头打印，很像栈的方式，先遍历的头部元素最后打印

• 循环

var reversePrint = function(head) {
    let arr = []
    while (head) {
        arr.push(head.val)
        head = head.next
    }
    return arr.reverse()
};

• 递归

var reversePrint = function(head) {
    let arr = [] // arr 在 recursion 外部定义
    let recursion = (head) => {
        if (!head) return
        recursion(head.next)
        arr.push(head.val)
    }
    recursion(head)
    return arr // 此处不需要 reverse，为什么？
};