leetcode｜栈与队列

type

status

date

slug

summary

栈与队列都是容器接口，而非容器；

栈与队列可选容器，缺省状态下是deque；

提供push，pop等操作，但不提供送代器，不提供走访功能，因为只能在一边进行插入，弹出操作；

1.栈在系统方面有许多应用

Linux命令 cd/a/b/....运用栈的知识，确认进入了a目录；

函数递归必须要在栈中进行

2.匹配问题

例如，leetcode20，有效的括号

例如1047，删除字符串中所有相邻重复项

150，逆波兰表达式求值,此题思路一样，，另外有点消消乐的感觉，实现代码要比前两道还简单，关键stoi函数的使用之前不清楚

队列方面遇到了两种值得细究的结构：单调队列，优先级队列

看题239，滑动窗口最大值

(主要思想是队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来一个单调队列

而且不要以为实现的单调队列就是对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。)

用deque作为单调队列的底层数据结构，C++中deque是stack和queue默认的底层实现容器（这个我们之前已经讲过），deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。 -carl

347.前k个高频元素

本题主要有以下几点

1.用unordered_map存放元素及出现的频率

2.用优先级队列实现小顶堆

另外还要注意一下如比较函数等细节

附上代码随想录中对于这一部分的描述：

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢，使用快排要将map转换为vector的结构，然后对整个数组进行排序，而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。