当前位置：首页 > news >正文

JS队列之双端队列介绍

news 2026/3/26 15:34:13

首先先说它的应用场景。例如低代码平台、富文本编辑器上的重做和撤销功能。

然后进入正文：

核心比喻：一艘可以两头装卸货物的长驳船

想象一下，你有一艘很长很长的驳船，船上有很多集装箱的空位，从船头到船尾依次编号 0, 1, 2, 3, ...

普通队列 (Queue)：就像一个普通的码头，所有货物都从船尾（Back）装上船 (enqueue)，然后只能从船头（Front）卸货 (dequeue)。先进来的货物（集装箱）总是先出去，非常公平。

双端队列 (Deque)：现在，你的这艘驳船升级了！它既可以在船尾装货 (addBack)，也可以在船头装货 (addFront)。同样，卸货也既可以从船头卸 (removeFront)，也可以从船尾卸 (removeBack)。它就像一个两端都有吊机的超级驳船，操作非常灵活。

这就是双端队列的核心思想：一个允许在两端进行添加和移除操作的线性数据结构。

深入理解你的 JavaScript 代码

你的这段代码非常巧妙，它用一个普通的对象 (#items) 来模拟这艘驳船。但它有一个关键的优化，让我们来一步步拆解。

我们船上有两个重要的记录员：

#count：记录船尾下一个空位的编号。货物总是装在这个位置。

#lowestCount：记录船头第一个有货物的集装箱的编号。卸货总是从这里开始。

1. addBack(element) - 从船尾装货
code
JavaScript
download
content_copy
expand_less
addBack(element) {
this.#items[this.#count] = element;
this.#count++;
}

这是最简单的操作。就像在船尾的下一个空位（#count 指示的位置）放上一个集装箱 (element)，然后更新下一个空位的编号（#count++）。

船的状态变化：
#items = {}, #count = 0, #lowestCount = 0
addBack('A') -> #items = {0: 'A'}, #count = 1, #lowestCount = 0
addBack('B') -> #items = {0: 'A', 1: 'B'}, #count = 2, #lowestCount = 0

2. removeFront() - 从船头卸货
code
JavaScript
download
content_copy
expand_less
removeFront() {
// ... 省略空检查 ...
const result = this.#items[this.#lowestCount];
delete this.#items[this.#lowestCount];
this.#lowestCount++;
return result;
}

这里是第一个巧妙之处！我们不是把所有集装箱都往前挪一格（那样太费力了），而是直接把船头第一个集装箱 (#items[#lowestCount]) 卸掉，然后宣布：“现在新的船头是下一个位置了！” (#lowestCount++)。

船的状态变化：
#items = {0: 'A', 1: 'B'}, #count = 2, #lowestCount = 0
removeFront() -> 卸掉 'A'
#items = {1: 'B'}, #count = 2, #lowestCount = 1
注意！船头前面空出来了一个位置 0！我们并没有移动集装箱 'B'。

3. addFront(element) - 从船头装货（最关键的部分）

这是最复杂也最能体现设计思想的地方。现在要在船头加一个集装箱，有三种情况：

情况一：船是空的 (this.isEmpty())
很简单，直接当做从船尾装货就行了。

情况二：船头前面有空位 (this.#lowestCount > 0)
这是最高效的情况！因为我们之前 removeFront() 的时候，在船头留下了空位。现在正好可以利用这些空位。

code
JavaScript
download
content_copy
expand_less
} elseif (this.#lowestCount > 0) {
this.#lowestCount--;
this.#items[this.#lowestCount] = element;
}

我们把新的船头位置往前挪一格 (#lowestCount--)，然后把新货物放上去。完美利用了空间！

船的状态变化：
假设当前状态：#items = {1: 'B', 2: 'C'}, #count = 3, #lowestCount = 1 (位置0是空的)
addFront('X') ->
#lowestCount 变成 0。
#items[0] = 'X'
最终状态：#items = {0: 'X', 1: 'B', 2: 'C'}, #count = 3, #lowestCount = 0

情况三：船头前面没有空位 (else)
这是最糟糕、最费力的情况。船头（位置0）已经顶格了，没地方放了。怎么办？只能让船上所有的集装箱都往船尾方向挪一格，给船头腾出一个位置 0 来。

code
JavaScript
download
content_copy
expand_less
} else {
for (let i = this.#count; i > 0; i--) {
this.#items[i] = this.#items[i - 1]; // 所有货物往后挪
}
this.#count++;
this.#lowestCount = 0; // 船头还在0
this.#items[0] = element; // 在腾出的0号位放上新货物
}

这个操作效率很低，所以代码的设计者通过 #lowestCount 机制，尽可能地避免这种情况的发生。

双端队列的现实应用场景

为什么我们需要这么一个“超级驳船”呢？

实现撤销/重做 (Undo/Redo) 功能

场景：你在一个编辑器里写字，或者在画图软件里操作。

应用：

你每执行一个操作（比如输入文字、删除图形），就把它 addBack 到一个双端队列里。

当你点击 “撤销” (Undo) 时，就从队尾 removeBack 一个操作，并执行它的反向操作。

这个被撤销的操作怎么办？可以把它 addFront 到另一个“重做队列”里。

当你点击 “重做” (Redo) 时，就从“重做队列”里 removeFront 一个操作，并重新执行它，再把它 addBack 回原来的操作历史队列。

双端队列的灵活性在这里体现得淋漓尽致。

滑动窗口算法