首先什么是队列?
排队买东西就是生活中队列的实际例子,在队伍中大家必须按照顺序来,不能插队,新来的人只能排在队伍的最后面。新加入的人相当于队列的后端加入的元素,队伍最前面买完东西的人离开队伍相当于是队列的前端元素的删除。其他的一些操作就不一一列举了,大家可以自行想象类比。
其实队列是和栈很类似,区别在于栈是先入后出(FILO)的数据结构,只能操作栈顶的元素,而队列是先入先出(FIFO)的数据结构,可以同时操作队列的前端和后端。队列只能在前端删除元素,在后端插入元素,相当于是一个受限的线性表,只能在前后端来对元素进行操作,不能够像线性表一样对中间的任意元素进行插入和删除操作,所以队列实际上可以看作是一种特殊的线性表。
既然要用javascript来实现队队列的模拟,那么先列举出需要用到的js数据结构以及对应的方法。
还是用js中的数组来存储队列中的元素,js中队数组的主要操作有如下方法:
-
-
push(a) 将元素a压入数组末端,返回数组的长度
-
shift() 删除数组开端的元素,返回这个元素
-
unshift(a) 在数组的开端添加新的元素a,返回数组的长度
-
slice(a,b) 返回原数组位置从[a,b)的值构成的所有项
-
splice(a,b,args) 从数组的a位置开始删除b个元素,然后再a位置插入系数args
-
concat(args) 在数组的末端加上参数args
我们将实现的队列的方法有如下几种:
-
-
dequeue () 出队
-
front () 返回队头
-
isEmpty() 队列是否为空
-
clear() 清空队列
-
size() 返回这个队列的长度
-
print() 打印队列所有元素
下面是js实现:
/* * 数据结构:队列 */ function Queue(){ var array = []; this.enqueue = function(data){ //入队操作 array.push(data); } this.dequeue = function(){ //出队 return array.shift(); } this.front = function(){ //返回对头 return array[0]; } this.isEmpty = function(){ // 判断队列是否为空 if(array.length == 0){ return true; } return false; } this.clear = function(){ //清除队列 array = []; } this.size = function(){ //返回队列的长度 return array.length; } this.print = function(){ //打印队列的所有元素 console.log(array.toString()); } } //下面实例化了一个队列对象queue,进行验证。 var queue = new Queue(); queue.enqueue("xianghuang"); //先入队三个元素 queue.enqueue("xiaobai"); queue.enqueue("xiaohua"); queue.print();//查看此时的队列中的元素 queue.dequeue(); // 出队一个元素 queue.print(); //看看此时的队列中的元素 console.log(queue.front()); //查看此时的队头 console.log(queue.isEmpty());//看看此时是否为空 console.log(queue.size()); //查看队列的长度 queue.clear(); //清空队列元素
下面是在chrome的console内的验证,没有错误。