JS队列数据结构实现及在基数排序中的应用

本文通过具体实例，深入讲解JavaScript中算法与数据结构的核心组件——队列(Queue)。内容旨在为读者提供清晰的实现思路与代码参考，便于学习与实践。

队列(Queue)

此前我们探讨过栈(Stack)，这是一种遵循“先入后出”(LIFO, Last-In-First-Out)原则的高效数据结构。相比之下，队列(Queue)同样是一种特殊的线性表，但其操作规则不同：元素只能在队尾插入，在队首删除。这种机制类似于日常生活中排队购票的场景。

队列主要用于存储按顺序排列的数据，严格遵循“先进先出”(FIFO, First-In-First-Out)原则。作为计算机系统中常用的数据结构，队列广泛应用于操作系统进程调度、打印池任务管理等多种场景。

与栈类似，队列的基本操作主要包含两类：向队列插入新元素以及从队列中删除元素，分别对应入队(Enqueue)和出队(Dequeue)操作，我们将通过这两个核心方法来实现队列功能。

除了基本的入队和出队，队列还包含其他辅助操作：例如读取队首元素，该操作仅返回队头数据而不将其移除，类似于栈的peek方法；back方法用于读取队尾元素；toString方法用于打印队列中所有元素；clear方法则用于清空整个队列。

队列(Queue) 队列数据定义

确定数据类型后，我们可以利用JavaScript中的数组来构建队列的实现。

队列的实现


//定义队列

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 );
}

由于JavaScript数组具备其他语言所不具备的特性，可以直接利用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 = [];
}

至此，我们已使用JavaScript成功实现了一个完整的队列。可以看出，利用JS数组特性可以省去不少繁琐步骤，确实非常便捷。


//清空队列

queue.clear();

console.log( queue.empty() ); // true

接下来，我们将利用队列来实现基数排序(Radix Sort)。

基数排序(Radix Sort)属于“分配式排序”(Distribution Sort)，它通过键值的局部信息，将待排序元素分配到特定的“桶”中，从而达到排序目的。基数排序是一种稳定性排序算法，其时间复杂度为O(nlog(r)m)，其中r为基数，m为堆数。在某些情况下，基数排序的效率高于其他稳定性排序算法。

首先看一下基数排序的实现步骤（以两位数为例）：需要进行两次扫描，第一次按个位数字排序，第二次按十位数字排序。每个数字根据对应数值被分配到不同的盒子中，最后将盒子中的数字依次取出，组成新的列表，即为排序后的结果。

假设我们有一串数字，分别为 73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数字排序，放到不同的盒子里，如下图

第一次排序
接下来将这些盒子中的数值重新串接起来，成为以下的数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39
然后根据十位数字排序，再放到不同的盒子里，如下图

第二次排序
接下来将这些盒子中的数值重新串接起来，整个数列已经排序完毕：14, 22, 28, 39, 43, 55, 65, 73, 81, 93

我们已经了解了基数排序的算法思想，接着我们要结合队列去实现它，一起来看看吧。


//基数排序

var queues = []; //定义队列数组
var nums = [];  //定义数字数组

//选十个0~99的随机数进行排序
for ( var i = 0 ; i < 10 ; i ++ ){
 queues[i] = new Queue();
 nums[i] = Math.floor( Math.random() * 101 );
}

//排序之前
console.log( 'before radix sort: ' + nums );

//基数排序
distribution( nums , queues , 10 , 1 );
collect( queues , nums );
distribution( nums , queues , 10 , 10 );
collect( queues , nums );

//排序之后
console.info('after radix sort: ' + nums );

//根据相应的（个位和十位）数值，将数字分配到相应队列

function distribution ( nums , queues , n , digit ) { //digit表示个位或者十位的值
 for( var i = 0 ; i < n ; i++ ){
  if( digit == 1){
   queues[ nums[i] % 10 ].enqueue( nums[i] );
  }else{
   queues[ Math.floor( nums[i] / 10 ) ].enqueue( nums[i] );
  }
 }
}

//从队列中收集数字

function collect ( queues , nums ) {
 var i = 0;
 for ( var digit = 0 ; digit < 10 ; digit ++ ){
  while ( !queues[digit].empty() ){
   nums[ i++ ] = queues[digit].front();
   queues[digit].dequeue();
  }
 }
}

我这里贴出两组测试的结果，大家自己动手实践一下。


//第一组测试

before radix sort: 23,39,2,67,90,41,47,21,98,13
after radix sort: 2,13,21,23,39,41,47,67,90,98

//第二组测试

before radix sort: 29,62,38,16,55,26,33,54,76,65
after radix sort: 16,26,29,33,38,54,55,62,65,76

至此，我们队列也就告一段落了，大家还可以往深入拓展，比如优先队列，循环队列等，希望大家能发散思维，多动手实践，一起加油！

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

JavaScript队列(Queue)数据结构实现与基数排序应用详解

队列(Queue)

队列的实现

实用工具推荐