Shouyu

Appearance

代码随想录 栈与队列：总结 ​

栈与队列理论基础 ​

理解四个问题：

  1. C++中stack，queue 是容器么？
  2. 我们使用的stack，queue是属于那个版本的STL？
  3. 我们使用的STL中stack，queue是如何实现的？
  4. stack，queue 提供迭代器来遍历空间么？

stack 是一个很熟悉的数据结构，但是在熟悉的编程语言中，它们的底层实现并不清楚。可以出一道面试题，

例如：

C++中 stack 的元素在内存中是连续分布的吗？

或者问：

C++中的STL stack 的底层实现是什么？

理解这道题目，我们就需要知道，栈是容器适配器，底层容器使用的不同容器，导致栈内的数据在内存中不一定是连续分配的。在默认情况下，C++ 里面的 stack 默认使用的是 deque，双端队列。那么 deque 在内存中的数据分布是什么样的呢？实际上是不连续的。

拓展：

  • 如果底层容器是 std::deque (默认)，那么元素在内存中不保证连续。

  • 如果底层容器是 std::vector，那么元素在内存中是连续的。

  • 如果底层容器是 std::list，那么元素在内存中是非连续的，因为 std::list 是链表结构。

为什么 deque 在内存中不保证连续，是因为 deque 作为双端队列，它在队头和队尾都支持快速插入和删除的操作，都是 O(1) 的时间复杂度，因此必须是非连续内存。

栈在系统中的应用 ​

其实，栈在系统中的应用有非常非常多。

  1. 函数的调用和递归，然后是表达式求值。
  2. 在编译器中，栈常用于将中缀表达式转换为后缀表达式，也就是逆波兰表达式。
  3. 栈还有语法解析、编译器、解释器的功能，使用栈来处理语法结构。例如括号匹配、标签匹配等。每当遇到一个开括号，就将其压入栈中；遇到闭括号时，就检查栈顶是否是对应的开括号。
  4. 撤销/重做 (Undo/Redo) 功能。在文本编辑器、图像处理软件等应用中，撤销和重做功能通常通过两个栈来实现：操作栈：记录用户执行的操作。每次操作都压入栈。撤销栈：当用户执行撤销操作时，被撤销的操作会从操作栈弹出并压入撤销栈。当用户执行重做操作时，被重做的操作会从撤销栈弹出并压入操作栈。
  5. 浏览器前进后退。一个栈用于存储用户访问过的页面（后退栈），另一个栈用于存储用户从后退栈中弹出的页面（前进栈）。
  6. 遍历图或树结构。

在记录一系列操作或者状态的时候，可以使用 栈。处理表达式或语法。

栈经典题目 ​

括号匹配问题 ​

括号匹配问题是使用栈解决的经典问题。

有效的括号 中有三种不匹配的情况。左括号多余、右括号多余，或者没有多余但类型不匹配，这三种情况。以及在匹配左括号的时候，可以让对应的右括号入栈。最后只需要比较当前元素和栈顶元素是否相等，这样就可以了，比左括号入栈要简单得多。

字符串去重 ​

删除字符串中所有相邻重复项 相邻的重复项需要我们对字符串连着的两个元素进行判断，本质上也是两个元素的匹配问题，因而可以使用栈。

思路就是把字符串按照顺序放到栈中，遇到匹配的元素栈顶就弹出。这样的话，栈里面剩下的就都是不匹配的元素了。

逆波兰表达式 ​

逆波澜表达式实际上是计算机处理表达式的原理。拿到两个操作对象，然后匹配到运算符的话，就进行计算。这样消耗掉两个操作对象，然后就又拿到一个操作对象。

队列经典题目 ​

滑动窗口最大值 ​

这道题的主要思想是：我们是要找滑动窗口里面的最大值，但问题是在滑动窗口里面线性查找的时间复杂度是比较高的。

所以说，滑动窗口可以使用队列来维护。队列是一个单调队列，队列元素从大到小排列。队列的队头一个元素是窗口里面的最大值。这样就可以以 O(1) 的时间复杂度取到这个滑动窗口里的最大值了。

但是，对于队列来说，移动窗口时需要移除的元素可能并不在队列的头部。这样，获取最大值的时间复杂度是降低了，但是移动窗口的时候移除元素又变得很麻烦。

为了解决这个问题，实际上主要思想就是队列里面没必要把窗口的所有元素都放进去，只需要维护那些当前及往后移动以后有可能成为窗口最大值的元素就行了。为了实现这个功能，我们需要保持两个规则。

  1. push(value)：如果移动窗口时添加的元素大于队列末尾元素的数值，那么就将这个队列的末尾元素弹出。直到添加的元素数值小于等于队列末尾的元素为止。这就好像添加的元素把移动窗口里面比它小的数全部吃掉一样。

  2. pop(value)： 如果移动窗口时，需要移除的元素等于队列的队头元素，那么直接弹出元素。 如果移动窗口时移除的元素小于队列的队头元素，那么不用任何操作，这个数在 push 的时候已经被移除了。

这道题单调队列是自己实现的，并未传统的队列（std::queue）。单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。

求前K个高频元素 ​

这道题引出了优先级队列，什么是优先级队列呢？

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

堆里的元素有顺序的，取出和添加时间复杂度都是 O(nlogn)

本题就要使用优先级队列来对部分频率进行排序。 注意这里是对部分数据进行排序而不需要对所有数据排序！

所以排序的过程的时间复杂度是 O(log⁡k) ，整个算法的时间复杂度是 O(nlog⁡k) 。

总结 ​

用栈实现队列，用队列实现栈考验 stack 和 que 的基础实现

通过括号匹配问题、字符串取出相邻重复项、逆波兰表达式讲了栈的应用。这三个都是一个匹配问题，消除匹配项。

通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。