JavaScript实现常见的数据结构

使用JavaScript实现栈、队列、链表、集合等常见数据结构。可能会有点用?

栈(Stack)

实际上JavaScript的Array本身就具有栈和队列的特性,所以我们可以借助Array来实现它们。

class Stack {
    constructor() {
        this.items = [];
    }
    get length() {
        return this.items.length;
    }
    // 获取栈顶元素
    get peek() {
        return this.items[this.items.length - 1];
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        this.items.pop();
    }
}

队列(Queue)

class Queue {
    constructor() {
        this.items = [];
    }
    get isEmpty() {
        return this.items.length === 0;
    }
    get length() {
        return this.items.length;
    }
    // 入队
    enqueue(element) {
        this.items.push(element);
    }
    // 出队
    dequeue() {
        return this.items.shift();
    }
}

优先队列

队列的升级版本,给每个元素一个优先级,入队时会先排序。这里PriorityQueue继承自Queue,所以只需要重写enqueue方法。

class PriorityQueue extends Queue {
    /**
     * 入队
     * @param {*} element 元素
     * @param {*} priority 优先级
     */
    enqueue(element, priority) {
        const queueElement = { element, priority };
        if (this.isEmpty) {
            super.enqueue(queueElement);
        } else {
            const preIndex = this.items.findIndex(items => queueElement.priority < items.priority);
            if (preIndex > -1) {
                this.items.splice(preIndex, 0, queueElement);
            } else {
                super.enqueue(queueElement);
            }
        }
    }
}

循环队列

循环队列可以想象为一个首尾相连的圆环,相较于普通队列,它更节省空间。

虽然同样继承自Queue,但基本上所有方法都重写了。

class LoopQueue extends Queue {
    constructor(maxSize) {
        super();
        this.maxSize = maxSize;
        this.head = -1; //头指针
        this.tail = -1; //尾指针
    }
    get isFull(){
        return (this.tail + 1) % this.maxSize === this.head;
    }
    get isEmpty(){
        return this.tail === -1 && this.head === -1;
    }
    enqueue(element) {
        if (this.isFull) {
            return false;
        }
        if (this.isEmpty) {
            this.head = 0;
        }
        this.tail = (this.tail + 1) % this.maxSize;
        this.items[this.tail] = element;
        return true;
    }
    dequeue(){
        if (!this.isEmpty) {
            if (this.tail === this.head) {
                this.tail = -1;
                this.head = -1;
            } else {
                this.head = (this.head + 1) % this.maxSize;
            }
            return true;
        }
        return false;
    }
}

链表(Linked List)

// 节点
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

// 链表
class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    // 追加
    append(element) {
        const node = new Node(element);
        let current = null;
        if (this.head === null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }
    /**
     * 插入
     * @param {*} element 元素
     * @param {*} position 位置
     */
    insert(element, position) {
        if (position >= 0 && position <= this.length) {
            const node = new Node(element);
            let current = this.head;
            let previous = null;
            if (position === 0) {
                this.head = node;
                this.head.next = current;
            } else {
                for (let index = 0; index < position; index++) {
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            this.length++;
            return true;
        }
        return false;
    }
    /**
     * 删除
     * @param {*} position 位置
     */
    removeAt(position) {
        if (position >= 0 && position < this.length) {
            let current = this.head;
            let previous = null;
            if (position === 0) {
                this.head = current.next;
            } else {
                for (let index = 0; index < position; index++) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length--;
            return current.element;
        }
        return null;
    }
    // 查找元素所在位置
    indexOf(element) {
        let current = this.head;
        let index = 0;
        while (current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }
    // 根据元素删除
    remove(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }
    toString() {
        let current = this.head;
        let string = '';
        while (current) {
            string += `${current.element} -- `;
            current = current.next;
        }
        string += '*';

        return string;
    }
}

集合(Set)

ES6中引入了集合类型,可以参考一下。

class Set {
    constructor() {
        this.items = {};
    }
    get size() {
        return Object.keys(this.items).length;
    }
    get values() {
        return Object.keys(this.items);
    }
    // 判断元素是否存在
    has(value) {
        return this.items.hasOwnProperty(value);
    }
    add(value) {
        if (!this.has(value)) {
            this.items[value] = value;
            return true;
        }
        return false;
    }
    remove(value) {
        if (this.has(value)) {
            delete this.items[value]
            return true;
        }
        return false;
    }
    // 并集
    union(otherSet) {
        const unionSet = new MySet();
        this.values.forEach((value) => unionSet.add(this.value));
        otherSet.values.forEach((value) => unionSet.add(otherSet.value));
        return unionSet;
    }
    // 交集
    intersection(otherSet) {
        const intersectionSet = new MySet();
        this.values.forEach((value, index) => {
            if (otherSet.has(value)) {
                intersectionSet.add(value);
            }
        });
        return intersectionSet;
    }
    // 差集
    difference(otherSet) {
        const differenceSet = new MySet();
        this.values.forEach((value) => {
            if (!otherSet.has(value)) {
                differenceSet.add(value);
            }
        });
        return differenceSet;
    }
    // 子集
    subset(otherSet) {
        return this.values.every((value) => otherSet.has(value));
    }
}

字典(Dictionary)

在JavaScript中,Object对象实际上就是字典,都是以{ key: value }的形式存储数据的。

class Dictionary {
    constructor() {
        this.items = {};
    }
    get keys() {
        return Object.keys(this.items);
    }
    get values() {
        const r = [];
        Object.keys(this.items).forEach((value) => {
            r.push(this.items[value]);
        });
        return r;
    }
    set(key, value) {
        this.items[key] = value;
    }
    get(key) {
        return this.items[key];
    }
    remove(key) {
        delete this.items[key];
    }
}

哈希表(Hash Table)

哈希表也是以键值对的形式存储数据的,但是因为每个数据都会根据key生成唯一的哈希值,所以查询速度非常快。

这里散列函数就是用来生成哈希值的,随便写的,常用的构造散列函数的方法在网上能查到很多。

class HashTable {
    constructor() {
        this.table = [];
    }
    // 散列函数
    getHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 64 * 0xffffff;
    }
    put(key, value) {
        const position = this.getHashCode(key);
        this.table[position] = value;
    }
    get(key) {
        return this.table[this.getHashCode(key)];
    }
    remove(key) {
        this.table[this.getHashCode(key)] = undefined;
    }
}

树(tree)

正常的二叉树没有必要实现,这里实现一下二叉搜索树。

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(data) {
        const newNode = new Node(data);
        const insertNode = (node, newNode) => {
            if (newNode.data < node.data) {
                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);
                }
            }
        }
        if (!this.root) {
            this.root = newNode;
        } else {
            insertNode(this.root, newNode);
        }
    }
    // 中序遍历
    inOrderTraverse(callback) {
        const inOrderTraverseNode = (node, callback) => {
            if (node !== null) {
                inOrderTraverseNode(node.left, callback);
                callback(node.data);
                inOrderTraverseNode(node.right, callback);
            }
        }
        inOrderTraverseNode(this.root, callback);
    }
    // 先序遍历
    preOrderTraverse(callback) {
        const preOrderTraverseNode = (node, callback) => {
            if (node !== null) {
                callback(node.data);
                preOrderTraverseNode(node.left, callback);
                preOrderTraverseNode(node.right, callback);
            }
        }
        preOrderTraverseNode(this.root, callback);
    }
    // 后序遍历
    postOrderTraverse(callback) {
        const postOrderTraverseNode = (node, callback) => {
            if (node !== null) {
                postOrderTraverseNode(node.left, callback);
                postOrderTraverseNode(node.right, callback);
                callback(node.data);
            }
        }
        postOrderTraverseNode(this.root, callback);
    }
    min() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        }
        return current.data;
    }
    max() {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        }
        return current.data;
    }
    search(data) {
        let current = this.root;
        while (current.data !== data) {
            if(data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }
    remove(data) {
        const removeNode = (node, data) => {
            if (node === null) {
                return false;
            }
            if (node.data === data) {
                if (node.left === null && node.right === null) {
                    return null;
                }
                if (node.left === null) {
                    return node.right;
                }
                if (node.right === null) {
                    return node.left;
                }

                let tempNode = node.right;
                while(tempNode.left !== null) {
                    tempNode = tempNode.left;
                }
                node.data = tempNode.data;
                node.right = removeNode(node.right, tempNode.data);
                return node;
            }
            if (node.data > data) {
                node.left = removeNode(node.left, data);
                return node;
            } 
            if(node.data < data) {
                node.right = removeNode(node.right, data);
                return node;
            }
        }
        this.root = removeNode(this.root, data);
    }
}

图(Graph)

这里实现的无向图。

class Graph {
    constructor() {
        this.vertices = []; // 存顶点
        this.adjList = {}; // 存边
    }
    // 顶点
    addVertex(v) {
        this.vertices.push(v);
        this.adjList[v] = [];
    }
    // 边
    addEdge(v, w) {
        this.adjList[v].push(w);
        this.adjList[w].push(v);
    }
    // 转化成邻接表的形式的字符串
    toString() {
        let str = '\n';
        for (let i = 0; i < this.vertices.length; i++) {
            const v = this.vertices[i];
            str += v + ' => ';
            const e = this.adjList[v];
            for (let j = 0; j < e.length; j++) {
                str += ' ' + e[j] + ' ';
            }
            str += '\n';
        }
        return str;
    }
}

参考文章