用 JS 写算法时你应该知道的——数组不能当队列使用！！
theme: cyanosis
小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。
在初学 JS 时，发现数组拥有 shift()、unshift()、pop()、push() 这一系列方法，而不像 Java 或 CPP 中分别引用队列、栈等数据结构，还曾偷偷窃喜。现在想想，这都是以高昂的复杂度作为代价的QAQ。
举个例子 - BFS
一般队列的应用是在 BFS 题目中使用到。BFS（Breath First Search）广度优先搜索，作为入门算法，基本原理大家应该都了解，这里不再细说。
给你一个大小为
m x n的整数矩阵isWater，它代表了一个由 陆地 和 水域 单元格组成的地图。如果
isWater[i][j] == 0，格子(i, j)是一个 陆地 格子。 如果isWater[i][j] == 1，格子(i, j)是一个 水域 格子。 你需要按照如下规则给每个单元格安排高度：
- 每个格子的高度都必须是非负的。
- 如果一个格子是是 水域 ，那么它的高度必须为
0。- 任意相邻的格子高度差 至多 为
1。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边） 找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。请你返回一个大小为
m x n的整数矩阵height，其中height[i][j]是格子(i, j)的高度。如果有多种解法，请返回 任意一个 。
常规 BFS 题目，从所有的水域出发进行遍历，找到每个点离水域的最近距离即可。常规写法，三分钟搞定。
js
/**
* @param {number[][]} isWater
* @return {number[][]}
*/
var highestPeak = function(isWater) {
// 每个水域的高度都必须是0
// 一个格子离最近的水域的距离 就是它的最大高度
let n = isWater.length, m = isWater[0].length;
let height = new Array(n).fill().map(() => new Array(m).fill(-1));
let q = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (isWater[i][j] === 1) {
q.push([i, j]);
height[i][j] = 0;
}
}
}
let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
while (q.length) {
for (let i = q.length - 1; i >= 0; i--) {
let [x, y] = q.shift();
for (let [dx, dy] of dir) {
let nx = x + dx, ny = y + dy;
if (nx < n && nx >= 0 && ny < m && ny >= 0 && height[nx][ny] === -1) {
q.push([nx, ny]);
height[nx][ny] = height[x][y] + 1;
}
}
}
}
return height;
};
然后，超时了……
调整一下，
js
/**
* @param {number[][]} isWater
* @return {number[][]}
*/
var highestPeak = function(isWater) {
// 每个水域的高度都必须是0
// 一个格子离最近的水域的距离 就是它的最大高度
let n = isWater.length, m = isWater[0].length;
let height = new Array(n).fill().map(() => new Array(m).fill(-1));
let q = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (isWater[i][j] === 1) {
q.push([i, j]);
height[i][j] = 0;
}
}
}
let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
while (q.length) {
let tmp = [];
for (let i = q.length - 1; i >= 0; i--) {
let [x, y] = q[i];
for (let [dx, dy] of dir) {
let nx = x + dx, ny = y + dy;
if (nx < n && nx >= 0 && ny < m && ny >= 0 && height[nx][ny] === -1) {
tmp.push([nx, ny]);
height[nx][ny] = height[x][y] + 1;
}
}
}
q = tmp;
}
return height;
};
ok，这回过了，而且打败了 90% 的用户。
那么问题出在哪里呢？shift()!!!
探究 JavaScript 中 shift() 的实现
在学习 C++ 的时候，队列作为一个先入先出的数据结构，入队和出队肯定都是O(1)的时间复杂度，用链表
让我们查看下 V8 中 shift() 的源码
简单实现就是
js
function shift(arr) {
let len = arr.length;
if (len === 0) {
return;
}
let first = arr[0];
for (let i = 0; i < len - 1; i++) {
arr[i] = arr[i + 1];
}
arr.length = len - 1;
return first;
}
所以，shift() 是 O(N) 的！！！ 吐血 QAQ
同理，unshift() 也是 O(N) 的，不过，pop() 和 push() 是 O(1)，也就是说把数组当做栈是没有问题的。
我就是想用队列怎么办！
没想到作为一个 JSer，想好好地用个队列都这么难……QAQ
找到了一个队列实现，详情见注释。
```js /*
Queue.js
A function to represent a queue
Created by Kate Morley - http://code.iamkate.com/ - and released under the terms of the CC0 1.0 Universal legal code:
http://creativecommons.org/publicdomain/zero/1.0/legalcode
*/
/ Creates a new queue. A queue is a first-in-first-out (FIFO) data structure - * items are added to the end of the queue and removed from the front. / function Queue(){
// initialise the queue and offset var queue = []; var offset = 0;
// Returns the length of the queue. this.getLength = function(){ return (queue.length - offset); }
// Returns true if the queue is empty, and false otherwise. this.isEmpty = function(){ return (queue.length == 0); }
/ Enqueues the specified item. The parameter is: * * item - the item to enqueue / this.enqueue = function(item){ queue.push(item); }
/ Dequeues an item and returns it. If the queue is empty, the value * 'undefined' is returned. / this.dequeue = function(){
// if the queue is empty, return immediately
if (queue.length == 0) return undefined;
// store the item at the front of the queue
var item = queue[offset];
// increment the offset and remove the free space if necessary
if (++ offset * 2 >= queue.length){
queue = queue.slice(offset);
offset = 0;
}
// return the dequeued item
return item;
}
/ Returns the item at the front of the queue (without dequeuing it). If the * queue is empty then undefined is returned. / this.peek = function(){ return (queue.length > 0 ? queue[offset] : undefined); }
} ```
把最初代码中的数组改为 Queue，现在终于可以通过了。:)