队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,新来的人只能在后面排队,直到轮到他们为止。
队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。队列被用在很多地方,比如提交操作系统执行的一系列进程、打印任务池等,一些仿真系统用队列来模拟银行或杂货店里排队的顾客。
一.队列的主要操作:- 插入。插入操作也叫做入队,在队尾插入新元素。
- 删除。删除操作也叫做出队,删除队头的元素。
- 读取队头的元素。
- 读取队尾的元素。
- 读取队列中成员数。
- 判断队列是否为空。
一个用数组实现的队列:
利用数组中的push和shift方法可以使队列的实现显得非常简单,请看例子:
var names=[]; names.push("likek"); names.push("zhangsan"); names.push("lisi"); console.log(names.join());//"likek,zhangsan,lisi" names.shift();//出队 console.log(names.join());//"zhangsan,lisi"
二.队列的实现:
从定义一个Queue构造函数开始
function Queue() { this.dataStore = []; }
队列的各种操作
Queue.prototype={ enqueue:function (element) { this.dataStore.push(element);//入队,加入新成员 }, dequeue:function(){ return this.dataStore.shift();//删除并返回队首元素 }, front:function(){ return this.dataStore[0];//返回队首元素 }, back:function(){ return this.dataStore[this.dataStore.length-1];//返回队尾元素 }, toString:function(){ return this.dataStore.join();//返回队列中所有元素 }, isempty:function(){ return !this.dataStore.length;//判断队列是否为空 } }
测试
var ui=new Queue(); ui.enqueue("likek"); ui.enqueue("哈哈"); ui.enqueue(18); ui.toString();//"likek,哈哈,18" ui.dequeue();//"likek" ui.toString();//"likek,哈哈" ui.isempty();//false ui.dequeue();ui.dequeue(); ui.isempty();//true
三.队列的应用-基数排序(这里只考虑小于100的数字):
对于 0~99 的数字,基数排序将数据集扫描两次。第一次按个位上的数字进行排序,第二
次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有
如下数字:
91, 46, 85, 15, 92, 35, 31, 22
经过基数排序第一次扫描之后,数字被分配到如下盒子中:
bin 0:
bin 1: 91, 31
bin 2: 92, 22
bin 3:
bin 4:
bin 5: 85, 15, 35
bin 6: 46
bin 7:
bin 8:
bin 9:
根据盒子的顺序,对数字进行第一次排序的结果如下:
91, 31, 92, 22, 85, 15, 35, 46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中:
bin 0:
bin 1:15
bin 2: 22
bin 3: 31,35
bin 4: 46
bin 5:
bin 6:
bin 7:
bin 8: 85
bin 9: 91,92
最后,将盒子中的数字取出,组成一个新的列表,该列表即为排好序的数字:
15, 22, 31, 35, 46, 85, 91, 92
接下来我们用代码来实现它:
//按照个位数字或者十位数字将数组的每一个元素压入对应的队列中 //nums代表需要排序的数组 //queues代表了nums数组的长度 //n代表了个位数或十位数字最大 //digit表示了此次排列是针对个位数还是十位数 function distribute(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]); } } } //将经过以上distribute函数处理之后的queues队列数组中的元素按照顺序取出(会将queues数组中的每一个队列清空),并放回nums,此时nums将更新为按照个位数或十位数排序后的数组 function collect(queues, nums) { var i = 0; for (var digit = 0; digit < 10; ++digit) { while (!queues[digit].isempty()) { nums[i++] = queues[digit].dequeue(); } } } //生成队列数组,总共十个队列 var queues = []; for (var i = 0; i < 10; ++i) { queues[i] = new Queue(); } //长度为10的待排序数组 var nums = [65,32,12,25,12,6,78,7,44,23]; //输出排序之前的数组nums console.log(nums.join());//65,32,12,25,12,6,78,7,44,23 //按照个位数的值将nums内的各个元素压入队列数组queues distribute(nums, queues, 10, 1); collect(queues, nums);//更新nums数组中的元素并清空queues中每个队列 console.log(nums.join());//32,12,12,23,44,65,25,6,7,78 //按照十位数的值将nums内的各个元素压入队列数组queues distribute(nums, queues, 10, 10); collect(queues, nums);//更新nums console.log(nums.join());//6,7,12,12,23,25,32,44,65,78 //排序完成
四.优先队列
优先队列和普通的队列的区别在于,优先队列在删除元素时不必遵守先进先出的约定,而是根据优先级的大小来决定该删除谁。举个现实生活中的例子,比如医院急诊科的候诊室,就是一个采取优先队列的例子。当病人进入候诊室时,护士会评估患者病情的严重程度,然后给一个优先级代码。高优先级的患者先于低优先级的患者就医,同样优先级的患者按照先来先服务的顺序就医。
我们现在用代码来实现这一场景:
//建一个患者类 function Patient(name, code) { this.name = name; this.code = code; //代表优先级,值越小代表优先级越高 } //对于Queue类我们只需要修改其dequeue方法和toString方法即可 function Queue() { this.dataStore = []; } Queue.prototype = { enqueue: function (element) { this.dataStore.push(element); //入队,加入新成员 } , dequeue: function () { var priority = 0; for (var i = 1; i < this.dataStore.length; ++i) { if (this.dataStore[i].code < this.dataStore[priority].code) { priority = i; console.log(priority); } } return this.dataStore.splice(priority, 1); } , front: function () { return this.dataStore[0]; //返回队首元素 } , back: function () { return this.dataStore[this.dataStore.length - 1]; //返回队尾元素 } , toString: function () { var retStr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retStr += this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n"; } return retStr; } , isempty: function () { return !this.dataStore.length; //判断队列是否为空 } } //五个病人排队等候 var p = new Patient("Smith", 5); var ed = new Queue(); ed.enqueue(p); p = new Patient("Jones", 4); ed.enqueue(p); p = new Patient("Fehrenbach", 6); ed.enqueue(p); p = new Patient("Brown", 1); ed.enqueue(p); p = new Patient("Ingram", 1); ed.enqueue(p); console.log(ed.toString()); /*Smith code: 5 Jones code: 4 Fehrenbach code: 6 Brown code: 1 Ingram code: 1*/ //一个病人出队就诊 ed.dequeue(); console.log(ed.toString()); /*Smith code: 5 Jones code: 4 Fehrenbach code: 6 Ingram code: 1*/ //又一个病人出队就诊 ed.dequeue(); console.log(ed.toString()); /*Smith code: 5 Jones code: 4 Fehrenbach code: 6*/ //我来看病 p = new Patient("likeke", 2); ed.enqueue(p); console.log(ed.toString()); /*Smith code: 5 Jones code: 4 Fehrenbach code: 6 likeke code: 2*/
相关推荐
第1章 课程导学对课程整体进行介绍,让您切实感受到前端工程师学习数据结构与算法的必要性。 1-1 课程导学 试看 1-2 学习姿势 1-3 说明与承诺第2章 基础算法之“字符串类”字符串作为JS最基本的数据类型,掌握好字符...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
本文实例讲述了JavaScript数据结构与算法之队列原理与用法。分享给大家供大家参考,具体如下: 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和...
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...
数据结构1.pptx 2X1{SH5V_HSM`5JS[H]Z`JP.png 33XTI0U)]QTVK1MINJY0)F3.png 34MMEH64LMCA}H5G_RXKPGO.png 65]YTLJ{NP7ICB9{]%XK5J2.png 73I2ZJ(3Z5XWL3W1LFVZRCR.png MQJ[~8HPO2L{35`{CY8{WXO.png P)(%S5}WL7HD(09E1...
栈和队列 JS常用的数据结构和算法,链表、栈、队列、排序和查找:octocat
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...
通过JavaScript来封装实现常见的数据结构与算法 介绍 收录了各种常见的数据结构与算法通过 JavaScript 来封装的代码,可以直接拿取使用 注意 现在暂未更新完,进度会随着本人CSDN博客上的文章进度而更新,欢迎大家...
该自述文件重新组合了许多项目,这些项目侧重于使用JavaScript实现数据结构。 该项目本身不包含任何代码。 :baby: 孩子们 :oden: 顺序 :JavaScript的列表规范 数组 :JavaScript的动态数组数据结构 双端队列 :snake...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
多种语言包括java、python、c语言、go语言、php等来实现的数据结构的源码,包含数组、 链表、栈、队列、递归、排序、二分查找、散列表、二叉树、堆、图、回溯、分治、动态规划的实现方法。非常适合学习数据结构的小...
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...
顺序数据结构数组栈Stack后进先出(LIFO)队列Queue先进先出(FIFO)链表LinkedList存储有序的元素集合元素本身指针(链接):指向下一个元素
算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...