栈

概念

• 栈是一个线性结构，在计算机中是⼀个相当常⻅的数据结构。
• 栈的特点是只能在某⼀端添加或删除数据，遵循先进后出的原则

实现

每种数据结构都可以⽤很多种⽅式来实现，其实可以把栈看成是数组的⼀个⼦集，所以这⾥使⽤数组来实现

class Stack() {
    constructor() {
        this.stk = []
    }
    //插入一个元素
    push(item) {
        this.stk.push(item)
    }
    //弹出栈顶元素
    pop() {
        this.stk.pop()
    }
    //统计栈内元素个数
    getCount() {
        return this.stk.length
    }
    //返回栈顶元素
    peek() {
        return this.stk[this.getCount() - 1]
    }
    //判断栈是否为空
    isEmpty() {
        return this.getCount() === 0
    }
}

队列

概念

队列是⼀个线性结构，特点是在某⼀端添加数据，在另⼀端删除数据，遵循先进先出的原则

实现

这⾥会讲解两种实现队列的⽅式，分别是单链队列和循环队列

• 单链队列

class Queue {
    constructor() {
        this.queue = [] 
    }
    //队尾插入一个元素
    enQueue(item) {
        this.queue.push(item) 
    }
    //队头弹出一个元素
    deQueue() {
        return this.queue.shift()
    }
    //返回队头元素
    getHeader() {
        return this.queue[0] 
    }
    //统计队列里的元素个数
    getLength() {
        return this.queue.length 
    }
    //判断队列是否为空
    isEmpty() {
        return this.getLength() === 0 
    }
}

因为单链队列在出队操作的时候需要 $O(n)$ 的时间复杂度，所以引⼊了循环队列。循环队列的出队操作平均是 $O(1)$的时间复杂度
- 循环队列

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) {
            //模仿Java中ArrayList的扩容机制
            this.resize(this.getLength()  + this.getLength() >> 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
    }
}

链表

概念

链表是⼀个线性结构，同时也是⼀个天然的递归结构。链表结构可以充分利⽤ 计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销⽐较⼤

实现

• 单向链表

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() {
        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
    }
    向第index个元素后面插入一个元素
    insertNode(v, index) {
        return this.addNode(v, index)
    }
    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
    }
    isEmpty() {
        return this.size === 0
    }
    getSize() {
        return this.size
    }
}

树

二叉树

• 树拥有很多种结构，⼆叉树是树中最常⽤的结构，同时也是⼀个天然的递归结构。
• ⼆叉树拥有⼀个根节点，每个节点⾄多拥有两个⼦节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当⼀颗树的叶数量数量为满时，该树可以称之为满⼆叉树

二叉搜索树

• ⼆分搜索树也是⼆叉树，拥有⼆叉树的特性。但是区别在于⼆分搜索树每个节点的值都⽐ 他的左⼦树的值⼤，⽐右⼦树的值⼩
• 这种存储⽅式很适合于数据搜索。因为当需要查找的时候，因为需要查找的值⽐根节点的值⼤或小，所以只需要在根节点的右或左⼦树上寻找，⼤⼤提⾼了搜索效率

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}

class BST {
    constructor() {
        this.root = null
        this.size = 0
    }
    getSize() {
        return this.size
    }
    isEmpty() {
        return this.size === 0
    }
    addNode(v) {
        this.root = this._addChild(this.root, v)
    }
    // 添加节点时，需要⽐较添加的节点值和当前节点值的⼤⼩
    _addChild() {
        if (!node) {
            this.size++
            return new Node(v)
        }
        if (node.value > v) {
            node.left = this._addChild(node.left, v)
        } else if (node.value < v) {
            node.right = this._addChild(node.right, v)
        } 
        return node
    }
}

堆

概念

• 堆通常是⼀个可以被看做⼀棵树的数组对象。
• 堆的实现通过构造⼆叉堆，实为⼆叉树的⼀种。这种数据结构具有以下性质。
• 任意节点⼩于（或⼤于）它的所有⼦节点 堆总是⼀棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填⼊。
• 将根节点最⼤的堆叫做最⼤堆或⼤根堆，根节点最⼩的堆叫做最⼩堆或⼩根堆。
• 优先队列也完全可以⽤堆来实现，操作是⼀模⼀样的。

实现大根堆

堆的每个节点的左边⼦节点索引是 $i * 2 + 1$ ，右边是 $i * 2 + 2$ ，⽗节点是 $(i - 1) /2$ 。

• 堆有两个核⼼的操作，分别是 $shiftUp$ 和 $shiftDown$ 。前者⽤于添加元素，后者⽤于删除根节点。
• $shiftUp$ 的核⼼思路是⼀路将节点与⽗节点对⽐⼤⼩，如果⽐⽗节点⼤，就和⽗节点交换位置。
• $shiftDown$ 的核⼼思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断⽗节点和两个⼦节点的⼤⼩，如果⼦节点⼤，就把最⼤的⼦节点和⽗节点交换

class MaxHeap {
    constructor() {
        this.heap = []
    }
    size() {
        return this.heap.length
    }
    isEmpty() {
        return this.size() == 0
    }
    add(item) {
        this.heap.push(item)
        this._shiftUp(this.size() - 1)
    }
    removeMax() {
        this._shiftDown(0)
    }
    //父节点下标
    getParentIndex(k) {
        return parseInt((k - 1) / 2)
    }
    //左子树下标,右子树加1即可
    getLeftIndex(k) {
        return k * 2 + 1
    }
    //交换两个节点
    _swap(left, right) {
        let rightValue = this.heap[right]
        this.heap[right] = this.heap[left]
        this.heap[left] = rightValue
    }
    //核心操作
    _shiftUp(k) {
        // 如果当前节点⽐⽗节点⼤，就交换
        while (this.heap[k] > this.heap[this.getParentIndex(k)]) {
            this._swap(k, this.getParentIndex(k))
            // 将索引变成⽗节点
            k = this.getParentIndex(k)
        }
    }
    //核心操作
    _shiftDown(k) {
        // 交换⾸位并删除末尾
        this._swap(k, this.size() - 1)
        this.heap.splice(this.size() - 1, 1)
        // 判断节点是否有左孩⼦，因为⼆叉堆的特性，有右必有左
        while (this.getLeftIndex(k) < this.size()) {
            let j = this.getLeftIndex(k)
            // 判断是否有右孩⼦，并且右孩⼦是否⼤于左孩⼦
            if (j + 1 < this.size() && this.heap[j + 1] > this.heap[j]) j++
            // 判断⽗节点是否已经⽐⼦节点都⼤
            if (this.heap[k] >= this.heap[j]) break
            this._swap(k, j)
            k = j
        }    
    }
}