相思资源网

JS中的算法与数据结构之队列(Queue)实例详解
站长资源 2024/9/21 佚名
24 1538
相思资源网 Design By www.200059.com

本文实例讲述了JS中的算法与数据结构之队列(Queue)。分享给大家供大家参考，具体如下：

队列(Queue)

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

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

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

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

JS中的算法与数据结构之队列(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