数据结构学习笔记--栈

相信大家都听过一句话 程序=数据结构+算法 ，数据结构和算法是脱离编程语言而存在的，不同的语言有不同的实现版本，但内在的逻辑却不会有变化，所体现的编程思想不会有变化。虽然前端可能对数据结构和算法的要求没有那么高，但是作为一个 程序员 数据结构是我们应该掌握的基本知识。

1、栈的定义

栈是一种特殊的线性表，我们只能够在栈顶对其进行操作，有着 先进后出 的特点

2、栈的实现

实现栈可以用数组来存储数据，这是最简单的方式。

// 定义一个stack类
function Stack() {
    let items = [] // 用于存储数据，
}

复制代码

2.1定义栈的一些常用的方法

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

你还可以定义其他你认为你将要用到的方法，这些只是一些常用的方法

push

// 添加一个元素到栈顶
this.push = (data) => {
    items.push(data)
}
复制代码

pop

// 删除栈顶元素
this.pop = () => {
    return items.pop()
}
复制代码

top

// 返回栈顶元素
this.top = () => {
    return items[items.length - 1]
}
复制代码

isEmpty

// 检查栈是否为空
this.isEmpty = () => {
    return items.length === 0
}
复制代码

size

// 返回栈的大小
this.size = () => {
    return items.length
}
复制代码

clear

// 清空栈
this.clear = () => {
    items = []
}
复制代码

最终代码

function Stack() {
    let items = []
    this.push = (data) => {
        items.push(data)
    }
    this.pop = () => {
        return items.pop()
    }
    this.top = () => {
        return item[items.length - 1]
    }
    this.isEmpty = () => {
        return items.length === 0
    }
    this.size = () => {
        return items.length
    }
    this.clear = () => {
        items = []
    }
}

复制代码

3、栈的应用

3.1、检查括号的合法性

下面的字符串中包含小括号，请编写一个函数判断字符串中的括号是否合法，所谓合法，就是括号成对出现

• sdf(ds(ew(we)rw)rwqq)qwewe 合法
• (sd(qwqw)sd(sd)) 合法
• ()()sd()(sd()fw))( 不合法

思路分析

括号存在嵌套关系，也存在并列关系，如果是用数组存储这些括号，然后再想办法一对一对的抵消掉，似乎是一个可行的办法，可是如何判断一个左括号对应的是哪个右括号呢？站在数组的肩膀上思考这个问题，就陷入到一种无从下手的绝望之中。

现在，我们站在栈的肩膀上思考这个问题，解题的步骤就非常简单，我们可以使用for循环遍历字符串的每一个字符，对每个字符做如下的操作：

• 遇到左括号，就把左括号压如栈中
• 遇到右括号，判断栈是否为空，为空说明没有左括号与之对应，缺少左括号，字符串括号不合法，如果栈不为空，则把栈顶元素移除，这对括号抵消掉了

当for循环结束之后，如果栈是空的，就说明所有的左右括号都抵消掉了，如果栈里还有元素，则说明缺少右括号，字符串括号不合法。

代码实现

function is_leagl(str) {
    let stack = new Stack()
    for(let i = 0; i < str.length; i ++) {
        let item = str[i]
        if(item === '(') { // 左括号入栈
            stack.push(item)
        } else if (item === ')') { // 右括号
            if(stack.isEmpty()) { // 检查栈是否为空
                return false
            } else { // 不为空弹栈
                stack.pop()
            }
        }
    }
}
复制代码

栈还有其他很多的应用比如：1、计算代数式；2、构造表达式；3、用于函数得调用等等。

4、最后

在学习了栈之后了解到了它的方便之处，虽然是基于数据来实现的，但是在某些场景使用起来比数据更加方便快捷。后面会继续学习队列、链表、树、图等其他数据结构来丰富自己的知识。