我们需要创建自己的类来表示一个队列。先从最基本的声明类开始:
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;
如果打印队列的内容,就会得到John
、Jack
和Camila
这三个元素。因为我们向队列添加了三个元素,所以队列的大小为3(当然也就不为空了)。
下图展示了目前为止执行的所有入列操作,以及队列当前的状态:
然后,出列两个元素(执行两次dequeue
方法)。下图展示了dequeue
方法的执行过程:
最后,再次打印队列内容时,就只剩Camila
一个元素了。前两个入列的元素出列了,最后入列的元素也将是最后出列的。也就是说,我们遵循了先进先出原则。