算法力扣刷题总结篇 —

算法力扣刷题总结篇 ——【四】

前言

栈和队列篇题目学习结束。
总结：

一、结构基础

stack类

（1）使用栈（后入先出）的结构时，用它。

（2）容器适配器（container adaptor）。本身不算容器，和vector不是一类，但是底层实现使用容器（比如deque、list、vector），对底层的容器结构封装接口，所以叫容器适配器。

（3）哪些容器可以作为stack类的底层？

答：外部看着一个栈，只有一个开口，就是“栈顶”。在底层的容器其实是容器的“back”尾部，作为开口，当作栈顶。如果容器类有：empty、size、push_back、pop_back、back的功能，能获取到最后一个元素，就可以作为stack的底层。
比如：vector、deque、list。默认是deque。
所以stack内的元素不一定是连续存放的：如果是vector，那么是连续存放；如果是deque，不是严格连续存放；如果是list，链表就不是连续存放。（连续存放指内存连续一片）

（4）stack类模版的定义：

template <class T, class Container = deque > class stack;
先指定元素类型，再指定底层容器类型。

（5）因为stack是封装底层类，所以成员函数不算多，也不提供iterator。

构造函数：
- 不带参数，构造空栈。stack< int > st;
- 用vector、deque、list对象直接初始化。比如：vector< int > nums= {1,3,2}; stack<int,vector< int >> st(nums);
empty()
- 无参数、返回bool。空，返回true；不空，返回false。
size()
- 无参数，返回size_type，无符号整数。获取大小。
top()
- 无参数，返回栈顶元素的引用。
- 其实是call 底层容器的back()函数。
push()
- 有参数，push的对象，只能一个参数。没有返回值。
- 其实是call 底层容器的push_back()函数。
pop()
- 无参数，无返回值。弹出栈顶。
- 其实是call 底层容器的pop_back()函数。
emplace()
- 有参数，也是往栈里压入元素操作。但是元素的构造是依靠emplace传参给元素类型的构造函数。没有返回值。
- 和push操作一样。但是区别：push的参数是已经创建好的对象，进行copy；emplace的参数是要传给元素类型的构造函数，还没有创建对象。
- 其实是call 底层容器的emplace_back()函数。
swap()
- 有参数，类型和调用者一样，同类型的栈。交换栈的内容，没有返回值。
- 和非成员函数重载的 swap()传两个参数一个意思。

（6）关系运算符:!= 、==、<、>、<=、>= 重载。比较两个栈。

其实是call 底层容器的重载元素符操作。

queue类

#include < queue > 头文件中有两个类：queue和priority_queue。
这里说queue：
（1）和stack原理一样：容器适配器；

（2）操作：先入先出。FIFO。

（3）所以是两端开口，那么底层容器的功能：empty、size、push_back、pop_front、back、front。比如：deque和list满足。vector不满足。默认deque。

（4）queue类模版定义：

template <class T, class Container = deque > class queue;

（5）成员函数：

stack（5）中queue都有。除了top()。
top()换成front()和back()。

（6）关系元素符重载同理。

priority_queue类

本质实现一个堆结构，默认是最大堆。但披着队列的外皮。具体详解和使用——此链接
（1）成员函数：同stack。
（2）没有关系运算符。
（3）容器适配器，需要有：empty、size、front、push_back、pop_back。比如：vector和deque满足，list不满足。默认是vector。
（4）重点是定义：

template <class T, class Container = vector, class Compare = less > class priority_queue;
如果想要实现最小堆，就得改变Compare。自定义比较函数。
自定义比较函数：用一个类Mycmp重载()运算符。参数是元素类型，返回bool。

二、题目回顾

总结题目参考链接

（1）二十七【232.用栈实现队列】两个栈。当stack2为空，才触发一次把stack1中元素全部pop放入stack2。所以push只需要stack1，pop只需要stack2，但要先判断空否？
（2）二十八【225. 用队列实现栈】一个队列就可以。push只管push，pop时候，把除最后一个元素外前面所有的“阻碍”，都再重新入队。
（3）栈结构操作：

二十九【20. 有效的括号】两种方法
- 参考给的方法：如果遇到左括号，把对应的右括号压入栈中；如果遇到右括号，判断栈里面有没有元素？（右括号多余）；栈顶元素是不是该右括号？（嵌套顺序）；等遍历结束，栈是不是空？（左括号多余）。
- 尝试实现的方法：如果遇到左括号，把左括号压入栈中；如果遇到右括号，如果栈为空：说明右括号多余（false）；如果栈顶元素不是对应左括号，说明嵌套顺序错误；如果遍历结束，栈不为空，说明左括号多余。
三十【1047. 删除字符串中的所有相邻重复项】类似“消消乐”，判断当前元素是否和栈顶元素相同，如果相同，弹出栈顶元素。
三十一【150. 逆波兰表达式求值】后缀表达式符合计算机的思路。遇到数字压入栈中，遇到运算符，取出栈顶两个数字计算之后，把结果压入栈中。
三十四【71.简化路径】明显用栈结构。但是构造的栈结构只放有效的文件名。最后pop文件名再处理间隔“/”。为了统一获得文件名，不在最后没有“/”出问题，先对path末尾加“/”。

（4）队列结构操作：

三十二【239. 滑动窗口最大值】自定义单调队列。用deque结构。如果进入窗口的元素，在此之前没有比它大的，全部pop卷走，让最大的值占据队列出口。当然第一步要放入第一个窗口内的元素。如果pop参数不是最大值，不操作pop。
三十三【347.前 K 个高频元素】用priority_queue结构。构造最小堆。