数据结构 — 栈(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
};
本文共 802 字,上次修改于 Oct 12, 2022
相关标签: 算法, 数据结构