队列的定义

队列(Queue)是一种遵从先进先出(First in, first out。简称FIFO)原则的有序集合。

定义队列的方法

入队

方法:enqueue() 
语法:arrayQueue.enqueue(element1,element2…elementX) 
参数:至少有一个元素 
描述:添加一个或几个新元素在队列尾部。

出队

方法:dequeue() 
语法:arrayQueue.dequeue() 
参数:无 
描述:移除队列头部的元素,同时返回被移除的元素

返回队首元素

方法:front() 
语法:arrayQueue.front() 
参数:无 
描述:仅仅返回队列的第一个元素

队列是否为空

方法:isEmpty() 
语法:arrayQueue.isEmpty() 
参数:无 
描述:如果队列中没有任何元素则返回true,否则返回false

清空队列

方法:clear() 
语法:arrayQueue.clear() 
参数:无 
描述:移除队列中的所有元素

返回队列的长度

方法:size() 
语法:arrayQueue.size() 
参数:无 
描述:返回队列中元素的个数

输出队列

方法:show() 
语法:arrayQueue.show() 
参数:无 
描述:返回队列中的所有元素

代码实现

通过动态原型模式创建队列类型

队列类跟栈类非常类似,唯一的区别就是的出队与退栈的方法不同。

   function Queue() {
        this.items = [];
        //初始化队列方法
        if (typeof Queue.prototype.push != "function") {
            //入队
            Queue.prototype.enqueue = function() {
                    var len = arguments.length;
                    if (len == 0) {
                        return;
                    }
                    for (var i = 0; i < len; i++) {
                        this.items.push(arguments[i])
                    }
                }
                //出队
            Queue.prototype.dequeue = function() {
                    var result = this.items.shift();
                    return typeof result != 'undefined' ? result : false;
                }
                //返回队首元素
            Queue.prototype.front = function() {
                    return this.items[items.length - 1];
                }
                //队列是否为空
            Queue.prototype.isEmpty = function() {
                    return this.items.length == 0;
                }
                //返回队列长度
            Queue.prototype.size = function() {
                    return this.items.length;
                }
                //清空队列
            Queue.prototype.clear = function() {
                    this.items = [];
                }
                //返回队列
            Queue.prototype.show = function() {
                return this.items;
            }
        }
    }

优先队列

优先队列是队列的修改版。元素的添加与移除是基于优先级别进行的。

通过寄生组合式继承队列,并为子类添加独有的方法实现优先队列。

//继承父类原型
   function inheritPrototype(superTyep, subType) {
          //创建寄生式继承           
           function inherit(p) {
               if (p == null) throw TypeError(); //首先判断输入的参数是不是为空,为空则抛出异常
               if (Object.create) { //判断当前浏览器支不支持Object.create方法,不支持则手写
                  return Object.create(p);
               }
                var t = typeof p; //进一步检测
                if (t !== 'object' && t !== 'function') {
                    throw TypeError();
                }

                function f() {} //定义一个空构造函数
                f.prototype = p; //将其原型属性设置为p
                return new f(); //使用f()创建p的继承对象
            }
            //实现父类原型的继承
            var prototype = inherit(superTyep.prototype);
            prototype.constructor = subType;
            subType.prototype = prototype;
        }

实现寄生组合式继承

//利用寄生组合式继承队列类型
        //优先队列
        function priorityQueue() {
            //继承父类的实例属性
            Queue.call(this);
            //创建队列元素
            function QueueElement(element, priority) {
                this.element = element;
                this.priority = (priority==0||priority) ? priority : 4; //默认级别为4
            }
            //修改(覆盖)父类方法
            this.enqueue = function (element, priority) {
                var queueElement = new QueueElement(element, priority);
                //设置优先级分级
                function pri(pri) {
                    //分级最多10级
                    //分级可以是数字0到9,也可以是字母A-J或小写字母a-j
                    var ma =pri+"",
                        num = /^[0-9]$/,
                        str = /^[A-J]$|^[a-j]$/;
                    //判断是否符合条件
                    if (!ma.match(num) && !ma.match(str)) {
                        throw new TypeError("分级必须是数字0-9或者是字母A-J(a-j)");
                    } else if (ma.match(num)) {
                        return true;
                    } else {
                        //要将字母转化成数字
                        switch (true) {
                            case /A/i.test(ma):
                                queueElement.priority = 0;
                                break;
                            case /B/i.test(ma):
                                queueElement.priority = 1;
                                break;
                            case /C/i.test(ma):
                                queueElement.priority = 2;
                                break;
                            case /D/i.test(ma):
                                queueElement.priority = 3;
                                break;
                            case /E/i.test(ma):
                                queueElement.priority = 4;
                                break;
                            case /F/i.test(ma):
                                queueElement.priority = 5;
                                break;
                            case /G/i.test(ma):
                                queueElement.priority = 6;
                                break;
                            case /H/i.test(ma):
                                queueElement.priority = 7;
                                break;
                            case /I/i.test(ma):
                                queueElement.priority = 8;
                                break;
                            case /J/i.test(ma):
                                queueElement.priority = 9;
                                break; 
                            default:
                                throw new TypeError("设置级别错误。");
                                break;
                        }
                        return true;                       
                    }
                }
                //分级成功才能进入队列
                //队列为空直接添加元素
                if ( this.isEmpty()&&pri(queueElement.priority)) {
                    this.items.push(queueElement);
                } else if (pri(queueElement.priority)) {
                    var added = false,
                        _items=this.items;
                    for (var i = 0; i < _items.length; i++) {
                        //级别高的放到前面
                        if (queueElement.priority <_items[i].priority) {       
                            _items.splice(i, 0, queueElement);
                            added = true;
                            break;
                        }
                    }  
                    //级别最低放最后          
                    if (!added) {
                        this.items.push(queueElement)
                    }
                }
            }
        }
        //继承父类原型 
        inheritPrototype(Queue, priorityQueue);

调用

var ss = new priorityQueue();
        ss.enqueue("a", 1);
        ss.enqueue("b", 3);
        ss.enqueue("c", 2);
        ss.enqueue("d", "a");
        console.log(ss.show());

成功按照级别入队: 
这里写图片描述

出队

ss.dequeue();

成功出队:

这里写图片描述