一、栈是什么？

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

• 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];    }}

原著是一个有趣的人,若有侵权,请通知删除