数据结构 JS 版

摘要：内容栈队列链表集合字典散列表树栈通过类封装实现栈结构，不直接继承数组的原生方法的原因是，数组具有某些其他数据结构的方法，为了只让栈暴露栈的方法，还得编写将非栈的方法封闭的代码，多了冗余代码，且不是面向对象编程的合理表现。

内容：栈、队列、链表、集合、字典、散列表、树

通过类封装实现栈结构，不直接继承数组的原生方法的原因是，数组具有某些其他数据结构的方法，为了只让栈暴露栈的方法，还得编写将非栈的方法封闭的代码，多了冗余代码，且不是面向对象编程的合理表现。

//栈，方法包括入栈操作、出栈操作、返回栈顶元素、判断栈是否为空、清空栈、栈的长度
//这里栈实例对象的方法都可看作闭包函数，items可看作类的私有变量，只有类实例的方法来访问，而items也是栈内容的存储实体。
function Stack(){
    var items = [];
    this.push = function(ele){
        items.push(ele);
    };
    this.pop = function(){
        items.pop();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.peek = function(){
        return items[items.length-1];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}
var stack = new Stack();
console.log(stack);
stack.push(2);
console.log(stack.size());
console.log(stack.isEmpty());

基础实现

//队列，方法包括入队操作、出队操作、返回队首元素、判断队列是否为空、清空队列、队列的长度
function Queue(){
    var items = [];
    this.inqueue = function(ele){
        items.push(ele);
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}

优先级队列

考虑到队列中每个元素具有优先级，所以队列中的元素采用对象来实现，具有两个属性：元素的值和元素的优先级。

//优先级队列
function PriorityQueue(){
    var items = [];
    function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }
    this.inqueue = function(element,priority){
        var queueElement = new QueueElement(element,priority);
        if(this.isEmpty()){
            items.push(queueElement);
        }else{
            for(var i=0;i priority){
                    items.splice(i,0,queueElement);
                    break;
                }else if(i === (items.length-1)){
                    items.push(queueElement);
                    break;  // 这里一定要break，不然会循环插入，导致堆溢出
                }
            }
        }
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0].element;
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
    this.get = function(){
        return items;
    }
}

循环队列/击鼓传花游戏

可以换个角度想：一排凳子，所有人循环去坐，击鼓之后，坐在第一个凳子（队头）上的人淘汰，即下面代码参考的思路。

//循环队列
//击鼓传花游戏，以固定循环次数来模拟每轮击鼓的固定时长，该游戏会一轮一轮迭代，每轮淘汰一人，直到只剩最后一人即为胜者
function hotPotato(namelist,num){
    var queue = new Queue();
    for(var i=0;i 1){
        for(i=0;i
链表
由于链表中每个元素都有指向下一个元素的指针，所以链表中每个元素利用对象来实现，对象具有两个属性：元素的值和指向下一个元素的指针；在指定位置插入或删除元素，都需要注意与前一个和后一个元素之间指针的关系；
//链表，元素在内存中非连续放置，方法包括链表尾部加入/删除元素，链表指定位置加入/删除元素，找出元素在链表中的索引，链表是否为空，链表的长度
function LinkedList(){
    var head = null;//链表第一个元素的引用
    var length = 0;//链表的长度，不然寻求size很麻烦
    var end = null;//链表最后一个元素的引用，方便插入/删除元素
    function Node(element){
        this.element = element;
        this.next = null;
    }
    //从链表尾部加入node元素
    this.appendList = function(element){
        var node = new Node(element);
        if(head === null){
            head = node;
        }else{
            end.next = node;
        }
        end = node;
        length++;
    };
    //从链表指定位置加入node元素,0表示在链表头插入该元素
    this.appendListAt = function(position,element){
        var node = new Node(element);
        if(position > 0){
            var frontNode = this.findNodeAt(position);
            var afterNode = frontNode.next;
            frontNode.next = node;
            node.next = afterNode;
            length++;
        }else if(position === 0){
            node.next = head;
            head = node;
            length++;
        }
    };
    //从链表尾部删除node元素
    this.removeList = function(){
        if(head !== null){
            var findNode = this.findNodeAt(length-1);
            end = findNode;
            findNode.next = null;
            length--;
        }
    };
    //从链表指定位置删除node元素
    this.removeListAt = function(position){
        if(position > 1){ //永远检测用户输入
            var frontNode = this.findNodeAt(position-1);
            var afterNode = frontNode.next.next;
            frontNode.next = afterNode;
            length--;
        }else if(position = 1){
            head = head.next;
            length--;
        }
    };
    //链表的大小
    this.size = function(){
        return length;
    };
    this.isEmpty = function(){
        return head === null ? true : false;
    }
    this.toString = function(){
        var iterNode = head;
        var outString = [];
        outString.push(head.element);
        for(var i=1;i 1){
            iterNode = iterNode.next;
            position--;
        }
        return iterNode;
    }
}
集合
采用对象来实现集合，对象的属性存放元素值，因为对象中的属性无序，可以很好地模拟集合的特性
//集合，集合类的方法包括添加/删除元素，是否有某值，清除集合，集合大小
function Set(){
    var items = {};
    this.has = function(value){
        return items.hasOwnProperty(value);
    }
    //向集合中添加元素
    this.add = function(value){
        if(!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    }
    //删除集合中的元素
    this.remove = function(value){
        if(this.has(value)){
            delete items[value];  // 删除元素的属性
        }
        return false;
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.values = function(){
        return Object.keys(items); //返回对象自身中可枚举属性
    }

    //集合的交集，并集，差集，子集方法
    //并集
    this.union = function(setB){
        var setAvalues = this.values();
        var setUnion = new Set();
        for(var i=0;i
字典
有集合的实现类似
//采用对象来实现字典，以key-value的形式存储，因为对象中的属性无序，字典的方法包括通过key来添加/删除元素，是否有某值，清除字典，字典大小
function Dictionary(){
    var items = {};
    this.has = function(key){
        return items.hasOwnProperty(key);
    }
    //向字典中添加元素
    this.set = function(key,value){
        if(!this.has(key)){
            items[key] = value;
            return true;
        }
        return false;
    }
    //删除字典中的元素
    this.remove = function(key){
        if(this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    }
    //获取固定的值
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.keys = function(){
        return Object.keys(items); //返回对象自身中可枚举属性
    }
    this.values = function(){
        var res = [];
        for(key in items){
            if(items.hasOwnProperty(key)){
                res.push(items[key]);
            }
        }
        return res;
    }
    //获取整个字典对象
    this.getItems = function(){
        return items; 
    }

}
二叉搜索树

二叉搜索树中每个节点都有三个属性。值，左引用，右引用。
注意在实现时，拿到节点对象的引用，并不能对节点本身进行删除，最好删除节点的方法是将上一个节点的引用指向置为null，并将节点对象的引用置为null（释放内存，通知垃圾回收）

//二叉搜索树
function BinarySearchTree(){
    var rootNode = null;
    function TreeNode(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //向树中插入新节点
    this.insert = function(key){
        var treeNode = new TreeNode(key);
        if(rootNode === null){
            rootNode = treeNode;
        }else{
            insertNode(rootNode,treeNode);
        }
    }
    function insertNode(node,treeNode){
        if(treeNode.key < node.key){
            if(node.left === null){
                node.left = treeNode;
            }else{
                insertNode(node.left,treeNode);
            }
        }else if(treeNode.key > node.key){
            if(node.right === null){
                node.right = treeNode;
            }else{
                insertNode(node.right,treeNode);
            }
        }
    }
    //先序遍历
    this.preOrderTraverse = function(){
        if(rootNode === null){
            console.log("没有节点");
        }else{
            pretraverse(rootNode);
        }
    }
    function pretraverse(node){
        if(node !== null){
            pretraverse(node.left);
            console.log(node.key);
            pretraverse(node.right);
        }
    }
    //中序遍历
    this.inOrderTraverse = function(){
        if(rootNode === null){
            console.log("没有节点");
        }else{
            intraverse(rootNode);
        }
    }
    function intraverse(node){
        if(node !== null){
            console.log(node.key);
            intraverse(node.left);
            intraverse(node.right);
        }
    }
    //后序遍历
    this.posOrderTraverse = function(){
        if(rootNode === null){
            console.log("没有节点");
        }else{
            postraverse(rootNode);
        }
    }
    function postraverse(node){
        if(node !== null){
            postraverse(node.left);
            postraverse(node.right);
            console.log(node.key);
        }
    }
    //移除树中的节点
    this.remove = function(key){
        rootNode = removeNode(rootNode,key);
    }
    function removeNode(node,key){
        if(node === null){
            return null;
        }
        if(key < node.key){
            node.left = removeNode(node.left,key);
            return node; //与下面三个return node的功能都是保证removeNode的返回值为删除节点后树的根节点
        }else if(key > node.key){
            node.right = removeNode(node.right,key);
            return node;
        }else{
            if(node !== null){ //考虑到被删除节点的三种情况
                if((node.left === null) && (node.right === null)){
                    node = null;//这里只是为了垃圾回收node，下面作用都类似
                    return node;//这里才是删除的功能，这里的返回是为了让node.left = removeNode(node.left,key);中node.left=null;
                }else if((node.left === null) && (node.right !== null)){
                    var temp = node.right;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right === null)){
                    var temp = node.left;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right !== null)){
                    var findNode = findMin(node.right);
                    node.key = findNode.key;
                    node.right = removeNode(node.right,findNode.key);
                    return node;
                }
            }
        }
    }
    function findMin(node){
        while(node.left !== null){
            node = node.left;
        }
        return node;
    }
    //查找某个节点
    this.search = function(key){
        var node = rootNode;
        while((node !== null) && (node.key !== key)){
            if(key < node.key){
                node = node.left;
            }else if(key > node.key){
                node = node.right;
            }
        }
        return (node !== null) ? true : false;
    }
    //获取树中最小值
    this.min = function(){
        var node = rootNode;
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    //获取树中最大值
    this.max = function(){
        var node = rootNode;
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    this.getRootNodeKey = function(){
        return rootNode.key;
    }
}