主要用于记录
Leetcode中利用栈与队列这两种数据结构进行求解的题目解法
题目总结
- 用栈实现队列 定义两个栈
in,out,当插入元素的时候直接插入到in中,当需要弹出元素的时候,首先判断out中是否有元素,有元素直接弹出,没有元素依次弹出in栈中的元素到out栈中并且弹出out栈中的元素 - 用队列实现栈 利用一个队列就可以实现了,在插入元素的时候首先插入元素,然后把之前的元素全部出队并且重新入队列(利用
que.size() - 1次循环完成即可) - 有效的括号 栈的最常见的应用,如果遇到满足要求的两个括号就可以同时出栈了,遇到不同的括号就直接把字符压入到栈中,最后判断栈中的元素是否为空即可
- 删除字符串中的所有相邻重复项 这里还是和上面一样的策略,但是不同的是这里可以直接把
string类型作为栈来使用,本来string类型就类似于vector<char>类型 - 逆波兰表达时求值 对于当前元素,如果是数字直接使用
stoi函数入栈,如果是符号,就可以取出栈顶的两个元素进行相应的运算之后在压入到栈中即可 - 滑动窗口最大值 一道
hard,自己构造单调队列进行求解即可,单调队列中的元素按照元素之间的某一个大小关系来决定出队的顺序而不是按照插入的顺序来确定出队和入队的关系,构造方式: 笔记 - 前K个高频元素 向这一种求解前面的几个元素的题目一般都可以使用堆的数据结构进行求解(就是优先队列的底层实现),注意
C++中的优先的队列的自定义方式,可以参考笔记查看解法,另外这里使用到了利用unordered_map进行数据统计的操作 笔记:
auto cmp = [](const T& a , const T& b) -> bool { return a < b; };
priority_queue<T , vector<T> , function<bool(const T& , const T&)>> pq(cmp);