首页 » 学习JavaScript数据结构与算法(第2版) » 学习JavaScript数据结构与算法(第2版)全文在线阅读

《学习JavaScript数据结构与算法(第2版)》4.2 创建队列

关灯直达底部

我们需要创建自己的类来表示一个队列。先从最基本的声明类开始:

function Queue {  //这里是属性和方法}  

首先需要一个用于存储队列中元素的数据结构。我们可以使用数组,就像在上一章Stack类中那样使用(你会发现Queue类和Stack类非常类似,只是添加和移除元素的原则不同):

let items = ;  

接下来需要声明一些队列可用的方法。

  • enqueue(element(s)):向队列尾部添加一个(或多个)新的项。

  • dequeue:移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。

  • front:返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack类的peek方法非常类似)。

  • isEmpty:如果队列中不包含任何元素,返回true,否则返回false

  • size:返回队列包含的元素个数,与数组的length属性类似。

4.2.1 向队列添加元素

首先要实现的是enqueue方法。这个方法负责向队列添加新元素。这里有一个非常重要的细节,新的项只能添加到队列末尾:

this.enqueue = function(element){  items.push(element);};  

既然我们使用数组来存储队列的元素,就可以用第2章和第3章中介绍过的JavaScript的array类的push方法。

4.2.2 从队列移除元素

接下来要实现dequeue方法。这个方法负责从队列移除项。由于队列遵循先进先出原则,最先添加的项也是最先被移除的。可以用第2章中介绍过的JavaScript的array类的shift方法。如果你不记得了,这里帮你回忆一下,shift方法会从数组中移除存储在索引0(第一个位置)的元素:

this.dequeue = function{  return items.shift;};  

只有enqueue方法和dequeue方法可以添加和移除元素,这样就确保了Queue类遵循先进先出原则。

4.2.3 查看队列头元素

现在来为我们的类实现一些额外的辅助方法。如果想知道队列最前面的项是什么,可以用front方法。这个方法会返回队列最前面的项(数组的索引为0):

this.front = function{  return items[0];};  

4.2.4 检查队列是否为空

下一个是isEmpty方法。如果队列为空,它会返回true,否则返回false(注意这个方法和Stack类里的一样):

this.isEmpty = function{  return items.length == 0;};  

对于isEmpty方法,可以简单地验证内部数组的length是否为0。

我们也可以为Queue类实现类似于array类的length属性的方法。size方法也跟Stack类里的一样:

this.size = function{  return items.length;};  

4.2.5 打印队列元素

完成!我们的Queue类就实现好了。也可以像Stack类一样增加一个print方法:

this.print = function{  console.log(items.toString);};  

现在我们真的完成了!

 Queue类和Stack类非常类似。唯一的区别是dequeue方法和front方法,这是由于先进先出和后进先出原则的不同所造成的。

使用Queue类

首先要做的是实例化我们刚刚创建的Queue类,然后就可以验证它为空(输出为true,因为我们还没有向队列添加任何元素):

let queue = new Queue;console.log(queue.isEmpty); //输出true  

接下来,添加一些元素(添加/"John/"/"Jack/"两个元素——你可以向队列添加任何类型的元素):

queue.enqueue(/"John/");queue.enqueue(/"Jack/");  

添加另一个元素:

queue.enqueue(/"Camila/");  

再执行一些其他的命令:

queue.print;console.log(queue.size); //输出3console.log(queue.isEmpty); //输出falsequeue.dequeue;queue.dequeue;queue.print;  

如果打印队列的内容,就会得到JohnJackCamila这三个元素。因为我们向队列添加了三个元素,所以队列的大小为3(当然也就不为空了)。

下图展示了目前为止执行的所有入列操作,以及队列当前的状态:

然后,出列两个元素(执行两次dequeue方法)。下图展示了dequeue方法的执行过程:

最后,再次打印队列内容时,就只剩Camila一个元素了。前两个入列的元素出列了,最后入列的元素也将是最后出列的。也就是说,我们遵循了先进先出原则。