【JavaScript数据结构系列】03-队列Queue

2022-08-22 19:09:39

【JavaScript数据结构系列】03-队列Queue

码路工人 CoderMonkey

转载请注明作者与出处

1. 认识队列Queue结构

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

如上图所示，

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

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

2. 队列的应用

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

等。

3. 队列的实现

注：

ES6 版的代码实现请查看 npm 包 data-struct-js 代码

Github/Gitee 上都能找到

npm install data-struct-js

3.1 常用方法

与栈的比较类似

方法	描述
enqueue(element)	添加元素到队列
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) {

      return 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]

// ↑ 栈结构的数据不应该被这样修改

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

// 工具方法：深拷贝

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]=deepCopy(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 工具包 data-struct-js ，
基于 ES6 实现的 JavaScript 数据结构，
虽然这个小*很少会被使用，
也许对于初学者学习 JavaScript 会有点帮助。
只要简单 install 一下即可，感兴趣的话还可以去
GitHub / Gitee 看源码。（Star 表支持～）

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

https://github.com/CoderMonkie/data-struct-js

https://gitee.com/coder-monkey/data-struct-js

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

-end-

码农公寓

【JavaScript数据结构系列】03-队列Queue

1. 认识队列Queue结构

2. 队列的应用

3. 队列的实现

3.1 常用方法

3.2 常用方法的代码实现

3.2.1 enqueue

3.2.2 dequeue

3.2.3 front

3.2.4 isEmpty

3.2.5 size

3.2.6 clear

3.2.7 toString

3.3 下面我们测试一下

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

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

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

4.2 代码实现

相关文章