JavaScript实现常见的数据结构

前端开发 作者: 2024-08-26 11:20:01
使用JavaScript实现栈、队列、链表、集合等常见数据结构。可能会有点用?
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();
    }
}
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();
    }
}

优先队列

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,queueElement);
            } else {
                super.enqueue(queueElement);
            }
        }
    }
}

循环队列

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;
    }
}
// 节点
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;
    }
}
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));
    }
}
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];
    }
}
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;
    }
}
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);
    }
}
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;
    }
}
原创声明
本站部分文章基于互联网的整理,我们会把真正“有用/优质”的文章整理提供给各位开发者。本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
本文链接:http://www.jiecseo.com/news/show_68942.html