JS数据结构：栈，队列，Set，Map

- 日理万妓 2022-01-20 10:11 141阅读 0赞

## Stack 栈 ##

var Stack = function(){
        var items = []   
        //私有属性，禁止直接外部访问，只能调用接口
    
        // push 栈顶添加元素
        this.push = function(element){
            items.push(element)
        }
        // pop 移除栈顶元素
        this.pop = function(){
            return items.pop()
        }
        // peek 检查栈顶
        this.peek = function(){
            return items[items.length - 1]
        }
    
        // 检查栈 是否为空
        this.isEmpty = function(){
            return items.length == 0
        }
    
        // 清除栈
        this.clear = function(){
            items = []
        }
    
        // 获取栈的大小
        this.length = function(){
            return items.length
        }
    
        // 检查items
        this.getItems = function(){
            return items
        }
    }
    复制代码

## Queue 队列 ##

var Queue = function(){
        var items = []
    
        //入队
        this.enqueue = function(element){
            items.push(element)
        }
        // 出队
        this.dequeue = function(){
            return items.shift()
        }
        //查看队列头
        this.front = function(){
            return items[0]
        }
    
        //检查队列是否为空
        this.isEmpty = function(){
            return items.length === 0
        }
    
        //队列大小
        this.size = function(){
            return items.length
        }
    }
    
    复制代码

## PriorityQueue 优先队列 ##

var PriorityQueue = function(){
        var items = []
    
        // 数据+优先级
        var QueueItem = function(element,priority){
            this.element = element
            this.priority = priority
        }
        
        this.enqueue = function(element,priority){
            var queueItem = new QueueItem(element,priority)
    
            var added = false
            
            for(var i = 0 ; i < items.length ; i++){
                if(queueItem.priority > items[i].priority){
                    items.splice(i,0,queueItem)
                    added = true
                    break
                }
            }
            if(!added){
                items.push(queueItem)
            }
        }
        this.getItems = function(){
            return items
        }
    }
    复制代码

## Set 集合 ##

*  我写的和网上其他方法不一样，
 *  ES6的Set支持去重，并防止对象转化成为\[object Obeject\]

## Map 字典 ##

*  桶 + 哈希 + 链表

class myMap {
                constructor() {
                    //初始化桶
                    this.bucket = new Array(8);
                    for (var i = 0; i < this.bucket.length; i++) {
                        this.bucket[i] = {
                            type: 'bucket_' + i,
                            next: null
                        }
                    }
                }
                makeHash(key) {
                    // 根据类型产生哈希 
                    var hash = 0;
                    if (typeof key !== 'string') {
                        if (typeof key === 'number') {
                            hash = Object.is(NaN, key) ? 0 : key;
                        } else if (typeof key == 'object') {
                            hash = 0;
                        } else if (typeof key == 'boolean') {
                            hash = +key;
                        } else {
                            //function undefined symbol()
                            hash = 8;
                        }
                    } else {
                        //如果是string
                        for (var i = key.length - 1; i > key.length - 4; i--) {
                            if (key[i]) {
                                hash += key[i].charCodeAt(0)
                            }
                        }
                    }
                    hash = hash % 8;
                    console.log(hash)
                    return hash;
                }
                get(key) {
                    let hash = this.makeHash(key);
                    //游标 桶
                    var oTempBucket = this.bucket[hash];
    
                    while (oTempBucket) {
                        if (oTempBucket.next.key == key) {
                            //如果已经存在
                            return oTempBucket.next.value
                        }
                        oTempBucket = oTempBucket.next;
                    }
                }
                set(key, value) {
                    let hash = this.makeHash(key);
                    var oTempBucket = this.bucket[hash];
                    while (oTempBucket.next) {
                        //查找
                        if (oTempBucket.next.key == key) {
                            //如果已经存在
                            oTempBucket.next.key == key
                        } else {
                            //如果不存在， 临时桶的next为空，下一步跳出循环
                            oTempBucket = oTempBucket.next;
                        }
                    }
                    //对空桶初始化赋值
                    oTempBucket.next = {
                        key,
                        value,
                        next: null
                    }
                }
                has(key) {
                    let hash = this.makeHash(key);
                    //游标桶
                    var oTempBucket = this.bucket[hash];
                    while (oTempBucket) {
                        if (oTempBucket.next && oTempBucket.next.key == key) {
                            //如果已经存在
                            return true
                        }
                        oTempBucket = oTempBucket.next;
                    }
                    return false;
                }
                delete(key) {
                    let hash = this.makeHash(key);
                    //游标桶
                    var oTempBucket = this.bucket[hash];
                    while (oTempBucket.next) {
                        // 判断下一个的key是否是
                        if (oTempBucket.next.key == key) {
                            console.log(oTempBucket, oTempBucket.next.next)
                            //当前的这个denext等于下一个的下一个
                            oTempBucket.next = oTempBucket.next.next;
                            return true;
                        }
    
                        oTempBucket = oTempBucket.next;
                    }
                    return false;
                }
                clear() {
                    this.bucket = new Array(8);
                    for (var i = 0; i < this.bucket.length; i++) {
                        this.bucket[i] = {
                            type: 'bucket_' + i,
                            next: null
                        }
                    }
                }
            }
    复制代码

## 二叉树 ##

*  正在写。。。

复制代码

## 图 ##

*  正在写。。。

复制代码