栈（Stack）

基础知识 #

栈是一种常用的数据结构，它最大的特点是“后入先出”，即后进入栈中的元素最先出来，为了确保“后入先出”（LIFO）的顺序，栈的插入（push）和删除（pop）操作都发生在栈顶。

如果数据保存的顺序和使用顺序相反，即最后保存的数据最先被使用，有“后入先出”的需要，可以考虑将数据保存到栈中。

数据结构 #

JavaScript 和 Go 中都没有实现专门的栈接口，可以用数组来模拟。

JavaScript #

可以使用 shift + unshift 或者 push + pop 实现一个栈。

Golang #

Golang 的数组没有封装常用方法，以下标 len(a) - 1 当栈顶为例：

func main() {
	stack := []int{}
	stack = append(stack, 1)
	stack = append(stack, 2)
	fmt.Println(stack)
	stack = stack[:len(stack)-1]
	fmt.Println(stack)
}
//[1 2]
//[1]

单调栈 #

单调栈实际上就是栈，只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。

单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置元素的数。

单调栈一般用于解决第一个大于 xxx 或者第一个小于 xxx 这种题目。

参考 https://www.cnblogs.com/liang24/p/14200734.html

常见题型 #

单调栈法 #

很多时候保存在栈中的数据是排序的。根据题目的不同，栈中的数据既可能是递增排序的，也可能是递减排序的。因此，有人将这种用排序的栈解决问题的方法称为单调栈法。

后缀表达式（逆波兰表达式） #

中缀表达式适合人类阅读，但是对计算机而言中序表达式是非常复杂的结构。逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。后缀表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。

剑指 Offer II 036. 后缀表达式

题目列表 #

20. 有效的括号

var isValid = function(s) {
    let nums = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(" || s[i] === "{" || s[i] === "[") {
            nums.push(s[i])
        } else {
            let pre = nums.pop()
            if (s[i] === "}" && pre === "{") {
                continue
            }
            if (s[i] === ")" && pre === "(") {
                continue
            }
            if (s[i] === "]" && pre === "[") {
                continue
            }
            return false
        }
    }
    if (nums.length === 0) {
        return true
    }
    return false
};