代码随想录一刷笔记_栈与队列

60+在408的算法考察难度和深度上还是收手了👍）

栈与队列理论基础

四个基本问题

• c++中stack是容器莫

  “栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。”

  故，stl中stack往往不被归类为容器，而被归类为container adapter（容器适配器）

• 我们使用的stack是属于哪个版本的stl

  三个最为普遍的stl版本：

  • HP STL。c++的第一个STL版本，且开源。
  • P.J.Plauger STL。被visual c++编译器采用，不开源。
  • SGI STL。被Linux的c++编译器GCC采用，开源。（显然用的是这个👌）

• 我们使用的stl中stack是如何实现的

  

  栈的底层实现可以是vector，deque，list等数据结构。

  在SGI STL中，stack默认是以deque为基础实现的（封住了一端）。

• stack提供迭代器来遍历stack空间莫

  栈只提供了push和pop等接口访问元素，不提供走访功能，也不提供迭代器。

用栈实现队列（232）

这一题使用两个栈模拟队列q的q.pop()，q.push()，q.getTop操作。

栈的基本操作：

// 声明栈
stack<int> s;

// 栈的基本操作
s.push();
s.pop();
s.top();
s.empty();
s.size();

用队列实现栈（225）

这一题使用两个队列模拟栈s的s.pop()，s.push()，s.getTop操作。

• 这一题的优化：可以指使用一条队列就能模拟栈的功能。

  将队列中弹出的元素添加回该条队列，最后的那一个元素也就是对应的栈的栈顶元素。

队列的常用操作：

// 声明队列
queue<int> q;

// 队列的基本操作
q.empty();
q.size();
q.front();	q.back();
q.push();	q.pop();

有效的括号（20）

经典的括号匹配问题）

tips:关于左右括号匹配判断的写法

if ((top == '(' && ch != ')') || (top == '{' && ch != '}') || (top == '[' && ch != ']'))
{ .... }

删除字符串中的所有相邻重复项（1047）

这一题有两种办法：

• 判断字符串是否有相邻重复项并去重，重复该操作直到不存在重复项。

• 使用栈。

  栈用来存放遍历过的元素，当遍历当前的元素的时候，去栈里查看是否遍历过相同数值的相邻元素。

  更进一步，直接把输出的result作为一个栈进行遍历，可以在一次循环后直接输出。时间复杂度达到了O(n)。

逆波兰表达式求值（150）

逆波兰表达式，也就是后缀表达式，可以借用栈将其转化为中缀表达式。

tips：

• stol()函数 将字符串转换为 long 类型的整数。（属于string头文件中，为 string to long 的缩写）
• c++中单引号和双引号表示不同的数据类型
  • ‘ ‘ 用于表示字符 char类型数据
  • “ ” 用于表示字符串 string类型数据

滑动窗口最大值（239）

👍这一题最方便快捷的方法（如果有）的话，是调用队列的pop()，push()，getMaxValue()三个方法，遍历数组的时候将滑动窗口（也即是当前队列）填满，并且找到其中最大值；然后弹出旧值，填入新值。可惜，没有getMaxValue()的方法。

解法中借用了单调队列的思想，即当前的滑动窗口中只维护有可能称为窗口中最大值的元素就可以了，同时保证窗口中的元素是有序的。

具体思想如下：

• 在单调队列中，若是要push的值val大于队尾的值，那么将队尾的数值弹出，直到队列为空或者队尾的值大于val，最后将val填入队尾。

• 在滑动窗口移动后，若是队首的值 == 移出滑动窗口范围的值（也就是上一个数组里标记的窗口范围中第一个值）需要将这个值弹出。

  • 为什么只需要做这个判断？

    因为每次窗口只向前移动一格，第一个值肯是第一个输入的，只可能在index = 0的地方。如果第一个值与移出滑动窗口范围的值不相等，则说明这个东西他不是该窗口中的最大值，被弹出了。(。・∀・)ノ

这样一来，借助单调队列的思想，滑动窗口移动过程中的最大值就是第一个元素！

tips：双端队列的常用操作：

// 声明双向队列
deque<int> q;

// 基本操作
q.front(); q.back();
q.push_front(); q.push_back();
q.pop_front(); q.pop_back();

前k个高频元素（347）

这一题因为讲到了对重复值统计的操作，所以考虑使用map这个数据结构。

然后是，需要输出前k个出现频率的元素，所以需要对统计的元素进行排序。如果直接对map中的元素进行排序的话，（比如使用快排）时间复杂度需要O(nlogn)。但是，题目要求的只是前k个频率的元素，所以只需要找到前k个就行，考虑使用优先级队列，也就是大根堆、小根堆这种数据结构。

对于堆这种数据结构，在遍历过程中进行pop操作时只能弹出堆顶的元素。故，采用小根堆的方式，将出现频率较小的元素弹出。