## 一、栈 &emsp;&emsp;栈（stack）是一种操作受限的线性表数据结构，基于后进先出（LIFO）策略的集合类型，例如函数中的临时变量符合后进先出的特性，因此用栈保存最合适。 &emsp;&emsp;在入栈和出栈过程中所需的空间复杂度是 O(1)，时间复杂度也是 O(1)。空间复杂度是指运行算法还需要的额外存储空间。 &emsp;&emsp;注意，内存中的堆栈和数据结构中的堆栈不是一个概念，前者是真实存在的物理区，后者是抽象的数据存储结构。 &emsp;&emsp;面试题30[包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)。在压栈时，与之前的最小值比较，每次把两者较小的那个值存放到辅助栈中。 &emsp;&emsp;面试题31[栈的压入和弹出序列](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/)。如果弹出的数字是栈顶，则弹出；如果弹出的数字不在栈顶，则把还没入栈的数字压入到辅助栈中，直到栈顶是弹出数字为止。 **1）括号匹配** &emsp;&emsp;用正确的类型和顺序匹配括号，例如“(”跟“)”匹配，“\[”跟“\]”匹配，“{”跟“}”匹配。例题：LeetCode的[20\. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)。 &emsp;&emsp;第一种思路是，当遇到匹配的最小括号对时，将它们从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是，[代码如下所示](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; } ~~~ &emsp;&emsp;第二种思路是巧妙的利用一张映射表，以右括号为键，左括号为值。先判断当前字符是否是左括号，若是，就入栈，否则匹配当前栈顶元素是否与当前字符匹配。 ~~~ 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）算术表达式求值** &emsp;&emsp;( 1 + ( 2 + 3 ) \* ( 4 \* 5 ) ) 是一个算术表达式，如果将4乘以5，把3加上2，取它们的积然后加1，就得到了101。 &emsp;&emsp;表达式由括号、运算符和操作数（数字）组成，可以用两个栈分别保存运算符和操作数来完成算术求值，处理过程如下所列。 &emsp;&emsp;（1）将操作数压入操作数栈； &emsp;&emsp;（2）将运算符压入运算符栈； &emsp;&emsp;（3）忽略左括号； &emsp;&emsp;（4）在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。 &emsp;&emsp;源码[如下所示](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(); } ~~~ ## 二、队列 &emsp;&emsp;队列（queue）也是一种操作受限的线性表数据结构，基于先进先出（FIFO）策略的集合类型，队列的应用非常广泛，例如循环队列、阻塞队列、并发队列等。 &emsp;&emsp;栈只需一个栈顶指针，而队列需要两个：队首指针和队尾指针。 &emsp;&emsp;面试题9[用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)。先进后出的栈实现先进先出的队列，一系列栈的压入和弹出模拟队列。 &emsp;&emsp;面试题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）循环队列** &emsp;&emsp;循环队列是首尾相连的队列，这样可避免在出队时进行数据搬移的操作，但需要准确的判断出队空和队满，[如下所示](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; } } ~~~ ## 三、散列表 &emsp;&emsp;散列表（Hash Table）也叫哈希表，一种以空间换时间的方式，是数组的扩展，可根据键（Key）而直接访问内存储存位置的数据结构。 &emsp;&emsp;它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，提升查找速度。 &emsp;&emsp;这个映射函数称做散列函数，存放记录的数组称做散列表。 &emsp;&emsp;散列函数的特点如下： &emsp;&emsp;（1）计算得到的结果是一个非负整数。 &emsp;&emsp;（2）如果 key1 = key2，那 hash(key1) == hash(key2)。 &emsp;&emsp;（3）如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。 &emsp;&emsp;但即使是著名的MD5、SHA等散列算法，也不能避免散列冲突。当出现冲突时，可采用拉链法（Chaining）和线性探测法（Linear Probing）。 &emsp;&emsp;所以在散列表中查找数据，最好情况是 O(1)，最坏情况是 O(n)。 &emsp;&emsp;LeetCode的[242\. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/)，除了排序字符之外，还可用散列表记录字符出现的次数。 &emsp;&emsp;LeetCode的[1\. 两数之和](https://leetcode-cn.com/problems/two-sum/)，将数组放入一个散列表中，用总数减去遍历的值，判断差是否可在散列表中查到。复杂度升级后的例题：[15\. 三数之和](https://leetcode-cn.com/problems/3sum/)、[18\. 四数之和](https://leetcode-cn.com/problems/4sum/)。 ## 四、位运算 &emsp;&emsp;位运算就是直接对整数在内存中的二进制进行操作。由于位运算不需要转成十进制，因此处理速度非常快。位运算的总结摘录于《[算法面试通关40讲](https://time.geekbang.org/course/intro/100019701)》。 &emsp;&emsp;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 ~~~ &emsp;&emsp;常用的位运算包括： ~~~ x&1 == 1 OR == 0 //判断奇偶（x%2==1）。 x = x&(x-1) //将最低位的 1 清零。 x & -x //得到最低位的 1。 ~~~ &emsp;&emsp;更复杂的位运算包括： ~~~ 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位（含）清零 ~~~ &emsp;&emsp;LeetCoded的[191\. 位1的个数](https://leetcode-cn.com/problems/number-of-1-bits/)，循环执行 x&(x-1)，并且记录循环次数，判断条件是x和0是否相同。 &emsp;&emsp;LeetCoded的[231\. 2的幂](https://leetcode-cn.com/problems/power-of-two/)，仍然使用 x&(x-1)，然后判断x是否等于0。 &emsp;&emsp;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)，欢迎阅读。  推荐一款前端监控脚本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不仅能监控前端的错误、通信、打印等行为，还能计算各类性能参数，包括 FMP、LCP、FP 等。