数据结构-队列结构和优先级队列

队列

队列(Queue),和栈一样,也是一种对数据的"存"和"取"有严格要求的[线性存储结构]

它是一种受限的线性表,先进先出FIFO(First In First Out)

  • 受限之处在于它只允许在表的前端进行删除操作
  • 而在表的后端进行插入操作

栈和队列不要混淆,栈结构是一端封口,特点是"先进后出";而队列的两端全是开口,特点是"先进先出"

js实现

   // js 实现队列
    function Queue() {
        // 队列属性
        this.items = [];

        // 向队列尾部添加新的项
        Queue.prototype.enqueue = function(element) {
            this.items.push(element);
        };

        // 移除队列的第一项,并返回被移除的元素
        Queue.prototype.dequeue = function() {
            return this.items.shift();
        };

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

        // 队列是否为空
        Queue.prototype.isEmpty = function() {
            return this.items.length === 0;
        };

        // 返回队列的元素个数
        Queue.prototype.size = function() {
            return this.items.length;
        };

        // 将队列转换为字符串形式
        Queue.prototype.toString = function() {
            var str = "";
            for (var i = 0; i < this.items.length; i++) {
                str += this.items[i] + " ";
            }
            return str;
        };
    }

    // 测试队列
    var queue = new Queue();

    queue.enqueue("aaa");
    queue.enqueue("bbb");
    queue.enqueue("ccc");
    queue.enqueue("ddd");
    console.log(queue.toString()); // aaa bbb ccc ddd 
    queue.dequeue();
    console.log(queue.toString()); // bbb ccc ddd
    console.log(queue.isEmpty()); // false
    console.log(queue.size()); //3

应用 实现击鼓传花

规则: 几个朋友围成一圈,依次报数,当到某个数字时,淘汰对应的人。 剩下的人继续从淘汰的下一位开始重新报数。 知道只剩余1人时结束。

   // 击鼓传花
   // list 所有人  num 第几个数字淘汰
   function passGame(list, num) {
       // 创建队列
       var queue = new Queue();

       // 把list中的人加入到队列中
       for (var i = 0; i < list.length; i++) {
           queue.enqueue(list[i]);
       }

       //   开始报数
       // 循环条件 剩余人数大于1
       while (queue.size() > 1) {
           // 从0开始 到 淘汰数字前 的所有人 重新加入队列
           for (var i = 0; i < num - 1; i++) {
               queue.enqueue(queue.dequeue());
           }
           // 对应的淘汰数字的人,直接淘汰
           queue.dequeue();
       }
       //   获取最后的胜利的人
       var endName = queue.front();
       console.log('胜利者', endName);
       //   返回 剩下的胜利者是原来列表第几
       return list.indexOf(endName);
   }

   var list = ['zs', 'ls', 'ww', 'zl', 'leilei']
   console.log(passGame(list, 3)) //最后胜利 zl 第3

优先级队列

优先队列不再遵循先入先出的原则,而是分为两种情况:

最大优先队列,无论入队顺序,当前最大的元素优先出队。

最小优先队列,无论入队顺序,当前最小的元素优先出队。

优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。

优先级队列要考虑的问题

  • 每个元素不再只是一个暑假,而且包含数据的优先级
  • 在添加方式中,根据优先级放入正确的位置。

比如现实中的例子:
急诊科会考虑病情严重的患者,而不是排号的顺序

js实现优先级队列

    // 优先级队列
    function PriorityQueue() {
        // 封装属性
        this.items = [];

        // PriorityQueue 中创建一个内部类, 用来保存元素的优先级
        // 传入元素 和 优先级
        function QueueElement(element, priority) {
            this.element = element;
            this.priority = priority;
        }

        // 实现插入方法
        PriorityQueue.prototype.enqueue = function(element, priority) {
            //   创建 QueueElement对象
            var queueElement = new QueueElement(element, priority);

            // 判断队列是否为空, 为空直接放入队列
            if (this.items.length === 0) {
                this.items.push(queueElement);
            } else {
                // 否则 遍历比较队列中的每一项的优先级,
                // 当前传入元素的优先级小于队列中的某一项时,插入,并终止遍历
                var flag = false; // 标志 是否插入
                for (var i = 0; i < this.items.length; i++) {
                    if (queueElement.priority < this.items[i].priority) {
                        this.items.splice(i, 0, queueElement);
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    this.items.push(queueElement);
                }
            }
        };
        // 移除队列的第一项,并返回被移除的元素
        PriorityQueue.prototype.dequeue = function() {
            return this.items.shift();
        };

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

        // 队列是否为空
        PriorityQueue.prototype.isEmpty = function() {
            return this.items.length === 0;
        };

        // 返回队列的元素个数
        PriorityQueue.prototype.size = function() {
            return this.items.length;
        };

        // 将队列转换为字符串形式
        PriorityQueue.prototype.toString = function() {
            var str = "";
            for (var i = 0; i < this.items.length; i++) {
                str += this.items[i].element + " ";
            }
            return str;
        };
    }

    // 测试代码
    var pq = new PriorityQueue()

    pq.enqueue('aaa-100', 100)
    pq.enqueue('bbb-10', 10)
    pq.enqueue('ccc-50', 50)
    pq.enqueue('ddd-30', 30)

    console.log(pq.toString()); // bbb-10 ddd-30 ccc-50 aaa-100 

    pq.dequeue()
    console.log(pq.toString()); //ddd-30 ccc-50 aaa-100 
    console.log(pq.isEmpty()); // false
    console.log(pq.size()); // 3
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 223,277评论 6 521
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 95,487评论 3 400
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 170,114评论 0 366
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 60,367评论 1 300
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 69,352评论 6 398
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,919评论 1 314
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 41,328评论 3 426
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 40,278评论 0 277
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,808评论 1 321
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,882评论 3 343
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 41,005评论 1 354
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,672评论 5 351
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 42,344评论 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,839评论 0 25
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,959评论 1 275
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 49,481评论 3 379
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 46,031评论 2 361

推荐阅读更多精彩内容