常用数据结构《二》· 栈

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

刘亚东；曲心慧编．C/C++常用算法手册：中国铁道出版社，2017.09

JavaScript实现栈结构

//@ 利用数组方法特性，根据栈只能在某一端添加或删除数据也就是先进后出原则实现栈
class Stack {
    constructor() {
        this.stack = [];
    }
    //* 数据进栈
    push(item) {
        this.stack.push(item);
    }
    //* 数据出栈
    pop() {
        this.stack.pop();
    }
    //* 返回栈尾数据
    peek() {
        return this.stack[this.getCount() - 1];
    }
    //* 返回栈的长度
    getCount() {
        return this.stack.length;
    }
    //* 是否为空栈
    isEmpty() {
        return this.getCount() === 0;
    }
}

栈的应用·括号匹配

//@ 栈的应用--括号匹配
var isValid = function (s) {
    let map = {
        '(': -1,
        ')': 1,
        '[': -2,
        ']': 2,
        '{': -3,
        '}': 3
    };

    //* 利用数组模拟栈结构
    let stack = [];

    //* 去除字符串中的字母和特殊字符后的数组
    let arr = []

    //* 去掉无用符号，利用正则表达式
    let newStr = s.replace(/\t|\r|\n|\s|\f|\"|\u|\*|\\|\$/ig, "");

    //* 删除字符串内的字母
    for (const i of newStr) {
        if (i < 'a' || i > 'z') {
            arr.push(i);
        }
    }
    s = arr;

    //* 根据map将括号进行匹配，匹配成功进栈，失败出栈并返回false
    for (let i = 0; i < s.length; i++) {
        if (map[s[i]] < 0) {
            stack.push(s[i]);
        } else {
            let last = stack.pop();
            if (map[last] + map[s[i]] != 0) {
                return false;
            }
        }
    }

    //* 站内还有未匹配的括号则返回 false
    if (stack.length > 0) {
        return false;
    }

    return true;
};
//@ 测试
console.log(isValid('[(dgy{$dg***}h**f)]')); // true
console.log(isValid('[(dgy{$dg**}hf])]')); // false