JavaScriptで償却定数時間キュー

class Queue {
    constructor() {
        this.front = [];
        this.back = [];
    }

    isEmpty() {
        return this.front.length == 0 && this.back.length == 0;
    }

    push(x) {
        this.back.push(x);
    }

    pop() {
        if(this.isEmpty()) { return undefined; }
        if(this.front.length == 0) {
            this.back.reverse();
            [this.front, this.back] = [this.back, this.front];
        }
        return this.front.pop();
    }
}

各要素ごとにreverse操作は高々1回しか行われないので償却してO(1)

github.com