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

时间:2021-01-23 11:54:31

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

码路工人 CoderMonkey

转载请注明作者与出处

1. 认识队列Queue结构

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

【JavaScript数据结构系列】03-队列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-