你的位置:首页 > Java教程

[Java教程]第五章:javascript:队列


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

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

一,队列的操作。

队列的两种主要操作是:向队列中插入新元素和删除队列中的元素。插入操作也叫做入队。删除元素也叫做出队。入队是在末尾插入新元素,出队是删除队头的元素。

队列的另外一项操作是读取队头的元素,这个操作叫peek()。该操作返回队头的元素,但不把它从队列中删除。除了读取队头的元素,我们想知道队列中有多少元素,可以使用length属性满足要求;要想清空队列中所有元素。可以使用clear()方法来实现。

二,一个数组实现的队列。

使用数组来实现队列看起来顺理成章。javascript中的数组具有其它编程语言中没有的优点,数组的push()可以在数组末尾加入元素,数组的shift()方法则可以删除数组的第一个元素。

push()方法将它的参数插入数组中第一个开放的位置,该位置总在数组的末尾,即使是个空数组也是如此。

  names = [];  names.push("Cny");  names.push("Jen");  console.log(names);//["Cny", "Jen"]

然后使用shift()方法删除数组的第一个元素:

  names.shift();  console.log(names);//["Jen"]

准备开始实现Queue类。先从构造函数开始:

  function Queue() {    this.dataStore = [];    this.enqueue = enqueue;    this.dequeue = dequeue;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;  }

enqueue()方法向队末尾添加一个元素:

  function enqueue(element) {    this.dataStore.push(element)  }

dequeue方法删除队首的元素

  function dequeue() {    return this.dataStore.shift();  }

可以使用以下方法读取队首和队末的元素

  function front() {    return this.dataStore[0];  }  function back() {    return this.dataStore[this.dataStore.length - 1]  }

还需要toString()方法显示队列内的所有元素

  function toString() {    var retStr = "";    for (var i = 0; i < this.dataStore.length; ++i ) {      retStr += this.dataStore[i] + "\n";    }    return retStr  }

最后,需要一个方法判断队列是否为空

  function empty() {    if (this.dataStore.length == 0) {      return true;    } else {      return false;    }  }

Queue类的定义和测试

  function Queue() {    this.dataStore = [];    this.enqueue = enqueue;    this.dequeue = dequeue;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;  }  //向队末尾添加一个元素  function enqueue(element) {    this.dataStore.push(element)  }  //删除队首的元素  function dequeue() {    return this.dataStore.shift();  }  function front() { //读取队首和队末的元素    return this.dataStore[0];  }  function back() { ////读取队首和队末的元素    return this.dataStore[this.dataStore.length - 1]  }  //显示队列内的所有元素  function toString() {    var retStr = "";    for (var i = 0; i < this.dataStore.length; ++i ) {      retStr += this.dataStore[i] + "\n";    }    return retStr  }  //队列是否为空  function empty() {    if (this.dataStore.length == 0) {      return true;    } else {      return false;    }  }  //测试程序  var q = new Queue();  q.enqueue("Me");  q.enqueue("Her");  q.enqueue("His");  console.log(q.toString());   q.dequeue();  console.log(q.toString());  console.log("第一个元素是: " + q.front());  console.log("最后一个元素是: " + q.back())


三,使用队列,方块舞和舞伴的分配问题

前面我们提到过,经常用队列模拟排队的人。下面,我们使用队列来模拟跳方块舞的人。当男男女女来到舞池,他们按照自己的性别排成两队。当舞池中有地方空出来的时候,两个队列中的第一个人组成舞伴。他们身后的人各自向前一位,组成新的队首。当一对新的舞伴进入舞池时,主持人会大喊出他们的名字。当一对舞伴走出舞池,且两队队伍任意一队没有人时,主持人会把这个情况告诉大家。

为了模拟这个情况,我们将男男女女姓名存储在一个文本文件。

女 小李男 福来男 强子男 李勇女 小梅男 来福女 艾丽男 张帆男 文强男 丁力女 娜娜

每个舞者的信息都被保存在一个Dancer对象中:

  function Dancer(name, sex) {    this.name = name;    this.sex = sex;  }

我们需要一个函数,将舞者的信息读到程序中来。

  function getDancers(males, females) {    //var names = _names.split("\n");    var names = _names.split("**");    for (var i = 0; i < names.length; ++i) {      names[i] = names[i].trim();    }    for (var i = 0; i < names.length; ++i) {      var dancer = names[i].split(" ");      var sex = dancer[0];      var name = dancer[1];      if (sex == "女") {        females.enqueue(new Dancer(name, sex));      } else {        males.enqueue(new Dancer(name, sex))      }    }  }

此函数将舞者按照性别分在不同的队列中。

下一个函数将男性和女性组成舞伴,并宣布配对结果:

  function dance(males, females) {    console.log("这组舞伴是:")    while (!females.empty() && !males.empty()) {      person = females.dequeue();      console.log("女舞者是" + person.name);      person = males.dequeue();      console.log("男舞者是" + person.name);    }  } 

我们可能对该程序做修改,想显示排队时男性女性的数量,队列中目前没有显示元素个数的方法。现在加入

  function count(){    return this.dataStore.length;  }

综合测试:

  function Queue() {    this.dataStore = [];    this.enqueue = enqueue;    this.dequeue = dequeue;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;    this.count = count;  }  //向队末尾添加一个元素  function enqueue(element) {    this.dataStore.push(element)  }  //删除队首的元素  function dequeue() {    return this.dataStore.shift();  }  function front() { //读取队首和队末的元素    return this.dataStore[0];  }  function back() { ////读取队首和队末的元素    return this.dataStore[this.dataStore.length - 1]  }  //显示队列内的所有元素  function toString() {    var retStr = "";    for (var i = 0; i < this.dataStore.length; ++i ) {      retStr += this.dataStore[i] + "\n";    }    return retStr  }  //队列是否为空  function empty() {    if (this.dataStore.length == 0) {      return true;    } else {      return false;    }  }  //队列个数  function count(){    return this.dataStore.length;  }  function Dancer(name, sex) {    this.name = name;    this.sex = sex;  }  function getDancers(males, females) {    //var names = _names.split("\n");    var names = _names.split("**");    for (var i = 0; i < names.length; ++i) {      names[i] = names[i].trim();    }    for (var i = 0; i < names.length; ++i) {      var dancer = names[i].split(" ");      var sex = dancer[0];      var name = dancer[1];      if (sex == "女") {        females.enqueue(new Dancer(name, sex));      } else {        males.enqueue(new Dancer(name, sex))      }    }  }  function dance(males, females) {    console.log("这组舞伴是:")    while (!females.empty() && !males.empty()) {      person = females.dequeue();      console.log("女舞者是" + person.name);      person = males.dequeue();      console.log("男舞者是" + person.name);    }  }   //测试程序  var _names = "女 小李**男 福来**男 强子**男 李勇**女 小梅**男 来福**女 艾丽**男 张帆**男 文强**男 丁力**女 娜娜";  var names = _names.split("**");  //测试程序  var maleDancer = new Queue();  var femaleDancer = new Queue();  getDancers(maleDancer, femaleDancer);  dance(maleDancer, femaleDancer)  if (!femaleDancer.empty()) {    console.log(femaleDancer.front().name + "正在等待跳舞")  }  if (!maleDancer.empty()) {    console.log(maleDancer.front().name + "正在等待跳舞")  }  //显示等待跳舞的人个数  var nanDancers = new Queue();  var nvDancers = new Queue();  getDancers(nanDancers, nvDancers)  dance(nanDancers,nvDancers);  if (nanDancers.count() > 0) {    console.log("有" + nanDancers.count() + "男舞者等待")  }  if (nvDancers.count() > 0) {    console.log("有" + mvDancers.count() + "女舞者等待")  }

 

四:使用队列对数据进行排序

队列不仅用于执行显示生活中与排队有关的操作,还可以用于对数据进行排序。计算机刚出现时,程序是通过穿孔卡输入主机的,每张卡包含一条程序语句。这些穿孔卡装在一个盒子里,经过一个继续装置进行排序。我们可以使用一组队列来模拟这一过程。这种技术叫基数排序。它不是最快的排序算法,但是它展示了一些有趣的队列使用方法。

对于0-99的数字,基数排序将数据扫描两次。第一次按个位上的数字进行排序,第二次按照十位上的数字进行排序。每个数字根据对于位上的数值被分在不同的盒子里。假设有如下数字:

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

经过基数排序第一次扫描后,数字被分配到以下盒子里

Bin 0 : Bin 1 : 91, 31Bin 2 : 82, 22Bin 3 : Bin 4 :Bin 5 : 85, 35Bin 6 : 46Bin 7 :Bin 8 :Bin 9 :

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

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

根据十位上的数字,再次排序。

Bin 0 : Bin 1 : 15Bin 2 : 22Bin 3 : 31, 35Bin 4 : 46Bin 5 : Bin 6 : Bin 7 :Bin 8 : 85Bin 9 : 91, 92

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

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

使用队列代表盒子,可以实现这个算法。我们需要9个队列,每一个对应一个数字。所有队列保存在一个数组中,使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应队列,根据个位数值对其从新排序,然后根据十位上的数值进行排序。结果即为排列好的数字

下面是根据 相应位(个位或十位)上的数值,将数字分配到相应队列的函数:

  function distribute(nums, queues, n, digit) { //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])]      }    }  }

下面是从队列中收集数字的函数

  function collect(queues, nums){    var i = 0;    for (var digit = 0; digit < 10; ++digit) {      while(!queues[digit].empty()){        nums[i++] = queues[digit].dequeue()      }    }  }

附上测试代码

  function Queue() {    this.dataStore = [];    this.enqueue = enqueue;    this.dequeue = dequeue;    this.front = front;    this.back = back;    this.toString = toString;    this.empty = empty;    this.count = count;  }  //向队末尾添加一个元素  function enqueue(element) {    this.dataStore.push(element)  }  //删除队首的元素  function dequeue() {    return this.dataStore.shift();  }  function front() { //读取队首和队末的元素    return this.dataStore[0];  }  function back() { ////读取队首和队末的元素    return this.dataStore[this.dataStore.length - 1]  }  //显示队列内的所有元素  function toString() {    var retStr = "";    for (var i = 0; i < this.dataStore.length; ++i ) {      retStr += this.dataStore[i] + "\n";    }    return retStr  }  //队列是否为空  function empty() {    if (this.dataStore.length == 0) {      return true;    } else {      return false;    }  }  //队列个数  function count(){    return this.dataStore.length;  }  //基础排序程序  function distribute(nums, queues, n, digit) { //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])      }    }  }  function collect(queues, nums){    var i = 0;    for (var digit = 0; digit < 10; ++digit) {      while(!queues[digit].empty()){        nums[i++] = queues[digit].dequeue()      }    }  }  function dispArray(arr) {    for (var i = 0; i < arr.length; ++i) {      console.log(arr[i] + " ")    }  }  //主程序  var queues = []  for (var i = 0; i < 10; ++i) {    queues[i] = new Queue();  }  var nums = []  for (var i = 0; i < 10; ++i){    nums[i] = Math.floor(Math.floor(Math.random() * 101))  }  console.log("之前的基数:")  dispArray(nums);  distribute(nums, queues, 10, 1);  collect(queues, nums);  distribute(nums,queues, 10 ,10);  collect(queues, nums);  console.log("之后的基数:")  dispArray(nums)

(本文未完待续 )

即将更新:

优先队列方法

 

上一章:第四章:javascript: 栈 下一章:第六章: 链表