栈

一、栈是什么?

  • 一个后进先出的数据结构
  • 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题(持续更新)

/**
 * @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];
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容