栈

一、栈是什么？

• 一个后进先出的数据结构

• JavaScript中没有栈，但是可以使用Array来实现栈的所有功能

  
  
• 代码

const stack = []

// 入栈
stack.push(1)
stack.push(2)

// 出栈
// pop() 移除数组的最后一项 并返回它
const item1 = stack.pop()
const item2 = stack.pop()

二、栈的应用场景

• 需要后进先出的场景
• 比如: 十进制转二进制、判断字符串的括号是否有效、函数调用堆栈...

2.1 场景一: 十进制转二进制

• 后出来的余数反而要拍到最前面。

• 把余数依次入栈，然后再出栈，就可以实现余数倒叙输出。

  
  
• 代码

/**
 * 请用栈这个数据结构，将100这个十进制数字转为二进制
 */

let transcodingStack = (s) => {
    const resArr = [];
    const stack = [];

    if (s == 0) return 0;
    if (s) stack.push(s);

    while (stack.length) {
        const n = stack.pop();
        if (parseInt(n / 2) !== 0) {
            resArr.push(n % 2);
            stack.push(parseInt(n / 2));
        } else {
            resArr.push(1);
        }
    }

    let res = "";

    for (let i = resArr.length - 1; i >= 0; i--) {
        res += resArr.pop();
    }

    return res;
}

console.log(transcodingStack(100)); // 1100100

2.2 场景二: 有效括号

[leetcode对应链接]https://leetcode-cn.com/problems/valid-parentheses/

• 越靠后的左括号，对应的右括号越靠前。

• 左括号入栈，右括号出栈，最后栈空了就是合法的。

  
  
• 思路

对于没有闭合的左括号而言，越考后的左括号，对应的右括号越靠前。 满足后进先出，考虑用栈。
新建一个栈
扫描字符串，首先判断是否为基数，基数则返回false，遇到左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接返回false。
最后栈空了就为true，否则为false
时间复杂度 O(n) 空间复杂度 O(n)

• 代码

var isValid = function (s) {
    // 判断是否为基数 直接返回false
    if (s.length % 2 === 1) return false;

    const stack = []
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === "(" || c === "[" || c === "{") {
            // 入栈
            stack.push(c)
        } else {
            const t = stack[stack.length - 1]
            if (
                (t === "(" && c === ")") || (t === "[" && c === "]") || (t === "{" && c === "}")
            ) {
                // 出栈
                stack.pop()
            } else {
                return false;
            }
        }
    }

    return stack.length === 0;
};

2.3 场景三: 函数调用堆栈

• 最后调用的函数，最先执行完。

• JS解释器使用栈来控制函数的调用顺序。

  
  
• 代码

let func1 = () => {
    func2()
}
let func2 = () => {
    func3()
}
let func3 = () => {}

func1()

// debugger func1()
// 调用堆栈里面首先调用一个匿名函数anonymous(此文件入口)
// 依次调用 anonymous=>func1=>func2=>func3
// 依次销毁 func3=>func2=>func1=>anonymous

三、技术要点

• 栈是一个后进先出的数据结构
• JavaScript中没有栈，但是可以使用Array实现栈的所有功能
• 栈常用操作:

push 入栈
pop 出栈
stack[stack.length-1] 栈顶

四、leetcode题(持续更新)

• 1047 https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function (S) {
    const stack = []

    if (!S) return "";
    if (S) stack.push(S[0])

    for (let i = 1; i < S.length; i++) {
        if (S[i] === stack[stack.length - 1]) {
            stack.pop()
        } else {
            stack.push(S[i])
        }
    }

    return stack.join("");
};

removeDuplicates("abbaca") // "ca"

• 请用ES6的class 封装一个stack的类，包括push，pop，peek方法

class Stack {
    constructor(stack) {
        this.stack = stack
    }

    push(item) {
        this.stack.push(item)
    }

    pop() {
        return this.stack.pop()
    }

    peek() {
        return this.stack[this.stack.length - 1];
    }
}