2025-04-12
Dequeを作ろう
両端キュー - Wikipedia
JavaScriptのArrayはshiftとunshiftを持つためDequeとしても使えると誤解しがちですが、実際はただのスタックなので配列の長さに比例した時間がかかります。紛らわしいですね。
というわけで、ちゃんとO(1)1でpop_frontとpush_frontができるDequeを作ります。
実装
リングバッファを使う方法で行きます。
class Deque {
constructor() {
this.head = 0;
this.tail = -1;
this.length = 0;
this.body = [];
}
get capacity() {
return this.body.length;
}
get(i) {
if (!(0 <= i && i < this.length)) return;
return this.body[(this.head + i) % this.capacity];
}
set(i, val) {
if (!(0 <= i && i < this.length)) return;
this.body[(this.head + i) % this.capacity] = val;
}
grow() {
const newCapacity = this.capacity === 0 ? 4 : this.capacity * 2;
const newBody = [];
for (let i = 0; i < newCapacity; i++) {
if (i < this.length) {
newBody.push(this.body[(this.head + i) % this.capacity]);
} else {
newBody.push(undefined);
}
}
this.head = 0;
this.tail = this.length - 1;
this.body = newBody;
}
pushFront(val) {
if (this.length === this.capacity) this.grow();
this.head -= 1;
this.body[this.head] = val;
this.length += 1;
}
popFront() {
const val = this.body[this.head];
this.body[this.head] = undefined;
this.head = (this.head + 1) % this.capacity;
return val;
}
pushBack(val) {
if (this.length === this.capacity) this.grow();
this.tail += 1;
this.body[this.tail] = val;
this.length += 1;
}
popBack() {
const val = this.body[this.tail];
this.body[this.tail] = undefined;
this.tail = (this.tail - 1 + this.capacity) % this.capacity;
return val;
}
*[Symbol.iterator]() {
for (let i = 0; i < this.length; i++) yield this.get(i);
}
}
こんな感じ。
ただ、これだとインデックスアクセスができないので少し不便です。というわけで、Proxyのget・setトラップを使ってできるようにしてやります。
今回は継承を使ってますが、普通に元のconstructorに付け足すだけでも十分です。
class Deque2 extends Deque {
constructor() {
super();
return new Proxy(this, {
get: (target, p) => {
if (
typeof p === "string" &&
!isNaN(p) &&
Number.isInteger(+p)
) {
const i = Number(p);
return target.get(i);
} else {
return target[p];
}
},
set: (target, p, val) => {
if (
typeof p === "string" &&
!isNaN(p) &&
Number.isInteger(+p)
) {
const i = Number(p);
target.set(i, val);
} else {
target[p] = val;
}
},
});
}
}
Number.isNaN
ではなくisNaN
であることに注意。isNaN(string)
はstring
が数値として解釈できるとき以外は全てNaN
と判定するのでそれを利用しています。
まとめ
もっと便利に使いたかったら[Symbol.iterator]
とかflatMap
とかも生やすといいと思います。
さあ、リングバッファでみんなも楽しい双方向配列ライフを送ろう!
脚注
-
償却計算量 ↩