Javascript での、両端キュー (deque) の実装

Share

大した理由があるわけでもないのだけど、最近たまにJavascriptを触っている。いや、もちろん仕事などとは全く関係ない。趣味の話である。

その時に気づいたのだけど、どうやらJavascriptには、標準でキューが用意されていないらしい。正確には、Array.shift() などを用いればそれっぽい動作はできるのだが、内部動作的には配列を動かしているだけで、計算量も\(O(N)\)となり、きちんと実装されたキューとは言えないだろう。

キューが無いと、典型的なところでは、BFSを行おうとしたりする際に困る。というわけで、せっかくなので01-BFSなどで使用できるように、両端キューを実装してみることにした。

両端キューの実装方法にはいくつかあるが、ここでは配列を2つ用いた簡便な方法と、双方向リンクリストを用いた真面目な実装の二種類を作ってみた。

といっても、特に参考文献なども使用せず「こんな仕組みらしい」という聞きかじりからいきなり実装しているので、誤っていたり、効率の悪い実装などが入っている可能性がある。見つけたら、遠慮なくお知らせいただきたい。

// 配列を2つ使用しての両端キューの実装。
// どちらかの方向に偏るとそちら側の配列が際限なく伸びるので、
// 長期運用には使用しないほうがいい。
// でも、競技プログラミングならこれでいいでしょ……みたいな。
// 存在しない値を取得しようとすると、エラーではなく
// undefined を返すので注意。

class deque {
    // コンストラクタ。
    // 何も渡さなければ要素数 0 で初期化し、
    // 配列を渡せばそれを用いて初期化する。
    constructor(arr) {
        this.dualArray = [[], []];
        this.offset = 0;
        this.length = 0;
        if (arr instanceof Array && arr.length > 0) {
            for (value of arr) {
                this.push(value);
            }
        }
    }

    // 渡されたインデックスから、内部動作上のインデックスを返す関数。
    // [1, x] なら右側の配列、[0, x] なら左側の配列とする。
    getIndex(pos) {
        if (pos +  this.offset >= 0) {
            return [1, pos + this.offset];
        } else {
            return [0, -(pos + this.offset)-1];
        }
    }

    // value を右端に追加
    push(value) {
        let [lr, idx] = this.getIndex(this.length);
        if (lr === 0) {
            this.dualArray[lr][idx] = value;
            this.length += 1;
        } else {
            this.dualArray[lr].push(value);
            this.length += 1;
        }
    }

    // value を左端に追加
    pushLeft(value) {
        let [lr, idx] = this.getIndex(-1);
        if (lr === 0) {
            this.dualArray[lr].push(value);
            this.offset -= 1;
            this.length += 1;
        } else {
            this.dualArray[lr][idx] = value;
            this.offset -= 1;
            this.length += 1;
        }
    }

    // 右端の要素を削除し、値を返す
    pop() {
        if (this.length === 0) {
            return undefined;
        }
        let [lr, idx] = this.getIndex(this.length-1);
        if (lr === 0) {
            this.length -= 1;
            return this.dualArray[lr][idx];
        } else {
            this.length -= 1;
            return this.dualArray[lr].pop();
        }
    }

    // 左端の要素を削除し、値を返す
    popLeft() {
        if (this.length === 0) {
            return undefined;
        }
        let [lr, idx] = this.getIndex(0);
        if (lr === 0) {
            this.offset += 1;
            this.length -= 1;
            return this.dualArray[lr].pop();
        } else {
            this.offset += 1;
            this.length -= 1;
            return this.dualArray[lr][idx]
        }
    }

    // 指定したインデックスの値を取得する。
    get (pos) {
        if (pos < 0) {
            pos = this.length + pos;
        }
        if (pos < 0 || this.length <= pos) {
            return undefined;
        }
        let[lr, idx] = this.getIndex(pos);
        return this.dualArray[lr][idx];
    }
}
// 双方向連結リストによる、両端キューの実装。
// 学習の一環として作成。
// 実際のところ早くない……が、長期運用にも耐える構造のはず。
// 存在しない値を取得しようとすると、エラーではなく undefined を
// 返すので注意。

// 両端キュー用ノードのクラス
class dequeNode {
    constructor(value) {
        this.left = null;
        this.right = null;
        this.value = value;
    }
}

class deque {
    // コンストラクタ。
    // 何も渡さなければ、要素数 0 にて初期化のみ行い、
    // Array を渡せば、それを用いて初期化する。
    constructor(arr) {
        this.root = new dequeNode(null);
        this.root.left = this.root;
        this.root.right = this.root;
        this.length = 0;
        if (arr instanceof Array && arr.length > 0) {
            for (let value of arr) {
                this.push(value);
            }
        }
    }

    // 参照ノードの左側に値を追加し、追加した要素の参照を返す
    insertLeft(ref, value) {
        if (!ref instanceof dequeNode) {
            return undefined;
        } else {
            const obj = new dequeNode(value);
            ref.left.right = obj;
            obj.left = ref.left;
            ref.left = obj;
            obj.right = ref;
            this.length += 1;
            return obj;
        }
    }

    // 参照ノードの右側に値を追加し、追加した要素の参照を返す
    insertRight(ref, value) {
        if (!ref instanceof dequeNode) {
            return undefined;
        } else {
            const obj = new dequeNode(value);
            ref.right.left = obj;
            obj.right = ref.right;
            ref.right = obj;
            obj.left = ref;
            this.length += 1;
            return obj;
        }
    }

    // 右端に値を追加し、追加した要素の参照を返す
    push(value) {
        return this.insertLeft(this.root, value);
    }

    // 左端に値を追加し、追加した要素の参照を返す
    pushLeft(value) {
        return this.insertRight(this.root, value);
    }

    // 右端の要素を削除し、その値を返す
    pop() {
        if (this.length === 0) {
            return undefined;
        } else {
            const result = this.root.left.value;
            this.root.left.left.right = this.root;
            this.root.left = this.root.left.left;
            this.length -= 1;
            return result;
        }
    }

    // 左端の要素を削除し、その値を返す
    popLeft() {
        if (this.length === 0) {
            return undefined;
        } else {
            const result = this.root.right.value;
            this.root.right.right.left = this.root;
            this.root.right = this.root.right.right;
            this.length -= 1;
            return result;
        }
    }

    // 左から pos-1 番目の値を取得する
    get(pos) {
        if (pos < 0) {
            pos = this.length + pos;
        }
        if (pos >= this.length) {
            return undefined;
        }

        // 一応近い方から数えるように……。
        if (pos < this.length / 2) {
            let nd = this.root.right;
            for (let i = 0; i < pos; i++) {
                nd = nd.right;
            }
            return nd.value;
        } else {
            let nd = this.root.left;
            for (let i = 0; i < this.length - pos - 1; i++) {
                nd = nd.left;
            }
            return nd.value;
        }
    }
}
Share

コメントを残す

メールアドレスが公開されることはありません。