• 技术文章 >web前端 >js教程

    深入解析js中实现队列(代码分享)

    奋力向前奋力向前2021-08-25 09:37:17转载237

    之前的文章《浅析Vue中入口缓存的问题(代码分享)》中,给大家介绍了解了Vue中入口缓存的问题。下面本篇文章给大家介绍js中实现队列,伙伴们来看看吧。

    队列定义

    队列(Queue)是一种遵从先进先出(First in,first out。简称FIFO)原则的有序集合。 它和栈的不同点是栈是先进后出的,队列是先进先出的,栈都是在一端进与出,而队列是在一端进在另一端出。栈的删除操作在表尾进行,队列的删除操作在表头进行。顺序栈能够实现多栈空间共享,而顺序队列不能。 共同点是只允许在端点处插入和删除元素。多链栈和多链队列的管理模式可以相同。

    栈(stack)定义

    JavaScript是单线程语言,主线程执行同步代码。 函数调用时, 便会在内存形成了一个“调用记录”,又称“调用帧”,保存调用位置和内部变量等信息。如果函数内部还调用了其他函数,那么在调用记录上方又会形成一个调用记录, 所有的调用记录就形成一个“调用栈”。(尾调用、尾递归优化)

    堆(heap)定义

    对象被分配在一个堆中,一个用以表示一个内存中大的未被组织的区域。

    所以

    JS是单线程, 主线程执行同步代码, 事件、I/O 操作等异步任务,将会进入任务队列执行,异步执行有结果之后,就会变为等待状态, 形成一个先进先出的执行栈,主线程的同步代码执行完之后,再从”任务队列”中读取事件, 执行事件异步任务的回调。 这就是为什么执行顺序是, 同步 > 异步 > 回调 更简单的说:只要主线程空了(同步),就会去读取”任务队列”(异步),这就是JavaScript的运行机制。

    本文将实现 基本队列、优先队列和循环队列

    消息队列与事件循环Event Loop

    一个JavaScript运行时包含了一个待处理的消息队列(异步任务),(内部是不进入主线程,而进入”任务队列”(task queue)的任务。比如UI事件、ajax网络请求、定时器setTimeoutsetInterval等。 每一个消息都与一个函数(回调函数callback)相关联。当栈为空时,从队列中取出一个消息进行处理。这个处理过程包含了调用与这个消息相关联的函数(以及因而创建了一个初始堆栈帧)。当栈再次为空的时候,也就意味着消息处理结束。

    这个过程是循环不断的,所以整个的这种运行机制又称为Event Loop(事件循环)。

    基本队列

    基本队列的方法中,包含了一下6个方法

    ① 向队列(尾部)中添加元素(enqueue)

    ②(从队列头部)删除元素(dequeue)

    ③ 查看队列头部的元素(front)

    ④ 查看队列是否为空(isEmpty)

    ⑤ 查看队列的长度(size)

    ⑥ 查看队列(print)

    function Queue() {
      //初始化队列(使用数组实现)
      var 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 == 0;
      };
    
      //清空队列
      this.clear = function () {
        items = [];
      };
    
      //返回队列长度
      this.size = function () {
        return items.length;
      };
    
      //查看列队
      this.show = function () {
        return items;
      };
    }
    
    var queue = new Queue();
    queue.enqueue("hello");
    queue.enqueue("world");
    queue.enqueue("css");
    queue.enqueue("javascript");
    queue.enqueue("node.js");
    console.log(queue.isEmpty()); // false
    console.log(queue.show()); //hello,world,css3,javascript,node.js
    console.log(queue.size()); //5
    console.log(queue.front()); //hello
    console.log(queue.dequeue()); //hello
    console.log(queue.show()); //'world', 'css', 'javascript', 'node.js'
    console.log(queue.clear());
    console.log(queue.size()); //0

    优先队列的实现

    在优先队列中,元素的添加或者删除是基于优先级的。实现优先队列有两种方式:① 优先添加,正常出列;② 正常添加,优先出列

    优先添加,正常出列的(最小优先队列)例子(这个例子在实现队列的基础上,把添加进队列的元素从普通数据改为对象(数组)类型,该对象包含需要添加进队列的元素的值和优先级):

    function PriorityQueue() {
        //初始化队列(使用数组实现)
        var items = []
        //因为存在优先级,所以插入的列队应该有一个优先级属性
        function queueEle(ele, priority) {
            this.ele = ele
            this.priority = priority
        }
        //入队
        this.enqueue = function (ele, priority) {
            let element = new queueEle(ele, priority)
            //为空直接入队
            if (this.isEmpty()) {
                items.push(element)
            }
            else {
                var qeueued = false; //是否满足优先级要求,并且已经入队
                for (let i = 0; i < this.size(); i++) {
                    if (element.priority < items[i].priority) {
                        items.splice(i, 0, element)
                        qeueued = true
                        break;
                    }
                }
                //如果不满足要求,没有按要求入队,那么就直接从尾部入队
                if (!qeueued) items.push(element)
            }
        }
    
        //出队
        this.dequeue = function () {
            return items.shift()
        }
    
        //返回首元素
        this.front = function () {
            return items[0]
        }
    
        //队列是否为空
        this.isEmpty = function () {
            return items.length == 0
        }
    
        //清空队列
        this.clear = function () {
            items = []
        }
    
        //返回队列长度
        this.size = function () {
            return items.length
        }
    
        //查看列队
        this.show = function () {
            return items
        }
    }
    
    var priorityQueue = new PriorityQueue();
    priorityQueue.enqueue('优先级2-1', 2);
    priorityQueue.enqueue('优先级1-1', 1);
    priorityQueue.enqueue('优先级1-2', 1);
    priorityQueue.enqueue('优先级3-1', 3);
    priorityQueue.enqueue('优先级2-2', 2);
    priorityQueue.enqueue('优先级1-3', 1);
    priorityQueue.show(); // 按优先级顺序输出
    
    //输出
    [
    0:queueEle {ele: "优先级1-1", priority: 1},
    1:queueEle {ele: "优先级1-2", priority: 1},
    2:queueEle {ele: "优先级1-3", priority: 1},
    3:queueEle {ele: "优先级2-1", priority: 2},
    4:queueEle {ele: "优先级2-2", priority: 2},
    5:queueEle {ele: "优先级3-1", priority: 3}
    ]

    循环队列

    可以使用循环队列来模拟击鼓传花的游戏(约瑟夫环问题):一群孩子围成一圈,每次传递 n 个数,停下来时手里拿花的孩子被淘汰,直到队伍中只剩下一个孩子,即胜利者。

    循环队列,每次循环的时候(从队列头部)弹出一个孩子,再把这个孩子加入到队列的尾部,循环 n 次,循环停止时弹出队列头部的孩子(被淘汰),直到队列中只剩下一个孩子。

    function Queue() {
      //初始化队列(使用数组实现)
      var 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 == 0;
      };
    
      //清空队列
      this.clear = function () {
        items = [];
      };
    
      //返回队列长度
      this.size = function () {
        return items.length;
      };
    
      //查看列队
      this.show = function () {
        return items;
      };
    }
    
    /**
     *
     * @param {名单} names
     * @param {指定传递次数} num
     */
    function onlyOne(names, num) {
      var queue = new Queue();
      //所有名单入队
      names.forEach((name) => {
        queue.enqueue(name);
      });
    
      //淘汰的人名
      var loser = "";
      //只要还有一个以上的人在,就一直持续
      while (queue.size() > 1) {
        for (let i = 0; i < num; i++) {
          //把每次出队的人,再次入队 ,这样一共循环了num 次(击鼓传花一共传了num次)
          queue.enqueue(queue.dequeue());
        }
        //到这就次数就用完了,下一个就要出队了
        loser = queue.dequeue();
        console.log(loser + "被淘汰了");
      }
      //到这就剩下一个人了
      return queue.dequeue();
    }
    
    var names = ["文科", "张凡", "覃军", "邱秋", "黄景"];
    var winner = onlyOne(names, 99);
    console.log("金马奖影帝最终获得者是:" + winner);

    推荐学习:JavaScript视频教程

    以上就是深入解析js中实现队列(代码分享)的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:禅境花园,如有侵犯,请联系admin@php.cn删除
    专题推荐:js
    上一篇:浅谈Node.js中的path模块和常用方法 下一篇:Node.js中如何利用node-cron来调度任务?
    线上培训班

    相关文章推荐

    • 通过javascript计算圆柱体的体积并保留4位小数• 示例详解用javascript隐藏电子邮件地址• 深入浅析JavaScript中的回调函数• 详解怎么使用JavaScript打印div元素的内容• 你值得了解的JavaScript“继承之jquery”使用方法(代码详解)• 深入解析JavaScript中对象拷贝方法(附代码)

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网