数据结构与算法－队列篇(js实现)

　　队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,新来的人只能在后面排队,直到轮到他们为止。

　　队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。队列被用在很多地方,比如提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

一.队列的主要操作：

• 插入。插入操作也叫做入队，在队尾插入新元素。
• 删除。删除操作也叫做出队，删除队头的元素。
• 读取队头的元素。
• 读取队尾的元素。
• 读取队列中成员数。
• 判断队列是否为空。

　一个用数组实现的队列：

　利用数组中的push和shift方法可以使队列的实现显得非常简单，请看例子：

var names=[];
names.push("likek");
names.push("zhangsan");
names.push("lisi");
console.log(names.join());//"likek,zhangsan,lisi"
names.shift();//出队
console.log(names.join());//"zhangsan,lisi"

 二.队列的实现：

　从定义一个Queue构造函数开始

function Queue() {
　this.dataStore = [];
}

 　队列的各种操作

Queue.prototype={
  enqueue:function　(element) {
　　　this.dataStore.push(element);//入队，加入新成员
　},
  dequeue:function(){
     return this.dataStore.shift();//删除并返回队首元素
  },
  front:function(){
     return this.dataStore[0];//返回队首元素
  },
  back:function(){
     return this.dataStore[this.dataStore.length-1];//返回队尾元素
  },
  toString:function(){
     return this.dataStore.join();//返回队列中所有元素
  },
  isempty:function(){
     return !this.dataStore.length;//判断队列是否为空
  }
}

   测试

var ui=new Queue();
ui.enqueue("likek");
ui.enqueue("哈哈");
ui.enqueue(18);
ui.toString();//"likek,哈哈,18"
ui.dequeue();//"likek"
ui.toString();//"likek,哈哈"
ui.isempty();//false
ui.dequeue();ui.dequeue();
ui.isempty();//true

 三.队列的应用－基数排序(这里只考虑小于100的数字)：

　对于 0~99 的数字,基数排序将数据集扫描两次。第一次按个位上的数字进行排序,第二

　次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有

　如下数字:

　91, 46, 85, 15, 92, 35, 31, 22

　经过基数排序第一次扫描之后,数字被分配到如下盒子中:

　bin 0:

    bin 1: 91, 31

    bin 2: 92, 22

    bin 3:

    bin 4:

    bin 5: 85, 15, 35

    bin 6: 46

    bin 7:

    bin 8:

    bin 9:

　根据盒子的顺序,对数字进行第一次排序的结果如下:

　91, 31, 92, 22, 85, 15, 35, 46

　然后根据十位上的数值再将上次排序的结果分配到不同的盒子中:

　bin 0:

    bin 1:15

    bin 2: 22

    bin 3: 31,35

    bin 4: 46

    bin 5:

    bin 6:

    bin 7:

    bin 8: 85

    bin 9: 91,92

　最后,将盒子中的数字取出,组成一个新的列表,该列表即为排好序的数字:

　15, 22, 31, 35, 46, 85, 91, 92　

 

   接下来我们用代码来实现它：

//按照个位数字或者十位数字将数组的每一个元素压入对应的队列中
//nums代表需要排序的数组
//queues代表了nums数组的长度
//n代表了个位数或十位数字最大
//digit表示了此次排列是针对个位数还是十位数
function distribute(nums, queues, n, digit) {
　for (var i = 0; i < n; ++i) {
　　　if (digit == 1) {
　　　　queues[nums[i]%10].enqueue(nums[i]);
　　　}else {
　　　　queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
　　　}
　}
}
//将经过以上distribute函数处理之后的queues队列数组中的元素按照顺序取出(会将queues数组中的每一个队列清空)，并放回nums，此时nums将更新为按照个位数或十位数排序后的数组
function collect(queues, nums) {
　　var i = 0;
　　for (var digit = 0; digit < 10; ++digit) {
　　　　while (!queues[digit].isempty()) {
　　　　　nums[i++] = queues[digit].dequeue();
　　　　}
　　}
}
//生成队列数组，总共十个队列
var queues = [];
for (var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
//长度为10的待排序数组
var nums = [65,32,12,25,12,6,78,7,44,23];
//输出排序之前的数组nums
console.log(nums.join());//65,32,12,25,12,6,78,7,44,23

//按照个位数的值将nums内的各个元素压入队列数组queues
distribute(nums, queues, 10, 1);
collect(queues, nums);//更新nums数组中的元素并清空queues中每个队列
console.log(nums.join());//32,12,12,23,44,65,25,6,7,78
//按照十位数的值将nums内的各个元素压入队列数组queues
distribute(nums, queues, 10, 10);
collect(queues, nums);//更新nums
console.log(nums.join());//6,7,12,12,23,25,32,44,65,78
//排序完成

四.优先队列

　　优先队列和普通的队列的区别在于，优先队列在删除元素时不必遵守先进先出的约定，而是根据优先级的大小来决定该删除谁。

　　举个现实生活中的例子，比如医院急诊科的候诊室,就是一个采取优先队列的例子。当病人进入候诊室时,护士会评估患者病情的严重程度,然后给一个优先级代码。高优先级的患者先于低优先级的患者就医,同样优先级的患者按照先来先服务的顺序就医。

　我们现在用代码来实现这一场景：

    //建一个患者类
    function Patient(name, code) {　
        this.name = name;　
        this.code = code;　 //代表优先级，值越小代表优先级越高
    }
    //对于Queue类我们只需要修改其dequeue方法和toString方法即可
    function Queue() {　
        this.dataStore = [];
    }
    Queue.prototype = {
        enqueue: function (element) {　　　
            this.dataStore.push(element); //入队，加入新成员
            　
        }
        , dequeue: function () {　　　　
            var priority = 0;　　　　
            for (var i = 1; i < this.dataStore.length; ++i) {　　　　　　
                if (this.dataStore[i].code < this.dataStore[priority].code) {
                    priority = i;
                    console.log(priority);　　　　　
                }　　　
            }　　　
            return this.dataStore.splice(priority, 1);　
        }
        , front: function () {
            return this.dataStore[0]; //返回队首元素
        }
        , back: function () {
            return this.dataStore[this.dataStore.length - 1]; //返回队尾元素
        }
        , toString: function () {　　　　
            var retStr = "";　　　　
            for (var i = 0; i < this.dataStore.length; ++i) {　　　　
                retStr += this.dataStore[i].name + " code: "　　　 + this.dataStore[i].code + "\n";　　
            }　　
            return retStr;　
        }
        , isempty: function () {
            return !this.dataStore.length; //判断队列是否为空
        }
    }
    //五个病人排队等候
    var p = new Patient("Smith", 5);
    var ed = new Queue();
    ed.enqueue(p);
    p = new Patient("Jones", 4);
    ed.enqueue(p);
    p = new Patient("Fehrenbach", 6);
    ed.enqueue(p);
    p = new Patient("Brown", 1);
    ed.enqueue(p);
    p = new Patient("Ingram", 1);
    ed.enqueue(p);
    console.log(ed.toString());
　　  /*Smith code: 5
　　　Jones code: 4
　　　Fehrenbach code: 6
　　　Brown code: 1
　　　Ingram code: 1*/
　　//一个病人出队就诊
    ed.dequeue();
    console.log(ed.toString());
　　  /*Smith code: 5
　　　Jones code: 4
　　　Fehrenbach code: 6
　　　Ingram code: 1*/
　　//又一个病人出队就诊
    ed.dequeue();
    console.log(ed.toString());
　　  /*Smith code: 5
　　　Jones code: 4
　　　Fehrenbach code: 6*/
　　//我来看病
    p = new Patient("likeke", 2);
    ed.enqueue(p);
    console.log(ed.toString());
　　  /*Smith code: 5
　　　Jones code: 4
　　　Fehrenbach code: 6
　　　likeke code: 2*/