JS数据结构与算法-队列结构 _生活百科

队列结构一.认识队列

受限的线性结构:
- 我们已经学习了一种受限的线性结构:栈结构.
- 并且已经知道这种受限的数据结构对于解决某些特定问题,会有特别的效果.
- 下面,我们再来学习另外一个受限的数据结构:队列.
队列(Queue)，它是一种受限的线性表,先进先出(FIFO First ln First Out)
- 受限之处在于它只允许在表的前端( front ）进行删除操作
- 而在表的后端(rear)进行插入操作
生活中类似的队列结构
- 生活中类似队列的场景就是非常多了
- 比如在电影院,商场,甚至是厕所排队.
- 优先排队的人,优先处理.(买票,结账, WC)

二.队列的应用

打印队列:
- 有五份文档需要打印,这些文档会按照次序放入到打印队列中.
- 打印机会依次从队列中取出文档,优先放入的文档，优先被取出，并且对该文档进行打印.
- 以此类推,直到队列中不再有新的文档.
线程队列:
- 在开发中,为了让任务可以并行处理,通常会开启多个线程.
- 但是,我们不能让大量的线程同时运行处理任务.(占用过多的资源)
- 这个时候,如果有需要开启线程处理任务的情况,我们就会使用线程队列.
- 线程队列会依照次序来启动线程,并且处理对应的任务.
队列如何实现呢?
- 我们一起来研究一下队列的实现.

三.队列类的创建

队列的实现和栈一样,有两种方案:
- 基于数组实现
- 基于链表实现

function Queue() {//属性this.items = []}四.队列的常见操作

队列有哪些常见的操作呢?
- enqueue(element):向队列尾部添加一个(或多个)新的项。
- dequeue()∶移除队列的第一(即排在队列最前面的)项，并返回被移除的元素。
- front():返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似) 。
- isEmpty):如果队列中不包含任何元素，返回true，否则返回false 。
- size():返回队列包含的元素个数，与数组的length属性类似。
- toString():将队列中的内容,转成字符串形式
现在，,我们来实现这些方法.
- 其实很栈中方法的实现非常相似.因为我们的队列也是基于数组的

//1.将元素加入到队列中Queue.prototype.enqueue = function (element) {this.items.push(element)}//2.从队列中删除前端元素Queue.prototype.dequeue = function () {return this.items.shift()}//3.查看前端元素Queue.prototype.front = function () {return this.items[0]}//4.查看队列是否为空Queue.prototype.isEmpty = function () {return this.items.length === 0}//5.查看队列中元素的个数Queue.prototype.size = function () {return this.items.length}//6.toString方法Queue.prototype.toString = function () {let resultString = ''for (let i = 0; i < this.items.length; i++) {resultString += this.items[i] + ''}return resultString}

五.击鼓传花