栈和队列的理论基础

àì夳堔傛蜴生んèń 2023-10-14 08:42 23阅读 0赞

### 栈和队列的理论基础 ###

*  面试题
 *  栈经典题目
 *   *  1. 括号匹配问题
     *   *  三种不匹配的情况
         *  技巧
     *  2. 字符串去重问题
     *  3. 逆波兰表达式问题
 *  队列经典题目
 *   *  1. 滑动窗口最大值问题
     *   *  单调队列
     *  2. 求前k个高频元素
     *   *  优先级队列
         *   *  优先级队列中的排列原则
             *  什么是堆
 *  总结

# 面试题 #

栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

1.  陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
2.  陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。

一个队列在**模拟栈**弹出元素的时候只要将队列**头部的元素**（除了最后一个元素外） **重新添加到队列尾部**，此时在去弹出元素就是栈的顺序了。

# 栈经典题目 #

## 1. 括号匹配问题 ##

### 三种不匹配的情况 ###

1.  第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
2.  第二种情况，括号没有多余，但是括号的类型没有匹配上。
3.  第三种情况，字符串里右方向的括号多余了，所以不匹配。

### 技巧 ###

这里还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

## 2. 字符串去重问题 ##

思路就是可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。

## 3. 逆波兰表达式问题 ##

和相邻字符串消除类似。

# 队列经典题目 #

## 1. 滑动窗口最大值问题 ##

使用**单调队列**来解决。

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

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

### 单调队列 ###

设计单调队列的时候，pop和push操作要保持如下规则：

1.  pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
2.  push(value)：如果push的元素value大于入口元素的数值，那么就将队列出口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

一些同学还会对单调队列都有一些困惑，首先要明确的是，题解中单调队列里的**pop和push接口**，**仅适用于本题**。

## 2. 求前k个高频元素 ##

通过求前 K 个高频元素，引出另一种队列就是**优先级队列**。本题就要使用优先级队列来对部分频率进行排序。

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

### 优先级队列 ###

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

#### 优先级队列中的排列原则 ####

优先级队列内部元素是自动依照元素的权值排列。

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

#### 什么是堆 ####

堆是一棵**完全二叉树**，树中每个结点的值都不小于（或不大于）其左右孩子的值。

如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

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

# 总结 #

我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。

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

**参考资料**：[栈与队列的理论基础][Link 1]

[Link 1]: https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html#%E6%A0%88%E5%9C%A8%E7%B3%BB%E7%BB%9F%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8