本文实例讲述了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