栈和队列
Last renew: September 17, 2022 pm
栈和队列总结
栈和队列的原理很清晰，队列先进先出，栈后进先出。
这两种数据结构底层其实都是数组/链表实现的，只是API限制了他们的特性。
栈的经典题目
注：栈内元素在内存中并不是连续分布。
232 225 是处理学习栈和队列底层实现的好题目。一个是用栈来实现队列，一个是用队列来实现栈。
栈在系统中的应用
LC20 系统是如何处理括号、花括号的。写代码前分析好有哪几种不匹配的情况。第一种：字符串中左方向的括号多余了，bupipei；第二种，括号没有多余，但类型不匹配；第三种，字符串中右括号多余了，所以不匹配。
LC71 linux系统又是如何利用cd进入目录的
初次之外，递归的实现是栈 ：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中。然后递归返回的时候，从栈顶弹出上一次递归的各项参数。这就是为什么递归可以返回上一层位置的原因。
字符串去重问题
LC1047 把字符串顺序放到一个栈中，相同的话栈就弹出，最后栈里剩下的元素就是相邻不相同的了。
逆波兰表达式问题
计算的公式，将数字放在前，符号放在后，这样的字符串用对栈计算效率最高。
队列的经典题目
滑动窗口最大值问题
LC239 单调队列
队列没有必要维护窗口里的所有元素，只要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
求前k个高频元素
LC347 优先级队列
什么是优先级队列呢？
就是一个披着外皮的堆，因为优先级队列的对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，所以看起来就像一个队列。
优先级队列内部是按照元素的权值排列，权值可以自己定义。