栈 队列

栈

什么是栈？

栈、是一种后进先出(LIFO,Last-In-First-Out)的数据结构。记住这个英文缩写，避免在一些地方出现了LIFO我们不知道是什么，就很尬。

后进先出我们记住下图，堆叠的盘子，顶部的盘子是最后放上的，但是当我们洗盘子的时候，肯定是从上面拿的。

image.png

对于js来说怎么实现栈呢？

我们先看一下，栈结构的一个表述图。知道一下什么是栈顶和栈底(正如上面所说，后入先出)。入栈和出栈都是从栈顶操作的。入栈使用了push方法、出栈使用了pop方法。

image.png

push

push方法在对数组进行添加元素时，很常见。我这里想要提的是push()的返回值。

let a = []
let b = a.push(12)   
console.log(b)       // 1

push()方法的返回值，是数组的长度。

pop

从图上可以知道，pop的作用就是从数组的尾部移除元素(数组的末尾是栈顶)。我也要提一下返回值。

let arr = [1,2,3,4]
let result = arr.pop()
console.log(result)     // 4

这里pop的返回值是移除的元素。

栈的应用

判断函数的括号

如下，我们判断括号使用错误的状态。当然这种情况，编辑器就会报错了。

// 正确
function fun(){
}
// 错误
function fun( ]{
}

函数的括号可以看成字符串'()'和 '( ]'，然后遍历这个字符串。如果当前元素的上个元素是'('并且当前元素是')'，就将栈顶的元素移除(此时栈顶的元素是当前元素的上个元素)。其它情况就进栈。

image.png

function check(param) {
    let arr = param.split('')
    let stack_arr = []
    for (let i = 0; i < arr.length; i++) {
        // 上一项是( 并且这一项是 ) 就出栈 也就是把上一项移除了
        if (arr[i - 1] === '(' &amp;&amp; arr[i] === ')') {
            stack_arr.pop()
        } else {
            // 否则 把这项进栈
            stack_arr.push(arr[i])
        }
    }
    return stack_arr.length
}

check('(]')

队列

什么是队列？

而队列数据结构就更简单了，队列也就是排队。就向下面这张排队做核酸的图片。队列先进先出(FIFO First-In-First-Out)

image.png

js怎么实现队列？

入队还是用push方法，出队用到了shift方法

image.png

shift

shift则是从数组的头部移除元素。shift方法的返回值是移除的元素。

let a = [1,2,3,4]
let b = a.shift()
console.log(1)