数据结构学习笔记--栈

布满荆棘的人生 2022-01-20 03:53 318阅读 0赞

### 为什么要学习数据结构？ ###

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

## 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、最后 ##

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