先记住这个答案
数组元素是按索引连续存放的。push 和 pop 只动末尾,前面的元素位置都不用变,通常是 O(1)。shift 删掉第一个元素后,剩下的每个元素索引都要减 1;unshift 在开头插入,每个元素索引都要加 1,所以是 O(n),数组越长越慢。用数组当队列时,如果每次出队都 shift,处理 n 个元素总共就是 O(n²)。数据量大时,可以用一个游标记住队头的位置,出队只移动游标。
- 尾部增删通常是
O(1),头部增删是O(n) - 加元素的返回新长度,删元素的返回被删元素
- 大量出队不要反复
shift,用游标记录队头 - 四个方法都会修改原数组
先把四个方法的返回值分清
性能之外,面试还常考这四个方法返回什么,很多人会记混。
const head = ['B', 'C']
console.log(head.unshift('A')) // 返回新长度
console.log(head.shift()) // 返回被移除的元素
console.log(JSON.stringify(head))
const tail = ['A', 'B']
console.log(tail.push('C')) // 返回新长度
console.log(tail.pop()) // 返回被移除的元素
console.log(JSON.stringify(tail))查看输出与解释
3
A
["B","C"]
3
C
["A","B"]规律很好记:加元素的 push 和 unshift 返回新长度,删元素的 pop 和 shift 返回删掉的那个元素。四个方法都直接修改原数组,没有一个返回新数组,所以不能写成 arr.push(1).map(...)。
为什么头部操作更慢
可以把数组想成电影院里的一排座位,每个人坐在编了号的座位上。散场时最后一个人离开,其他人不用动,这是 pop。如果坐在 1 号位的人离开,还要求座位从 1 号开始连续坐满,后面的人就得每人往前挪一个座位,这就是 shift。人越多挪得越久。
- 用游标代替反复
shift - 处理消息队列、做 BFS 广度优先遍历时,经常要不断从队头取元素。用一个
head变量记住当前队头的索引,出队时读queue[head]再让head加 1,元素不用挪,每次出队都是O(1)。 游标方案有一个代价:已经出队的元素还留在数组里,占着内存。长期运行的队列要定期清理,比如head超过数组一半长度时,用queue = queue.slice(head)丢掉前面的部分,再把head归零。这些都是在数据量真的大时才值得做的优化,几百个元素的数组直接shift完全没问题。
容易答错的地方
- 说每次
push都一定是O(1) - 数组底层会预留一些空间,空间用完时引擎要申请更大的空间并把数据搬过去,那一次
push是O(n)。因为扩容不是每次都发生,平均摊到每次操作上还是常数时间,所以准确的说法是摊还O(1)。 - 以为引擎会把
shift优化成O(1) - 有些引擎对特定情况做了优化,小数组上可能感觉不到差别,但语言规范没有这种保证。回答时说「按规范语义
shift需要移动后续元素,通常按O(n)估算,实际性能要在目标环境里测」最稳妥。
面试官还会怎么问?
空数组调用 pop 或 shift 会报错吗?
不会报错,返回 undefined,长度还是 0。所以如果队列里本身可能存 undefined,不能只靠返回值判断队列是否为空,要看 length。
unshift(1, 2) 和先 unshift(1) 再 unshift(2) 结果一样吗?
不一样。一次传多个参数时,它们按传入顺序整体放到开头,结果是 [1, 2, ...];分两次调用时,后插入的在最前面,结果是 [2, 1, ...]。
需要两头都频繁增删时用什么?
可以实现一个双端队列,用环形缓冲区加头尾两个指针,两头增删都是 O(1)。前端业务里真需要这个的场景不多,先确认数组确实是性能瓶颈再动手。
参考资料
示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。