javascript里的数据结构

[violet0sea]

1. 堆栈

   function Stack() {
   let items = [];
   
   // 入栈
   this.push = function(ele) {
       items.push(ele);
   };
   
   // 出栈
   this.pop = function() {
       return items.pop();
   }
   
   // 返回栈顶的元素
   this.peek = function() {
       const len = items.length;
       if(len === 0) {
           return null;
       }
       return items[len - 1];
   }
   
   // 返回堆栈是否为空
   this.isEmpty = function() {
       return !items.length;
   }
   
   // 清空
   this.clear = function() {
       items = [];
   }
   
   // 获取堆栈的大小
   this.size = function() {
       return items.length;
   }
   }

[violet0sea]

队列

function Queue() {
    let items = [];

    // 入列
    this.enqueue = function(ele) {
        items.push(ele);
    };

    // 出列
    this.dequeue = function() {
        return items.shift();
    };

    // 返回队列中第一个元素
    this.front = function() {
        return items[0];
    };

    // 判断队列是否为空
    this.isEmpty = function() {
        return !items.length;
    };

    // 返回队列长度
    this.size = function() {
        return items.length;
    };

    // 清空队列
    this.clear = function() {
        items = [];
    };
}

优先队列 元素的添加和移除基于优先级

function PriorityQueue() {
    let items = [];

    function Element(element, priority) {
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function(element, priority) {
        const node = new Element(element, priority);

        if(this.isEmpty()) {
            items.push(node);
        } else {
            let added = false;
            for(let i = 0; i < items.length; i++) {
                if(node.priority < items[i].priority) {
                    items.splice(i, 0, node);
                    added = true;
                    break;
                }
            }

            if(!added) {
                items.push(node);
            }
        }
    };

 // 出列
    this.dequeue = function() {
        return items.shift();
    };

    // 返回队列中第一个元素
    this.front = function() {
        return items[0];
    };

    // 判断队列是否为空
    this.isEmpty = function() {
        return !items.length;
    };

    // 返回队列长度
    this.size = function() {
        return items.length;
    };

    // 清空队列
    this.clear = function() {
        items = [];
    };

}

[violet0sea]

链表 链表是存储有序元素的集合 区别于数组是连续放置的，链表可以是不连续的，每个元素由一个存储元素本身的节点（element）以及一个指向下一个元素的引用（next），通常使用下面的结构

function node(element) {
    this.element = element;
    this.next = next;
}

传统的数组在增加和移除元素时需要移动其他元素，而链表只需要操作指针（也就是next）； 数组在访问元素时使用下标，属于快速的操作，而链表却需要从头开始迭代整个列表直到找到需要的元素。

function LinkedList() {
    const Node = function(element) {
        this.element = element;
        this.next = null;
    };

    let length = 0;
    let head = null;

    this.append = function(element) {
        const node = new Node(element);
        let current;

        if(head === null) {
            head = node;
        } else {
            current = head;

            while(current.next) {
                current = current.next;
            }

            current.next = node;
        }

        length++;
    }

    this.insert = function(position, element) {
        if(position >= 0 && position < length) {
            const node = new Node(element);
            let current = head,
                previous,
                index = 0;

            if(position === 0) {
                node.next = current;
                head = node;
            } else {
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }

                previous.next = node;
                node.next = current;
            }

            length++;

            return true;
        } else {
            return false;
        }

    }

    this.removeAt = function(position) {
        if(position > -1 && position < length) {
            let current = head,
                previous,
                index = 0;

            if(position === 0) {
                head = current.next;
            } else {
                while(index++ < position) {
                    previous = current;
                    current = current.next;
                }

                previous.next = current.next;
            }

            length--;

            return current.element;
        } else {
            return null;
        }
    }

    this.indexOf = function(element) {
        let current = head,
            i = 0;

        while(current) {
            if(current.element === element) {
                return i;
            }
            current = current.next;
            i++;
        }

        return -1;
    }

    this.remove = function(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }

    this.size= function() {
        return length;
    }

    this.getHead = function() {
        return head;
    }

    this.isEmpty = function() {
        return length === 0;
    }

    this.toString = function() {
        let result = '';
        let current = head;

        while(current) {
            result += current.element;
            current = current.next;
        }

        return result;
    }
}

[violet0sea]

集合 由一组无序且唯一的项组成的 例如自然数集合：N = {0, 1, 2, 3, 4, 5,...} 等价于没有重复元素而且没有顺序的数组

Javascript已经存在Set类的实现

function SimpleSet() {
    let items = [];

    this.has = function(value) {
        return !!~items.indexOf(value);
    };

    this.add = function(value) {
        if(!this.has(value)) {
            items.push(value);
        }

        return items;
    };

    this.delete = function(value) {
        let index = items.indexOf(value);

        if(!!~index) {
            items.splice(index, 1);
            return true;
        }

        return false;
    };

    this.clear = function() {
        items = [];
    };

    this.size = function() {
        return items.length;
    };

    this.values = function() {
        return [...items];
    };
}

[violet0sea]

二叉搜索树🌲

function BinarySearchTree() {
    const Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    let root = 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);
            }
        }
    }

    this.insert = function(key) {
        const newNode = new Node(key);

        if(root === null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    }

    // 树的遍历：先序、中序、后序

    function inOrderTraverseNode(node, cb) {
        if(node !== null) {
            inOrderTraverseNode(node.left, cb);
            cb(node.key);
            inOrderTraverseNode(node.right, cb);
        }
    }

    this.inOrderTraverse = function(cb) {
        inOrderTraverseNode(root, cb);
    };

    function preOrderTraverseNode(node, cb) {
        if(node !== null) {
            cb(node.key);
            preOrderTraverseNode(node.left, cb);
            preOrderTraverseNode(node.right, cb);
        }
    }

    this.preOrderTraverse = function(cb) {
        preOrderTraverseNode(root, cb);
    };

    function postOrderTraverseNode(node, cb) {
        if(node !== null) {
            postOrderTraverseNode(node.left, cb);
            postOrderTraverseNode(node.right, cb);
            cb(node.key);
        }
    }

    this.postOrderTraverse = function(cb) {
        postOrderTraverseNode(root, cb);
    };

    this.minNode = function() {
        let current = root;
        while(current && current.left) {
            current = current.left;
        }

        return current && current.key;
    };

    this.maxNode = function() {
        let current = root;
        while(current && current.right) {
            current = current.right;
        }

        return current && current.key;
    };

    function searchNode(node, key) {
        let current = node;

        if(current === null) {
            return false;
        }

        if(current.key > key) {
            return searchNode(current.left, key);
        } else if(current.key < key) {
            return searchNode(current.right, key);
        } else {
            return true;
        }
    }

    this.search = function(key) {
        return searchNode(root, key);
    };

    function removeNode(node, key) {

        if(node === null) {
            return null;
        }

        if(key < node.key) {
            node.left = removeNode(node.left, key);
            return node;
        } else if(key > node.key) {
            node.right = removeNode(node.right, key);
            return node;
        } else {

            // case 1: 一个叶节点
            if(node.left === null && node.right === null) {
                node = null;
                return node;
            }

            // case 2: 只有一个子节点的节点
            if(node.left === null) {
                node = node.right;
                return node;
            } else if(node.right === null) {
                node = node.left;
                return node;
            }

            // case 3: 拥有两个叶子节点的节点
            function findMinNode(node) {
                while(node && node.left) {
                    node = node.left
                }

                return node;
            }
            const temp = findMinNode(node.right);
            node.key = temp.key;
            node.right = removeNode(node.right, temp.key);
            return node;
        }
    }

    this.remove = function(key) {
        root = removeNode(root, key);
    };
}