# 03-队列Queue

# 1. 认识队列Queue结构

队列，跟我们的日常生活非常贴近，我们前面举例了食堂排队打饭的例子，我们继续用这个例子来说明。

如上图所示，

第一个加入队列的为队列头
最后一个为队列尾
FIFO：先进先出，后进后出的原则
添加删除操作：只能添加到队尾，只能删除队列头

去银行办业务要先取号，然后等待叫号，一样一样的。
（银行也有VIP，后面我们讲优先队列）

# 2. 队列的应用

JavaScript事件队列
图的广度优先遍历中使用队列
打印时的打印任务队列

等。

# 3. 队列的实现

# 3.1 常用方法

与栈的比较类似

方法	描述
enqueue	添加元素到队列
dequeue	删除队列元素
front	查看当前队列头元素
isEmpty	检查是否为空队列
size	检查队列容量
clear	清空队列
toString	字符串化

# 3.2 常用方法的代码实现

队列也是线性结构，下面我们基于数组来实现一下它的常用方法。

首先，写出 Queue 的构造函数

function Queue() {
  this.__items = []
}

# 3.2.1 enqueue

实现分析：用push向队列添加元素

function Queue() {
  this.__items = []
  
  Queue.prototype.enqueue = function (element) {
      this.__items.push(element)
  }
}

# 3.2.2 dequeue

实现分析：用shift删除队列排头元素

function Queue() {
  this.__items = []
  
  Queue.prototype.dequeue = function () {
    return this.__items.shift()
  }
}

# 3.2.3 front

实现分析：查看队列头即数组第一个元素

function Queue() {
  this.__items = []
  
  Queue.prototype.front = function () {
    return this.__items.length === 0 ? undefined : this.__items[0]
  }
}

# 3.2.4 isEmpty

实现分析：只要看内部数组元素个数是否为0

function Queue() {
  this.__items = []
  
  Queue.prototype.isEmpty = function () {
      return __items.length === 0
  }
}

# 3.2.5 size

实现分析：返回内部数组元素个数

function Queue() {
  this.__items = []
  
  Queue.prototype.size = function () {
      return this.__items.length
  }
}

# 3.2.6 clear

实现分析：只要看元素个数是否为0

function Queue() {
  this.__items = []
  
  Queue.prototype.clear = function () {
      this.__items.length = 0
  }
}

# 3.2.7 toString

实现分析：将内部数组用 join 连结

function Queue() {
	this.__items = []
  
  Queue.prototype.toString = function() {
    return this.__items.join(',')
  }
}

实现完了，总结如下：

function Queue() {
  this.__items = []

  Queue.prototype.enqueue = function (element) {
    this.__items.push(element)
  }

  Queue.prototype.dequeue = function () {
    return this.__items.shift()
  }

  Queue.prototype.front = function () {
    return this.__items.length === 0 ? undefined : this.__items[0]
  }

  Queue.prototype.isEmpty = function () {
    return this.__items.length === 0
  }

  Queue.prototype.size = function () {
    return this.__items.length
  }

  Stack.prototype.clear = function () {
    this.__items.length = 0
  }

  Queue.prototype.toString = function () {
    return this.__items.join(' ')
  }
}

# 3.3 下面我们测试一下

// ---------------------------------------------
// Test: Queue
// ---------------------------------------------
var q = new Queue()
for (var i = 0; i < 5; i++) {
    q.enqueue(i)
}
console.log('isEmpty: ', q.isEmpty())
console.log('size: ', q.size())
console.log('toString: ', q.toString())
while (!q.isEmpty()) {
    console.log(`dequeue: `, q.dequeue())
}
console.log('isEmpty: ', q.isEmpty())
console.log('size: ', q.size())

// 打印结果：
// isEmpty:  false
// size:  5
// toString:  0 1 2 3 4
// dequeue:  0
// dequeue:  1
// dequeue:  2
// dequeue:  3
// dequeue:  4
// isEmpty:  true
// size:  0

我们得到了符合预期的结果。

# 4. 思考题：基于栈结构的队列实现

# 4.1 栈与队列的顺序原则是相反的，如何用栈实现上面的队列？

学完了 Stack 和 Queue这两个常用的典型数据结构，
让我们暂时放慢攀登的脚步，缓缓消化一下：
这时候正合适练习一下，在使用中加深对这两个数据结构的理解，
发现我们实现的代码中，还要哪些问题，哪些地方可以改善。

在解答之前，让我们先对之前的栈稍做改进。

回想一下，我们实现的栈结构常用方法中，还欠缺什么？

不能获取元素集合
没有办法遍历集合

# 4.1.1 对已实现的栈结构的改进

添加获取元素集合的方法

Stack.js

function Stack() {
  this.__items = []
  // ...
  Stack.prototype.getItems = function() {
    return this.__items
  }
}

这样，是实现了，但是，这里返回 __items 在简单类型时值传递没有问题，复杂类型时，返回的引用使外部可以对其进行修改，这就不符合我们栈的要求了。

// 错误结果示例：
var s = new Stack()
s.push(22)
s.push(33)
console.log(s)				// => [22, 33]
var items = s.getItems()
items[0] = 11
console.log(s)				// => [11, 33]
// ↑ 栈结构的数据不应该被这样修改

获取元素集合的改进
这里应该使用深拷贝的，我们来简单实现一下
这样的工具方法积累多了你可以写一个如underscore.js这样的库了

// 工具方法：深拷贝
function deepCopy(source) {
  var dest
  if(Array.isArray(source)) {
    dest = []
    for (let i = 0; i < source.length; i++) {
      dest[i] =deepCopy(source[i])
    }
  }
  else if(toString.call(source) === '[object Object]') {
    dest = {}
    for(var p in source){
      if(source.hasOwnProperty(p)){
        dest[p]=source[p]
      }
    }
  }
  else {
    dest = source
  }
  return dest
}

Stack.js

Stack.prototype.getItems = function() {
  this.__items = []
  // ...
  Stack.prototype.getItems = function() {
    return deepCopy(this.__items)
  }
}

测试一下：

// 正确结果示例：
var s = new Stack()
s.push(22)
s.push(33)
console.log(s)				// => [22, 33]
var items = s.getItems()
items[0] = 11
console.log(s)				// => [22, 33]
// ↑ 栈结构的数据未被修改

遍历集合

Stack.js

这里遍历时使用上面刚添加的 getItems 方法，在回调中传入集合元素副本

Stack.prototype.traverse = function (cb) {
  if (!cb || toString.call(cb) !== '[object Function]') return

  var items = this.getItems()
  for (var index = items.length - 1; index >= 0; index--) {
    var element = items[index];
    cb(element, index)
  }
}

同理，可以给队列 Queue 添加以上两个方法（获取集合的getItems方法和遍历的traverse方法），你可以试试呀

下面我们就去完成基于栈结构的队列实现。

# 4.2 代码实现

实现分析：栈与队列的顺序原则刚好是相反的，要用栈实现队列，就需要两个栈，一个放传入的元素，一个放调整顺序后准备出队的元素。

__inStack ：用于入队
__outStack ：用于出队
入队时：直接入队， push 进 __inStack
出队时：出队集合__outStack中有元素则直接出队，没有的话将 __inStack 中的元素倒过来

function QueueBasedOnStack() {

  this.__inStack = new Stack()
  this.__outStack = new Stack()

  QueueBasedOnStack.prototype.enqueue = function(element) {
    this.__inStack.push(element)
  }

  QueueBasedOnStack.prototype.dequeue = function() {
    if(this.__outStack.isEmpty()) {
      while(!this.__inStack.isEmpty()) {
        this.__outStack.push(this.__inStack.pop())
      }
    }
    return this.__outStack.pop()
  }

  QueueBasedOnStack.prototype.size = function() {
    return (this.__inStack.size() + this.__outStack.size())
  }

  QueueBasedOnStack.prototype.isEmpty = function() {
    return this.__inStack.size() === 0 && this.__outStack.size() === 0
  }

  QueueBasedOnStack.prototype.clear = function() {
    this.__inStack.clear() 
    this.__outStack.clear()
  }

  QueueBasedOnStack.prototype.toString = function() {
    var items = this.getItems()
    return items.join('--')
  }

  QueueBasedOnStack.prototype.getItems = function() {
    return this.__inStack.getItems().concat(this.__outStack.getItems().reverse())
  }
}

测试一下

// ---------------------------------------------
// Test: QueueBasedOnStack
// ---------------------------------------------
console.log('----Test: QueueBasedOnStack----')

var qs = new QueueBasedOnStack()
qs.enqueue('A')
console.log('after enqueue: ', qs.toString())
qs.enqueue('B')
console.log('after enqueue: ', qs.toString())
qs.enqueue('C')
qs.enqueue('D')
qs.enqueue('E')
console.log('after enqueue: ', qs.toString())
qs.dequeue()
console.log('after dequeue: ', qs.toString())
qs.dequeue()
console.log('after dequeue: ', qs.toString())
qs.dequeue()
console.log('after dequeue: ', qs.toString())

查看结果：

----Test: QueueBasedOnStack----
after enqueue:  A
after enqueue:  A--B
after enqueue:  A--B--C--D--E
after dequeue:  B--C--D--E
after dequeue:  C--D--E
after dequeue:  D--E

收工。

文章中的代码实现能让我们更简单地弄清楚我们要讲的数据结构，
不同于文章中的代码实现，我还做了一份 npm 工具包，
基于ES6，只要简单 install 一下即可。
感兴趣的话还可以去 GitHub / Gitee 看源码。（来 Star 一下嘛）

npm install data-struct-js --save-dev

最后，感谢您的阅读和支持~

-end-

← 02-栈Stack 04-优先队列PriorityQueue →

~扫码关注<码路工人>了吗？~

~关注公众号可以第一时间获取最新文章~

~扫码关注可以联系交流~