队列(Queue)

我们之前说到了,它是一种比较高效的数据结构,遵循 先入后出(LIFO,last-in-first-out) 的原则。而今天我们要讨论的队列,它也是一种特殊的列表,它与栈不同的是, 队列只能在队尾插入元素,在队首删除元素,就像我们平时排队买票一样~

队列用于存储按顺序排列的数据,遵循 先进先出(FIFO,First-In-First-Out) 的原则,也是计算机常用的一种数据结构,别用于很多地方,比如提交给操作系统的一系列进程,打印池任务等。

同栈有点类似,队列的操作主要也是有两种:向队列中插入新元素和删除队列中的元素,即入队和出队操作,我们采用 enqueue 和 dequeue 两个方法。

除此之外,队列还有一些其他的操作,比如读取队首的元素,该操作仅返回对头元素并不将它从队列中删除,类似栈的 peek 方法;back 方法读取队尾的元素;toString 方法可以打印当前队列中所有的元素;clear 方法清空当前队列等。

队列(Queue)

 
队列数据定义

我们定义好数据类型,可以通过JS中的数组去实现它。

队列的实现

//定义队列 function Queue(){ this.dataStore = []; this.enqueue = enqueue; //入队 this.dequeue = dequeue; //出队 this.front = front; //查看队首元素 this.back = back; //查看队尾元素 this.toString = toString; //显示队列所有元素 this.clear = clear; //清空当前队列 this.empty = empty; //判断当前队列是否为空 }

我们先来实现入队操作:

enqueue:向队列添加元素

//向队列末尾添加一个元素,直接调用 push 方法即可 function enqueue ( element ) { this.dataStore.push( element ); }

因为JS中的数组具有其他语言没有的有点,可以直接利用 shift 方法删除数组的第一个元素,因此,出队操作的实现就变得很简单了。

dequeue:删除队首的元素

//删除队列首的元素,可以利用 JS 数组中的 shift 方法 function dequeue () { if( this.empty() ) return 'This queue is empty'; else this.dataStore.shift(); }

我们注意的,上面我做了一个判断,队列是否还有元素,因为去删除空队列的元素是没有意义的,那么,我们就来看看 empty 方法是如何实现的。

empty:判断队列是否为空

//我们通过判断 dataStore 的长度就可知道队列是否为空 function empty(){ if( this.dataStore.length == 0 ) return true; else return false; }

我们先来看看测试一下这几个方法,

var queue = new Queue(); console.log( queue.empty() ); //true //添加几个元素 queue.enqueue('Apple'); queue.enqueue('Banana'); queue.enqueue('Pear'); console.log( queue.empty() ); // false

现在,我不知道谁在第一个,谁是最后一个,我们可以利用 front 和 back 方法分别来查看,

front:查看队首元素

//查看队首元素,直接返回数组首个元素即可 function front(){ if( this.empty() ) return 'This queue is empty'; else return this.dataStore[0]; }

back:查看队尾元素

//查看队首元素,直接返回数组最后一个元素即可 //读取队列尾的元素 function back () { if( this.empty() ) return 'This queue is empty'; else return this.dataStore[ this.dataStore.length - 1 ]; }

我们先看看对不对:

//查看队首元素 console.log( queue.front() ); // Apple //查看队尾元素 console.log( queue.back() ); // Pear //出队 queue.dequeue(); //查看队首元素 console.log( queue.front() ); // Banana //查看队尾元素 console.log( queue.back() ); // Pear

没问题!现在,我想看看,总共有多少水果,toString方法来实现,

toString:查看队列中所有元素

//查看对了所有元素,我这里采用数组的 join 方法实现 function toString(){ return this.dataStore.join('\n'); }

现在,你可以看看你还有什么水果没吃的了,

console.log( queue.toString() ) // Apple // Banana // Pear

我们就剩下一个 clear 方法了,如果你已经把所有水果都吃完了,那么你应该使用 clear 方法,

//清空当前队列,也很简单,我们直接将 dataStore 数值清空即可 function clear(){ delete this.dataStore; this.dataStor = []; }

至此,我们已经用JS实现了一个队列,怎么样,是不是觉得JS的数组超级好用,省去了不少麻烦,有木有!!

//清空队列 queue.clear(); console.log( queue.empty() ); // true

下面,我们利用队列来实现基数排序。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/4ca01427b25212b66b818b9db603e406.html