摘要：本文已同步到你可能知道的數(shù)據(jù)結(jié)構(gòu)與算法，歡迎。新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端就叫棧底。參考文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法描述

本文已同步到github 你可能知道的 javaScript 數(shù)據(jù)結(jié)構(gòu)與算法，歡迎Star。

如果想閱讀筆者更多文章，歡迎猛戳這里

關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法，終于抽時(shí)間把之前看過的這兩本書《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》、《數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述》，整理出來了一部分內(nèi)容，由于最近較忙，先把已整理出來的內(nèi)容發(fā)一下。對于未整理出來的內(nèi)容會在后續(xù)整理出來，并更新到此文，也會隨著對數(shù)據(jù)結(jié)構(gòu)與算法不斷的學(xué)習(xí)，不斷優(yōu)化更新此文，感興趣的小伙伴可以先收藏哦。這兩本書對前端來講是很好的入門數(shù)據(jù)結(jié)構(gòu)與算法的書，個(gè)人感覺《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》這本書從排版以及思路上更清晰一些。

另外，為了截圖和驗(yàn)證方便，本文的例子大多是書中的例子。

本文較長，如果閱讀起來不方便，可鏈接到我的github中，多帶帶查看。

閑言少敘，直接開始了

棧是一種遵從后進(jìn)先出LIFO（Last In First Out，后進(jìn)先出）原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端就叫棧底。

定義一個(gè)棧的類，并為該棧聲明一些方法，存儲數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)使用數(shù)組

class Stack {
    constructor() {
        this.dataStore = []
    }

    // 向棧中添加一個(gè)或多個(gè)元素到棧頂
    push() {
        for (let i = 0; i < arguments.length; i++) {
            this.dataStore.push(arguments[i])
        }
    }

    // 移出棧頂元素，并返回被移出的元素
    pop() {
        return this.dataStore.pop()
    }

    // 返回棧頂元素，不對棧做修改
    peek() {
        return this.dataStore[this.dataStore.length - 1]
    }

    // 判斷棧是否為空，如果為空返回true，否則返回false
    isEmpty() {
        return this.dataStore.length === 0
    }

    // 清空棧
    clear() {
        this.dataStore = []
    }

    // 返回棧中元素的個(gè)數(shù)

    size() {
        return this.dataStore.length
    }
}

// 棧的操作

let stack = new Stack()

stack.push(1, 2, 3)
console.log(stack.dataStore) // [1, 2, 3]
console.log(stack.pop())     // 3
console.log(stack.dataStore) // [1, 2]
console.log(stack.peek())    // 2
console.log(stack.dataStore) // [1, 2]
console.log(stack.size())    // 2
console.log(stack.isEmpty()) // false
stack.clear()
console.log(stack.dataStore)  // []
console.log(stack.isEmpty())  // true
console.log(stack.size())     // 0

棧的應(yīng)用

本文舉書中一個(gè)進(jìn)制轉(zhuǎn)換的例子并稍作修改,棧的類還是使用上面定義的Stack

function transformBase(target, base) {
    let quotient;                    // 商
    let remainder;                   // 余數(shù)
    let binaryStr = "";              // 轉(zhuǎn)換后的值
    let digits = "0123456789ABCDEF"  // 對轉(zhuǎn)換為16進(jìn)制數(shù)做處理
    let stack = new Stack()
    while(target > 0) {
        remainder = target % base
        stack.dataStore.push(remainder)
        target = Math.floor(target / base)
    }

    while(!stack.isEmpty()) {
        binaryStr += digits[stack.dataStore.pop()].toString()
    }

    return binaryStr
}

console.log(transformBase(10, 2))   // 1010
console.log(transformBase(10, 8))   // 12
console.log(transformBase(10, 16))  // A

隊(duì)列是遵循FIFO（First In First Out，先進(jìn)先出，也稱為先來先服務(wù)）原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。

其實(shí)隊(duì)列和棧類似，只是原則不同，隊(duì)列是先進(jìn)先出，用代碼來實(shí)現(xiàn)一個(gè)隊(duì)列及操作隊(duì)列的一些方法，以下用代碼實(shí)現(xiàn)一個(gè)隊(duì)列的類, 測試和棧類似，就不做具體測試了。

class Queue {
    constructor() {
        this.dataStore = []
    }

    // 入隊(duì)
    enqueue() {
        for (let i = 0; i < arguments.length; i++) {
            this.dataStore.push(arguments[i])
        }
    }

    // 出隊(duì)
    dequeue() {
        return this.dataStore.shift()
    }

    // 返回隊(duì)列第一個(gè)元素，不改變隊(duì)列
    front() {
        return this.dataStore[0]
    }

    // 隊(duì)列是否為空
    isEmpty() {
        return this.dataStore.length === 0
    }

    // 返回隊(duì)列的的元素個(gè)數(shù)
    size() {
        return this.dataStore.length
    }
}

隊(duì)列中在生活中有著大量應(yīng)用，如登機(jī)時(shí)，商務(wù)艙要優(yōu)于經(jīng)濟(jì)艙，這時(shí)候可以給隊(duì)列中的元素設(shè)置優(yōu)先級，下面用代碼來實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列的類

class PriorityQueue {

    constructor() {
        this.dataStore = []
    }

    isEmpty() {
        return this.dataStore.length === 0
    }

    enqueue(element, priority) {

        function QueueElement(element, priority) {
            this.element = element
            this.priority = priority
        }
        // 定義每次往隊(duì)列里添加的元素
        let queueElement = new QueueElement(element, priority)

        if (this.isEmpty()) {
            // 如果每次隊(duì)列為空直接添加到隊(duì)列中
            this.dataStore.push(queueElement)
        } else {
            // 定一個(gè)是否被添加到隊(duì)列的標(biāo)志
            let isAdded = false
            for (let i = 0; i < this.dataStore.length; i++) {
                if (queueElement.priority < this.dataStore[i].priority) {
                    // 優(yōu)先級數(shù)值越小，代表優(yōu)先級越高
                    this.dataStore.splice(i, 0, queueElement)
                    isAdded = true
                    break;
                }
            }

            if (!isAdded) {
                // 如果被添加的新元素優(yōu)先級最低，添加到隊(duì)尾
                this.dataStore.push(queueElement)
            }
        }
    }
    //
}

let priorityQueue = new PriorityQueue()

priorityQueue.enqueue("a", 5)
priorityQueue.enqueue("b", 2)
priorityQueue.enqueue("c", 3)

console.log(priorityQueue.dataStore)

最后的隊(duì)列如下圖：

直接上代碼:

class LinkedList {
    constructor() {
        this.head = null // 鏈表的第一個(gè)元素
        this.length = 0
    }
    // 向鏈表尾部添加一個(gè)新元素
    append(element) {
        let Node = function(element) {
            this.element = element
            this.next = null
        }
        let node = new Node(element)
        let currentNode;
        if (this.head == null) {
            // 如果鏈表head為null，表示鏈表無元素，直接把node賦值給head即可
            this.head = node
        } else {
            currentNode = this.head
            while (currentNode.next) {
                // 每次循環(huán)會進(jìn)行到鏈表的倒數(shù)第一個(gè)元素，把currentNode設(shè)置為倒數(shù)第一個(gè)元素
                currentNode = currentNode.next
            }
            // 把新增的node賦值給currentNode的next屬性，最后一個(gè)元素的next永遠(yuǎn)為null
            currentNode.next = node
        }
        // 鏈表的元素個(gè)數(shù)每次append后 +1
        this.length++
    }
    // 從鏈表中按位置刪除元素
    removeAt(position) {
        // position表示要移除元素的位置
        let index = 0
        let previous = null
        let currentNode = this.head
        if (position >= 0 && position < this.length) {
            while (index < position) {
                // 主要是找出position位置的元素，設(shè)置為currentNode
                previous = currentNode
                currentNode = currentNode.next
                index++
            }
            // 把currentNode的上一個(gè)元素的next指向currentNode的下一個(gè)元素，就對應(yīng)刪除了currentNode
            previous.next = currentNode.next
        } else {
            // 表示鏈表中不存在這個(gè)元素，直接return null
            return null
        }
        // 刪除后鏈表的元素個(gè)數(shù)每次刪除減1
        this.length--;
        // 返回刪除的元素
        return currentNode
    }
    // 按元素值刪除元素
    remove(element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }
    // 向鏈表中插入新元素
    insert(element, position) {
        // element表示被插入元素的具體值
        // position表示被插入元素的位置
        if (position >= 0 && position < this.length) {
            let index = 0
            let previous = null
            let currentNode = this.head
            let Node = function(element) {
                this.element = element
                this.next = null
            }
            let node = new Node(element)
            while (index < position) {
                previous = currentNode
                currentNode = currentNode.next
                index++
            }
            // 把當(dāng)前元素的上一個(gè)元素的next設(shè)置為被插入的元素
            previous.next = node
            // 把被插入元素的next設(shè)置為當(dāng)前元素
            node.next = currentNode
            // 鏈表元素個(gè)數(shù)加1
            this.length++;
            // 如果插入元素成功，返回true
            return true
        } else {
            // 如果找不到插入元素位置，返回false
            return false
        }
    }
    // 查找元素在鏈表中的位置
    indexOf(element) {
        let currentNode = this.head
        let index = 0
        // 如果currentNode也就是head為空，則鏈表為空不會進(jìn)入while循環(huán)，直接返回 -1
        while (currentNode) {
            if (element === currentNode.element) {
                // 如果被找到，返回當(dāng)前index
                return index
            }
            // 每一輪循環(huán)如果被查找元素還沒有被找到，index后移一位，currentNode指向后一位元素，繼續(xù)循環(huán)
            index++
            currentNode = currentNode.next
        }
        // 如果一直while循環(huán)結(jié)束都沒找到返回 -1
        return -1
    }
    // 鏈表是否為空
    isEmpty() {
        return this.length === 0
    }
    // 鏈表元素個(gè)數(shù)
    size() {
        return this.length
    }
}

let linkedList = new LinkedList()

linkedList.append("a")
linkedList.append("b")
linkedList.append("c")
linkedList.append("d")
linkedList.removeAt(2)
linkedList.insert("e", 2)
console.log("bIndex", linkedList.indexOf("b"))
console.log("fIndex", linkedList.indexOf("f"))
linkedList.remove("d")
console.log(linkedList)

上述代碼測試結(jié)果如下圖所示:

class Set {
    constructor() {
        this.items = {}
    }

    has(val) {
        return val in this.items
    }

    // 向集合中添加一個(gè)新的項(xiàng)
    add(val) {
        this.items[val] = val
    }

    // 從集合中移除指定項(xiàng)
    remove(val) {
        if (val in this.items) {
            delete this.items[val]
            return true
        }
        return false
    }

    // 清空集合
    clear() {
        this.items = {}
    }

    // 返回集合中有多少項(xiàng)
    size() {
        return Object.keys(this.items).length
    }

    // 提取items對象的所有屬性，以數(shù)組的形式返回
    values() {
        return Object.keys(this.items)
    }

    // 取當(dāng)前集合與其他元素的并集
    union(otherSet) {
        let unionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            unionSet.add(values[i])
        }

        let valuesOther = otherSet.values()
        for (let i = 0; i < valuesOther.length; i++) {
            unionSet.add(valuesOther[i])
        }
        return unionSet
    }

    // 取當(dāng)前集合與其他元素的交集
    intersection(otherSet) {
        let intersectionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            if (otherSet.has(values[i])) {
                intersectionSet.add(values[i])
            }
        }
        return intersectionSet
    }

    // 取當(dāng)前集合與其他元素的差集
    diff(otherSet) {
        let intersectionSet = new Set()
        let values = this.values()
        for (let i = 0; i < values.length; i++) {
            if (!otherSet.has(values[i])) {
                intersectionSet.add(values[i])
            }
        }
        return intersectionSet
    }

    // 判斷當(dāng)前集合是否是其他集合的子集
    isSubSet(otherSet) {
        // 如果當(dāng)前集合項(xiàng)的個(gè)數(shù)大于被比較的otherSet的項(xiàng)的個(gè)數(shù)，則可判斷當(dāng)前集合不是被比較的otherSet的子集
        if (this.size() > otherSet.size()) {
            return false
        } else {
            let values = this.values()
            for (let i = 0; i < values.length; i++) {
                // 只要當(dāng)前集合有一項(xiàng)不在otherSet中，則返回false
                if (!otherSet.has(values[i])) {
                    return false
                }
            }
            // 循環(huán)判斷之后，當(dāng)前集合每一項(xiàng)都在otherSet中，則返回true
            return true
        }
    }
}

// 測試
let setA = new Set()
setA.add("a")
setA.add("b")
setA.add("c")
setA.remove("b")
console.log(setA.values()) // ["a", "c"]
console.log(setA.size()) // 2

let setB = new Set()
setB.add("c")
setB.add("d")
setB.add("e")

let unionAB = setA.union(setB)
console.log(unionAB.values()) // ["a", "c", "d", "e"]
let intersectionAB = setA.intersection(setB)
console.log(intersectionAB.values()) // ["c"]

let diffAB = setA.diff(setB)
console.log(diffAB.values()) // ["a"]

let setC = new Set()
setC.add("d")
setC.add("e")

let isSubSetCB = setC.isSubSet(setB)
console.log(isSubSetCB) // true

let isSubSetAB = setA.isSubSet(setB)
console.log(isSubSetAB) // false

一個(gè)樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)（除了頂部的第一個(gè)節(jié)點(diǎn)）以及零個(gè)或多個(gè)子節(jié)點(diǎn)

// 創(chuàng)建一個(gè)鍵
function createNode(key) {
    this.key = key
    this.left = null
    this.right = null
}

// 向樹中插入鍵
function insertNode(node, newNode) {
    if (newNode.key < node.key) {
        if (node.left === null) {
            node.left = newNode
        } else {
            insertNode(node.left, newNode)
        }
    } else {
        if (node.right === null) {
            node.right = newNode
        } else {
            insertNode(node.right, newNode)
        }
    }
}

// 遍歷回調(diào)
function printNode(value) {
    console.log(value)
}

// 中序遍歷
function inOrderTraverseNode(node, callback) {
    if (node !== null) {
        inOrderTraverseNode(node.left, callback)
        callback(node.key)
        // debugger 可以加入debugger，用瀏覽器控制觀察Call Stack(執(zhí)行環(huán)境棧)來分析程序執(zhí)行過程
        inOrderTraverseNode(node.right, callback)
    }
}

// 先序遍歷
function prevOrderTraverseNode(node, callback) {
    if (node !== null) {
        // 先訪問節(jié)點(diǎn)本身
        callback(node.key)
        // 再訪問左側(cè)節(jié)點(diǎn)
        prevOrderTraverseNode(node.left, callback)
        // 然后再訪問右側(cè)節(jié)點(diǎn)
        prevOrderTraverseNode(node.right, callback)
    }
}

// 后序遍歷
function postOrderTraverseNode(node, callback) {
    if (node !== null) {
        // 先訪問左側(cè)節(jié)點(diǎn)
        postOrderTraverseNode(node.left, callback)
        // 再訪問右側(cè)節(jié)點(diǎn)
        postOrderTraverseNode(node.right, callback)
        // 然后再訪問節(jié)點(diǎn)本身
        callback(node.key)
    }
}

class BinarySearchTree {
    constructor() {
        this.key = null
    }
    insert(key) {
        let newNode = new createNode(key)
        if (this.key === null) {
            this.key = newNode
        } else {
            insertNode(this.key, newNode)
        }
    }
    // 中序遍歷訪問節(jié)點(diǎn)(結(jié)果為按值由小到大訪問)
    inOrderTraverse(callback) {
        inOrderTraverseNode(this.key, callback)
    }
    // 先序遍歷訪問節(jié)點(diǎn)(結(jié)果為先訪問節(jié)點(diǎn)本身，再左側(cè)節(jié)點(diǎn)，然后再訪問右側(cè)節(jié)點(diǎn))
    prevOrderTraverse(callback) {
        prevOrderTraverseNode(this.key, callback)
    }
    // 后序遍歷訪問節(jié)點(diǎn)(結(jié)果為先訪問左側(cè)節(jié)點(diǎn)，再訪問右側(cè)節(jié)點(diǎn)，然后再訪問節(jié)點(diǎn)本身)
    postOrderTraverse(callback) {
        postOrderTraverseNode(this.key, callback)
    }
    // 查找樹中的最小值
    findMin(node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    // 查找樹中的最小值對應(yīng)的節(jié)點(diǎn)
    findMinNode(node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node
        }
        return null
    }

    // 查找樹中的最大值
    findMax(node) {
        if (node) {
            while(node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }

    // 查找樹中的特定值，如果存在返回true，否則返回false
    search(node, key) {
        if (node === null) {
            return false
        }

        if (key < node.key) {
            // 如果被查找的key小于節(jié)點(diǎn)值，從節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)繼續(xù)遞歸查找
            return this.search(node.left, key)
        } else if (key > node.key) {
            // 如果被查找的key大于節(jié)點(diǎn)值，從節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)繼續(xù)遞歸查找
            return this.search(node.right, key)
        } else {
            // 被查找的key等于node.key
            return true
        }
    }

    // 移除樹中的特定節(jié)點(diǎn)
    removeNode(node, key) {
        if (node === null) {
            return null
        }

        if (key < node.key) {
            node.left = this.removeNode(node.left, key)
        } else if (key > node.key) {
            node.right = this.removeNode(node.right, key)
        } else {
            // console.log(node)
            // 移除葉子節(jié)點(diǎn)(無左右節(jié)點(diǎn)的節(jié)點(diǎn))
            if (node.left === null && node.right === null) {
                node = null
                return node
            }

            // 移除只有一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)(只有左節(jié)點(diǎn)或只有右節(jié)點(diǎn))
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.left
                return node
            }

            // 移除有兩個(gè)節(jié)點(diǎn)(既有左節(jié)點(diǎn)又有右節(jié)點(diǎn))
            if (node.left && node.right) {
                // 1. 找到被移除節(jié)點(diǎn)的右節(jié)點(diǎn)下的最小節(jié)點(diǎn)，替換被移除的節(jié)點(diǎn)
                let minRightNode = this.findMinNode(node.right)
                // 2. 把被移除節(jié)點(diǎn)的key設(shè)置為 被移除節(jié)點(diǎn)的右節(jié)點(diǎn)下的最小節(jié)點(diǎn)的key
                node.key = minRightNode.key
                // 3. 移除找到的那個(gè)最小節(jié)點(diǎn)
                this.removeNode(node.right, node.key)
                // 4. 向被移除節(jié)點(diǎn)的父節(jié)點(diǎn)返回更新后節(jié)點(diǎn)的引用
                return node
            }
        }
    }
}

測試如下:

let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(6)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(20)
tree.insert(12)
tree.insert(14)
tree.insert(18)
tree.insert(25)

tree.inOrderTraverse(printNode)   // 3  5 6 7 8  9 10 11 12 13 14 15 18 20 25
tree.prevOrderTraverse(printNode) // 11 7 5 3 6  9 8  10 15 13 12 14 20 18 25
tree.postOrderTraverse(printNode) // 3  6 5 8 10 9 7  12 14 13 18 25 20 15 11

// tree.key為根節(jié)點(diǎn)，為了保持樹不同層的結(jié)構(gòu)一致，沒有使用root為屬性，使用了key
let minNodeVal = tree.findMin(tree.key)
console.log("minNodeVal", minNodeVal)

let maxNodeVal = tree.findMax(tree.key)
console.log("maxNodeVal", maxNodeVal)

let isHasNodeVal = tree.search(tree.key, 7)
console.log(isHasNodeVal)   // true

tree.removeNode(tree.key, 15)
console.log(tree) // 可以查看樹的結(jié)構(gòu)，15的這個(gè)節(jié)點(diǎn)的key已經(jīng)被替換為18，并且key為18的節(jié)點(diǎn)已經(jīng)被刪除

1. 中序遍歷

2. 先序遍歷

3. 后序遍歷

1. 移除以一個(gè)葉節(jié)點(diǎn)

2. 移除只有一個(gè)左側(cè)子節(jié)點(diǎn)或右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)

3. 移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)

冒泡排序的執(zhí)行過程

代碼如下:

let arr = [5, 4, 3, 2, 1]

// 交換元素的位置
function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1)
            }
        }
    }
}

bubbleSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

選擇排序的執(zhí)行過程

代碼如下:

let arr = [5, 4, 3, 2, 1]

function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function changeSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i
        for (let j = i; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j
            }
        }

        if (i !== minIndex) {
            swap(arr, i, minIndex)
        }
    }
}

changeSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

插入排序的執(zhí)行過程

代碼如下:

let arr = [5, 4, 3, 2, 1]

function swap(arr, index1, index2) {
    var temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
}

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let j = i
        let temp = arr[i]
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
}

insertSort(arr)
console.log(arr)  // [1, 2, 3, 4, 5]

由于功力有限，本文有錯(cuò)誤和不合理的地方，歡迎各位大神多多指正，非常感謝。

參考文章：

學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法
數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述