2、栈、队列、散列表和位运算
最后更新于：2022-04-02 06:11:17
## 一、栈
栈（stack）是一种操作受限的线性表数据结构，基于后进先出（LIFO）策略的集合类型，例如函数中的临时变量符合后进先出的特性，因此用栈保存最合适。
在入栈和出栈过程中所需的空间复杂度是 O(1)，时间复杂度也是 O(1)。空间复杂度是指运行算法还需要的额外存储空间。
注意，内存中的堆栈和数据结构中的堆栈不是一个概念，前者是真实存在的物理区，后者是抽象的数据存储结构。
面试题30[包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)。在压栈时，与之前的最小值比较，每次把两者较小的那个值存放到辅助栈中。
面试题31[栈的压入和弹出序列](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/)。如果弹出的数字是栈顶，则弹出；如果弹出的数字不在栈顶，则把还没入栈的数字压入到辅助栈中，直到栈顶是弹出数字为止。
**1）括号匹配**
用正确的类型和顺序匹配括号，例如“(”跟“)”匹配，“\[”跟“\]”匹配，“{”跟“}”匹配。例题：LeetCode的[20\. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)。
第一种思路是，当遇到匹配的最小括号对时，将它们从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是，[代码如下所示](https://codepen.io/strick/pen/RwrEWaP)。
~~~
function isValidParentheses(s) {
const length = s.length;
let i = 0;
const stack = [];
while (i < length) {
let stackLen = stack.length > 0 ? stack.length - 1 : stack.length;
if (
(stack[stackLen] == "(" && s[i] == ")") ||
(stack[stackLen] == "{" && s[i] == "}") ||
(stack[stackLen] == "[" && s[i] == "]")
) {
stack.pop();
i++;
continue;
}
stack.push(s[i]);
i++;
}
return stack.length === 0;
}
~~~
第二种思路是巧妙的利用一张映射表，以右括号为键，左括号为值。先判断当前字符是否是左括号，若是，就入栈，否则匹配当前栈顶元素是否与当前字符匹配。
~~~
function isValidParentheses(s) {
const stack = [],
map = { "}": "{", "]": "[", ")": "(" };
for (let i = 0, len = s.length; i < len; i++) {
let c = s[i];
if (!map[c]) {
stack.push(c);
continue;
}
if (stack.length > 0 && map[c] != stack.pop())
return false;
}
return stack.length == 0;
}
~~~
**2）算术表达式求值**
( 1 + ( 2 + 3 ) \* ( 4 \* 5 ) ) 是一个算术表达式，如果将4乘以5，把3加上2，取它们的积然后加1，就得到了101。
表达式由括号、运算符和操作数（数字）组成，可以用两个栈分别保存运算符和操作数来完成算术求值，处理过程如下所列。
（1）将操作数压入操作数栈；
（2）将运算符压入运算符栈；
（3）忽略左括号；
（4）在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
源码[如下所示](https://codepen.io/strick/pen/VweqvGe)。例题：LeetCode的[150\. 逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)。
~~~
function evalExpress(s) {
const length = s.length;
let i = 0;
const ops = [],
vals = [];
while (i < length) {
let word = s[i];
if (word == "(") {
} else if (word == "+" || word == "-" || word == "*" || word == "/")
ops.push(word);
else if (word == ")") {
let op = ops.pop(),
val = vals.pop();
if (op == "+") val = vals.pop() + val;
else if (op == "-") val = vals.pop() - val;
else if (op == "*") val = vals.pop() * val;
else if (op == "/") val = vals.pop() / val;
vals.push(val);
} else
vals.push(parseInt(word));
i++;
}
return vals.pop();
}
~~~
## 二、队列
队列（queue）也是一种操作受限的线性表数据结构，基于先进先出（FIFO）策略的集合类型，队列的应用非常广泛，例如循环队列、阻塞队列、并发队列等。
栈只需一个栈顶指针，而队列需要两个：队首指针和队尾指针。
面试题9[用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)。先进后出的栈实现先进先出的队列，一系列栈的压入和弹出模拟队列。
面试题59[窗口滑动的最大值](https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/)。只把可能成为滑动窗口最大值的数存入一个两端开口的队列（deque）。延伸题：[队列的最大值](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/)。
**1）循环队列**
循环队列是首尾相连的队列，这样可避免在出队时进行数据搬移的操作，但需要准确的判断出队空和队满，[如下所示](https://codepen.io/strick/pen/MWKZymb)。例题：LeetCode的[641\. 设计循环双端队列](https://leetcode-cn.com/problems/design-circular-deque/)。
~~~
class CircularQueue {
constructor(capacity) {
this.items = [];
this.n = capacity; //队列大小
this.head = 0; //队首指针
this.tail = 0; //队尾指针
}
enqueue(item) {
const { head, tail, n } = this;
//队满
if ((tail + 1) % n == head) return false;
this.items[tail] = item;
//队尾没有存储数据，会浪费一个数组的存储空间
this.tail = (tail + 1) % n;
return true;
}
dequeue() {
const { head, tail, n, items } = this;
//队空
if (head == tail) return null;
const result = items[head];
this.head = (head + 1) % n;
return result;
}
}
~~~
## 三、散列表
散列表（Hash Table）也叫哈希表，一种以空间换时间的方式，是数组的扩展，可根据键（Key）而直接访问内存储存位置的数据结构。
它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，提升查找速度。
这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数的特点如下：
（1）计算得到的结果是一个非负整数。
（2）如果 key1 = key2，那 hash(key1) == hash(key2)。
（3）如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
但即使是著名的MD5、SHA等散列算法，也不能避免散列冲突。当出现冲突时，可采用拉链法（Chaining）和线性探测法（Linear Probing）。
所以在散列表中查找数据，最好情况是 O(1)，最坏情况是 O(n)。
LeetCode的[242\. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/)，除了排序字符之外，还可用散列表记录字符出现的次数。
LeetCode的[1\. 两数之和](https://leetcode-cn.com/problems/two-sum/)，将数组放入一个散列表中，用总数减去遍历的值，判断差是否可在散列表中查到。复杂度升级后的例题：[15\. 三数之和](https://leetcode-cn.com/problems/3sum/)、[18\. 四数之和](https://leetcode-cn.com/problems/4sum/)。
## 四、位运算
位运算就是直接对整数在内存中的二进制进行操作。由于位运算不需要转成十进制，因此处理速度非常快。位运算的总结摘录于《[算法面试通关40讲](https://time.geekbang.org/course/intro/100019701)》。
XOR（异或）的特点如下：
~~~
x^0 = x
x^1s = ~x; //1s是一种全为1的数，即1s = ~0
x^(~x) = 1s;
x^x = 0;
a^b=c => a^c=b, b^c=a //swap
a^b^c = a^(b^c) = (a^b)^c
~~~
常用的位运算包括：
~~~
x&1 == 1 OR == 0 //判断奇偶（x%2==1）。
x = x&(x-1) //将最低位的 1 清零。
x & -x //得到最低位的 1。
~~~
更复杂的位运算包括：
~~~
x & (~0 << n) //将x最右边的n位清零
(x >> n) & 1 //获取x的第n位值（0或1）
x & (1 << (n-1)) //获取x的第n位的幂值
x | (1 << n) //仅将第n位置为1
x & (~(1 << n)) //仅将第n位置为0
x & ((1 << n) - 1) //将x最高位至第n位（含）清零
x & (~((1 << (n+1)) - 1)) //将第n位至第0位（含）清零
~~~
LeetCoded的[191\. 位1的个数](https://leetcode-cn.com/problems/number-of-1-bits/)，循环执行 x&(x-1)，并且记录循环次数，判断条件是x和0是否相同。
LeetCoded的[231\. 2的幂](https://leetcode-cn.com/problems/power-of-two/)，仍然使用 x&(x-1)，然后判断x是否等于0。
LeetCoded的[338\. 比特位计数](https://leetcode-cn.com/problems/counting-bits/)，使用递推公式 count\[i\] = count\[i&(i-1)\] + 1，只需一遍循环就能得出1的数量。
*****
> 原文出处：
[博客园-数据结构和算法躬行记](https://www.cnblogs.com/strick/category/1809992.html)
已建立一个微信前端交流群，如要进群，请先加微信号freedom20180706或扫描下面的二维码，请求中需注明“看云加群”，在通过请求后就会把你拉进来。还搜集整理了一套[面试资料](https://github.com/pwstrick/daily)，欢迎阅读。
';