本文共 6083 字,大约阅读时间需要 20 分钟。
如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: , 或者添加我的微信: 372623326
我们已经学习了一种受限的线性结构: 栈结构. 并且已经知道这种受限的数据结构对于解决某些特定问题, 会有特别的效果.
下面, 我们再来学习另外一个受限的数据结构: 队列. 它也是一种受限的线性结构.
我们也先来认识一下队列, 看看它的特点和应用场景等.
队列结构
队列(Queue),它是一种运算受限的线性表,先进先出(FIFO First In First Out)
生活中类似的队列结构
img
队列的图解
img
队列在程序中的应用
我们来实现一个类, 用于模拟队列中的操作
队列的创建
我们需要创建自己的类, 来表示一个队列
// 自定义队列function Queue() { var items = [] // 队列操作的方法}
代码解析:
队列的操作
队列有哪些常见的操作呢?
enqueue(element)
:向队列尾部添加一个(或多个)新的项。dequeue()
:移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。front()
:返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与Stack
类的peek
方法非常类似)。isEmpty()
:如果队列中不包含任何元素,返回true
,否则返回false
。size()
:返回队列包含的元素个数,与数组的length
属性类似。现在, 我们来实现这些方法. (其实已经比较简单了)
enqueue方法
// enter queue方法this.enqueue = function (element) { items.push(element)}
dequeue方法
// delete queue方法this.dequeue = function () { return items.shift()}
front()方法
// 查看前端的元素this.front = function () { return items[0]}
isEmpty方法
// 查看队列是否为空this.isEmpty = function () { return items.length == 0}
size方法
// 查看队列中元素的个数this.size = function () { return items.length}
完整的代码
我们来看一下队列完整的代码
// 自定义队列function Queue() { var items = [] // 队列操作的方法 // enter queue方法 this.enqueue = function (element) { items.push(element) } // delete queue方法 this.dequeue = function () { return items.shift() } // 查看前端的元素 this.front = function () { return items[0] } // 查看队列是否为空 this.isEmpty = function () { return items.length == 0 } // 查看队列中元素的个数 this.size = function () { return items.length }}
队列的使用
我们来简单使用一下我们封装的Queue
// 创建队列对象var queue = new Queue()// 在队列中添加元素queue.enqueue("abc")queue.enqueue("cba")queue.enqueue("nba")// 查看一下队列前端元素alert(queue.front())// 查看队列是否为空和元素个数alert(queue.isEmpty())alert(queue.size())// 从队列中删除元素alert(queue.dequeue())alert(queue.dequeue())alert(queue.dequeue())
前面, 我们实现了一种普通的队列. 队列中元素的处理顺序和插入的顺序密切相关.
但是, 还有一种比较常见的场景是和插入顺序无关, 而和元素本身的优先级有关系的队列.
这种队列就是优先级队列.
优先级队列的介绍
优先级队列的实现
实现优先级队列相对队列主要有两方面需要考虑:
优先级队列代码实现:
// 封装优先级队列function PriorityQueue() { var items = [] // 封装一个新的构造函数, 用于保存元素和元素的优先级 function QueueElement(element, priority) { this.element = element this.priority = priority } // 添加元素的方法 this.enqueue = function (element, priority) { // 1.根据传入的元素, 创建新的QueueElement var queueElement = new QueueElement(element, priority) // 2.获取传入元素应该在正确的位置 if (this.isEmpty()) { items.push(queueElement) } else { var added = false for (var i = 0; i < items.length; i++) { // 注意: 我们这里是数字越小, 优先级越高 if (queueElement.priority < items[i].priority) { items.splice(i, 0, queueElement) added = true break } } // 遍历完所有的元素, 优先级都大于新插入的元素时, 就插入到最后 if (!added) { items.push(queueElement) } } } // 删除元素的方法 this.dequeue = function () { return items.shift() } // 获取前端的元素 this.front = function () { return items[0] } // 查看元素是否为空 this.isEmpty = function () { return items.length == 0 } // 获取元素的个数 this.size = function () { return items.length }}
代码解析:
优先级队列的使用
我们来简单使用一下我们的优先级队列.
// 创建优先级队列对象var pQueue = new PriorityQueue()// 添加元素pQueue.enqueue("abc", 10)pQueue.enqueue("cba", 5)pQueue.enqueue("nba", 12)pQueue.enqueue("mba", 3)// 遍历所有的元素var size = pQueue.size()for (var i = 0; i < size; i++) { var item = pQueue.dequeue() alert(item.element + "-" + item.priority)}
击鼓传花是一个常见的面试算法题. 使用队列可以非常方便的实现最终的结果.
击鼓传花的规则
击鼓传花的实现
我们使用队列可以非常方便的实现这个代码.
封装函数
// 实现击鼓传花的函数function passGame(nameList, num) { // 1.创建一个队列, 并且将所有的人放在队列中 // 1.1.创建队列 var queue = new Queue() // 1.2.通过for循环, 将nameList中的人放在队列中 for (var i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]) } // 2.寻找最后剩下的人 while (queue.size() > 1) { // 将前num-1中的人, 都从队列的前端取出放在队列的后端 for (var i = 0; i < num; i++) { queue.enqueue(queue.dequeue()) } // 将第num个人, 从队列中移除 queue.dequeue() } // 3.获取剩下的一个人 alert(queue.size()) var endName = queue.dequeue() alert("最终留下来的人:" + endName) // 4.获取该人在队列中的位置 return nameList.indexOf(endName)}
代码验证:
// 验证结果var names = ['John','Jack','Camila','Ingrid','Carl'];var index = passGame(names, 7) // 数到8的人淘汰alert("最终位置:" + index)
画图解析上面淘汰的过程
img