[Vssue]栈与队列总结.md

youngyangyang04 commented 4 months ago

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html

Du1in9 commented 2 months ago

理论基础

栈与队列的底层实现，很多同学都比较模糊。面试题：栈里面的元素在内存中是连续分布的么？

栈是容器适配器，底层容器使用不同的容器。

缺省情况下，默认底层容器是 deque，在内存中的数据分布是不连续的。

栈在系统中的应用：举个例子，cd 进入目录的命令：cd a/b/c/../../ 最后进入 a 目录。

这就是栈的应用：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中。

栈的经典问题

例：6.4 括号匹配问题、6.5 字符串去重问题、6.6 逆波兰表达式问题

队列的经典问题

例：6.7 滑动窗口最大值问题、6.8 求前 K 个高频元素

① 滑动窗口：队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了。

单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则。

② 优先级队列：就是一个披着队列外衣的堆。最小堆是一棵完全二叉树，树中每个结点的值都不大于其左右孩子的值。