JavaScript数据结构——队列的实现

　　前面楼主简单介绍了JavaScript数据结构栈的实现，http://www.cnblogs.com/qq503665965/p/6537894.html，本次将介绍队列的实现。

　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

　　队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。下图演示了这两个操作。

　　队列的另外一项重要操作是读取队头的元素。这个操作叫做 peek() 。该操作返回队头元素，但不把它从队列中删除。除了读取队头元素，我们还想知道队列中存储了多少元素，可以使用 length 属性满足该需求；要想清空队列中的所有元素，可以使用 clear() 方法来实现。下表定义了队列的一些主要方法：

dataStorage	Array	存储数据的底层数据结构
enqueue	int	入队
dequeue	fucntion	出队
front	fucntion	返回队首元素
back	fucntion	返回队尾元素
toString	fucntion	显示队列内的所有元素
empty	function	判断队列是否为空

队列的实现

 function Queue(array) {

     if (array instanceof Array) {

         this.dataStorage = array;

     } else {

         throw "'"+array + "' is not an Array";

     }

 }

 Queue.prototype = {

     enqueue: function (element) {//向队列中添加元素

         this.dataStorage.push(element);

     },

     dequeue: function () {//删除队首元素

         return this.dataStorage.shift();

     },

     front: function () {//返回队首元素

         return this.dataStorage[0];

     },

     back: function () {//返回队尾元素

         return this.dataStorage[this.dataStorage.length - 1];

     },

     toString: function () {//输出队列中所有元素

         var result = "";

         for (var i = 0; i < this.dataStorage.length; i++) {

             result += this.dataStorage[i] + "\t";

         }

         return result;

     },

     empty: function () {//判定队列是否为空

         if (this.dataStorage.length == 0) {

             return true;

         }

         return false;

     }

 }

　　测试：　　

  var queue = new Queue(['a','b']);

 console.log(queue.toString());

 //queue.dequeue();//a出队

 //console.log(queue.toString());

 console.log(queue.front());//队头元素

 console.log(queue.back());//队尾元素

 queue.dequeue();

 queue.dequeue();

 console.log(queue.empty());

队列的应用——基数排序

　　原理：对于 0~99 的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。

　　假设有这样一个数组：{4, 73, 51, 76, 70, 19, 63, 64, 43, 12}，经过基数排序第一次扫描之后，数字被分配到如下盒子中：　　

 Box 0: 70

 Box 1: 51

 Box 2: 12

 Box 3: 73,63,43

 Box 4: 4,64

 Box 5: 76

 Box 6:

 Box 7:

 Box 8:

 Box 9: 19

　　根据盒子的顺序，对数字进行第一次排序的结果如下：

　　70,51,12,73,63,43,4,64,76,19

　　然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

 Box 0: 4

 Box 1: 12,19

 Box 2:

 Box 3:

 Box 4: 43

 Box 5: 51

 Box 6: 63,64

 Box 7: 70,73,76

 Box 8:

 Box 9:

　　最后，将盒子中的数字取出，组成一个新的列表，该列表即为排好序的数字：

　　4,12,19,43,51,63,64,70,73,76

　　使用队列代表盒子，可以实现这个算法。我们需要九个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即为排好序的数字。

　　下面是根据相应位（个位或十位）上的数值，将数字分配到相应队列的方法：　　

      function allocation(nums,queues,n,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 collection(queues, nums) {

             var i = 0;

             for (var digit = 0; digit < 10; ++digit) {

                 while (!queues[digit].empty()) {

                     nums[i++] = queues[digit].dequeue();

                 }

             }

         }

　　测试程序：

         var queues = [];

         for (var i = 0; i < 10; ++i) {

             queues[i] = new Queue([]);

         }

         var nums = [];

         for (var i = 0; i < 10; ++i) {//目标排序数组

             nums[i] = Math.floor(Math.floor(Math.random() * 101));

         }

         console.log("排序前:");

         showArray(nums);

         allocation(nums, queues, 10, 1);

         collection(queues, nums);

         allocation(nums,queues,10,10);

         collection(queues, nums);

         console.log("排序后");

         showArray(nums);

         function showArray(array) {

             console.log(array);

         }

　　结果：

　　下篇楼主将带来，链表的实现。

　　本文的示例代码地址：https://github.com/LJunChina/JavaScript

巴特西

JavaScript数据结构——队列的实现

队列的实现

队列的应用——基数排序

最新文章

热门文章