背景

前几天一个学弟问到我一个栈的问题，正好也很久没有熟悉这个概念了，就复习并简单给小学弟讲了一下，顺便发布一下此文章，希望也能对您有所帮助。

1.栈的定义

要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。 栈是一种特殊的线性表，仅能够在栈顶进行操作有着先进后出（后进先出）的特性。

2.栈的实现

从数据存储角度看，实现栈有两种方式，一种是以数组做基础，数组最简单的实现方式，一种是以链表做基础，这次咱们就以第一种方式实现

2.1 数据存储

首先定义一个简单的 Stack 类

function() {    let items = []}

2.2栈的方法push 添加一个元素到栈顶pop弹出栈顶元素top 返回栈顶元素，注意不是弹出isEmpty 判断栈是否为空size 返回栈里元素的个数clear 清空栈

代码实现

function Stack() {    let items = [];  // 存储数据    // 从栈顶添加元素，也叫压栈    this.push = function(item) {        items.push(item);    };    // 弹出栈顶元素    this.pop = function() {        return items.pop();    }    // 返回栈顶元素    this.top = function() {        return items[items.length-1];    }    // 判断栈是否为空    this.isEmpty = function () {        return items.length === 0    }    // 返回栈大小    this.size = function () {        return items.length;    }    //  清空栈     this.clear = function () {        items = [];    }}

一个栈的实现是不是很简单，就是这么简单，那么栈有什么作用呢，下边接着看看

3. 栈的应用

3.1 请编写一个判断字符串的括号是否合法，就是 字符串里括号成对出现，是不是就是我们的编辑器代码校验也是这个呀

"((sdjs)sds)sds(")"((sdjs)sds)sds""()((())"

3.1.1 分析

括号会存在嵌套关系，也存在并列关系，如果用数组存储这些括号，然后想办法一对一的抵消，似乎可行，可是如何判断一个左括号对应哪一个右括号呢，站在数组的层面可能会蹦，甚至绝望，但是站在栈的肩膀上，就很简单了。

我们可以遍历字符串，对 每个字符串操作

遇到左括号，就把左括号压入栈中遇到右括号，判断栈是否为空，为空说明左括号与之对应，缺少左括号，字符串括号不合法，如果栈不为空，则把栈顶元素移除，这对括号抵消掉了当循环结束，如果栈为空，说明所有对左右括号都抵消了，如果栈里还有元素，则说明缺少右括号，字符串括号不合法

3.1.2 代码

function is_True(string){    let stack = new Stack();    for(let i = 0; i < string.length; i++) {        let item = string[i];        // 遇到左括号进栈        if(item === "(") {            stack.push(string[i])        }else if (item === ")") {            if(stack.isEmpty()) { // 遇到右括号判断栈是否为空                return false            }else {                stack.pop()  //  弹出左括号            }        }    }    // 如果为空 说明 字符串括号正确    return stack.isEmpty()}console.log(is_True("((sdjs)sds)sds("));falseconsole.log(is_True("((sdjs)sds)sds")); trueconsole.log(is_True("()((())")); false

3.2 计算逆波兰表达式

也叫后缀表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式

比如

['4','13','5','/', '+'] 等价于 (4 + (13 / 5)) = 6['10', '6', '9', '3', '+', '-11', '*', '/','*','17', '+', '5', '+'] 等价  ((10*(6/((9+3)* -11))) +17) +5

3.2.1 分析

如果元素不是 加减乘除 中的一个 ，就压入栈中如果元素是 加减乘除中的某一个，则从栈中连续弹出两个元素，并对这两个元素进行机选，将计算结果压栈中；循环结束后，栈中只有一个元素 这个元素就是表达式对结果

3.2.2 实现

function calc_exp(exp) {    let stack = new Stack()    for(let i = 0; i < exp.length; i++) {        let item = exp[i];        if(["+", "-", "*", "/"].indexOf(item) !==-1) {            let value_exp1 = stack.pop();            let value_exp2 = stack.pop();            var exp_str = value_exp2 + item + value_exp1;            let res = parseInt(eval(exp_str)); //计算并取整 eval 方法可以直接计算表达式返回结果            // 计算结果压入栈中            stack.push(res.toString());        }else {            stack.push(item);        }    }    return stack.pop();}console.log(calc_exp(['4','13', '5', '/', '+']))     6

至此，就使用javascript实现了一个简单的栈，小编是一名前端程序员，如果您有收获还请点赞关注偶。