## 一、棧 &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 等。