[TOC] # 棧 棧是一種特殊的受限線性表。 棧是限定只能在表的一端進行插入或刪除操作的線性表。LIFO 用 JavaScript 來模擬一個棧： ``` js class Stack { constructor () { this.stack = [] } push (item) { this.stack.push(item) } pop () { this.stack.pop() } peek () { return this.stack[this.getCount() - 1] } getCount () { return this.stack.length } empty () { return this.getCount() === 0 } } ``` ## 應用 使用棧進行括號匹配 [LeetCode](https://leetcode.com/problems/valid-parentheses/submissions/1) ``` javaScript /** * @param {string} s * @return {boolean} */ var isValid = function(s) { let map = { '(': -1, ')': 1, '[': -2, ']': 2, '{': -3, '}': 3 } let stack = [] for (let i = 0; i < s.length; i++) { if (map[s[i]] < 0) { stack.push(map[s[i]]) } else { if (map[s[i]] + stack.pop() !== 0) return false } } return stack.length === 0 ? true : false }; ``` # 隊列 隊列是一種特殊的受限線性表。 隊列是限定只能在表的一端進行插入操作，在另一端進行刪除操作的線性表。FIFO 用 JavaScript 模擬一個單鏈隊列 ``` js class Queue { constructor () { this.queue = [] } enQueue (item) { return this.queue.push(item) } deQueue() { this.queue.shift() } getHeader () { return this.queue[0] } getLength () { return this.queue.length } isEmpty () { return this.getLength() === 0 } } ``` 因為單鏈隊列在出隊操作的時候需要 O(n) 的時間復雜度，所以引入了循環隊列。循環隊列的出隊操作平均是 O(1) 的時間復雜度。 ``` javaScript class SqQueue { constructor(length) { this.queue = new Array(length + 1) // 隊頭 this.first = 0 // 隊尾 this.last = 0 // 當前隊列大小 this.size = 0 } enQueue(item) { // 判斷隊尾 + 1 是否為隊頭 // 如果是就代表需要擴容數組 // % this.queue.length 是為了防止數組越界 if (this.first === (this.last + 1) % this.queue.length) { this.resize(this.getLength() * 2 + 1) } this.queue[this.last] = item this.size++ this.last = (this.last + 1) % this.queue.length } deQueue() { if (this.isEmpty()) { throw Error('Queue is empty') } let r = this.queue[this.first] this.queue[this.first] = null this.first = (this.first + 1) % this.queue.length this.size-- // 判斷當前隊列大小是否過小 // 為了保證不浪費空間，在隊列空間等于總長度四分之一時 // 且不為 2 時縮小總長度為當前的一半 if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) { this.resize(this.getLength() / 2) } return r } getHeader() { if (this.isEmpty()) { throw Error('Queue is empty') } return this.queue[this.first] } getLength() { return this.queue.length - 1 } isEmpty() { return this.first === this.last } resize(length) { let q = new Array(length) for (let i = 0; i < length; i++) { q[i] = this.queue[(i + this.first) % this.queue.length] } this.queue = q this.first = 0 this.last = this.size } } ``` # 鏈表 鏈表是一個線性結構，同時也是一個天然的遞歸結構。鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。  用 JavaScript 模擬一個單向鏈表 ``` js class Node { constructor(v, next) { this.value = v this.next = next } } class LinkList { constructor() { // 鏈表長度 this.size = 0 // 虛擬頭部 this.dummyNode = new Node(null, null) } find(header, index, currentIndex) { if (index === currentIndex) return header return this.find(header.next, index, currentIndex + 1) } addNode(v, index) { this.checkIndex(index) // 當往鏈表末尾插入時，prev.next 為空 // 其他情況時，因為要插入節點，所以插入的節點 // 的 next 應該是 prev.next // 然后設置 prev.next 為插入的節點 let prev = this.find(this.dummyNode, index, 0) prev.next = new Node(v, prev.next) this.size++ return prev.next } insertNode(v, index) { return this.addNode(v, index) } addToFirst(v) { return this.addNode(v, 0) } addToLast(v) { return this.addNode(v, this.size) } removeNode(index, isLast) { this.checkIndex(index) index = isLast ? index - 1 : index let prev = this.find(this.dummyNode, index, 0) let node = prev.next prev.next = node.next node.next = null this.size-- return node } removeFirstNode() { return this.removeNode(0) } removeLastNode() { return this.removeNode(this.size, true) } checkIndex(index) { if (index < 0 || index > this.size) throw Error('Index error') } getNode(index) { this.checkIndex(index) if (this.isEmpty()) return return this.find(this.dummyNode, index, 0).next } isEmpty() { return this.size === 0 } getSize() { return this.size } } ``` ## 常見問題 1.反轉單向鏈表 ``` js /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let prev = null let curr = head /* ①判斷當前節點是否為空 ②不為空就獲取當前節點的下一節點 ③然后把當前節點的next設為上一個節點 ④然后把pre設為curr， curr設為next */ while (curr !== null) { let nextTemp = curr.next curr.next = prev prev = curr curr = nextTemp } return prev }; ``` 2.如何判斷一個鏈表是否存在環？ - hashmap 存儲節點 ID - 快慢指針 [參考答案](https://www.cnblogs.com/qingyunzong/p/9143321.html) # 樹 ## 二叉樹 樹擁有很多種結構，二叉樹是樹中最常用的結構，同時也是一個天然的遞歸結構。 二叉樹擁有一個根節點，每個節點至多擁有兩個子節點，分別為：左節點和右節點。樹的最底部節點稱之為葉節點。 滿二叉樹(full binary tree)：每一個結點或者是一個分支結點，并恰好有兩個非空子結點；或者是葉結點。 完全二叉樹(complete binary tree)：從根結點起每層從左到右填充。一棵高度為 d 的完全二叉樹除了 d-1 層外，每一層都是滿的。底層葉結點集中在左邊的若干位置上。 ## 遞歸方式遍歷二叉樹 ``` js function preorderTraversal (root) { if (root !== null) { visit(root) preorderTraversal(root.left) preorderTraversal(root.right) } } function middleTraversal (root) { if (root !== null) { middleTraversal(root.left) visit(root) middleTraversal(root.right) } } function postTraversal (root) { if (!root) { postTraversal(root.left) postTraversal(root.right) visit(root) } } ``` ## 非遞歸方式遍歷二叉樹 ``` js // 用 stack 模擬遞歸，用一個 result 數組存儲結點順序 function preorderTraversal (root) { if (root === null) return const result = [], stack = [] stack.push(root) while (stack.length !== 0) { let p = stack.pop() result.push(p.val) // 先放右邊再放左邊，因為棧的特性，后進先出，我們先拿左邊的就相當于先訪問左子樹了 if (p.right !== null) { stack.push(p.right) } if (p.left !== null) { stack.push(p.left) } } return result } // 中序遍歷：左根右，先把根和左邊的結點全部存入棧，再處理右邊的，右邊子樹也做相同處理 function middleTraversal (root) { if (root === null) return const result = [], stack = [] while (true) { while (root !== null) { stack.push(root) root = root.left } // 終止條件：最后樹遍歷完了就終止了 if (stack.length === 0) { break } let p = stack.pop() result.push(p.val) root = p.right } return result } // LRD function postTraversal (root) { if (root === null) return const result = [], stack = [] stack.push(root) while (stack.length !== 0) { let p = stack.pop() result.push(p.val) if (p.left !== null) { stack.push(p.left) } if (p.right !== null) { stack.push(p.right) } } return result.reverse() // 反轉過來恰好是后序遍歷...... } ```