2025-04-12

Dequeを作ろう

両端キュー - Wikipedia
両端キュー - Wikipedia favicon ja.wikipedia.org

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とかも生やすといいと思います。

さあ、リングバッファでみんなも楽しい双方向配列ライフを送ろう!

脚注

  1. 償却計算量

© 2025 banakna_79