Queue with O(1) enqueue and dequeue with JS arrays

Question

If you simply implement it with .push() to .enqueue() and .shift() to .dequeue() that's easy but the the time complexity of .enqueue() is O(1) and .dequeue() is O(n).

While still using arrays, I have come come up with a nice solution to make both .enqueue() and .dequeue() in O(1). I am using sparse arrays. It turns out to be super efficient but only when the Queue size is larger than 25000. My benchmarks are like this;

Queue size 100
Queue: 0.12999999523162842
Array: 0.03999999910593033

Queue size 1000
Queue: 1.1049999967217445
Array: 0.5250000059604645

Queue size 10000
Queue: 3.0750000029802322
Array: 1.7799999937415123

Queue size 100000
Queue: 13.944999992847443
Array: 887.390000000596

OK Queue becomes much faster than Array as the size grows but i can not tell what to improve so that Queue doesn't fall behind Array at smaller scales. Is there anything that you can suggest in the below code?

class Queue extends Array {
  constructor(){
    super();
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0;
  }
  peek() {
    return this[this.head];
  }
}

var p = Array(100000).fill().map(_ => ~~(Math.random()*1000)),
    q = p.reduce((r,e) => r.enqueue(e), new Queue());

var s,e;

s = performance.now();
for (i=0; i < 100000; i++){
  q.dequeue();
}
e = performance.now();
console.log("Queue:", e-s);

s = performance.now();
for (i=0; i < 100000; i++){
  p.shift();
}
e = performance.now();
console.log("Array:", e-s);

Edit: After some research, now i understand that what many of us have been told is in fact not correct. .shift() is not O(n). It's been optimized to O(1) many years ago and i think last ones to optimize were the Firefox guys in 2017. Here the guys are discussing how to implement the optimization and it turns they do a very similar thing to what i implemented here. Unlike me, they just skip the "delete out the dequeued item" part since they write it in C++ and can move the pointer (head in above code) by leaving out freed spaces to GC. But in JS we have to delete them either in each .dequeue() operation or wait for (this.length - this.head) > 50000 and make a .splice(0,this.head) in order to prevent memory leak. This is inline with what i see with Chrome and new Edge (Chromium). Up until 50000 items .shift() works O(1) but then they switch to non optimized code. In Firefox this seems to be not the case as mentioned in a developer's comment.

Verdict: You may safely and simply implement efficient Queues with .push() and .shift().

Answer 1

Review

I find your indentations and line breaks rather difficult to read.

Object.defineProperty(this,"head",{ value   : 0
                                  , writable: true
                                  });

I would suggest you use the idiomatic style.

After { move to the next line and indent once. Place the comma at the end of lines and spaces after commas if not at end of line

Object.defineProperty(this, "head", { 
    value: 0,
    writable: true
});

or if the line is short

Object.defineProperty(this, "head", {value: 0, writable: true});

or

Object.defineProperty(
    this, 
    "head", { 
        value: 0,
        writable: true
    }
);

Same again with the ternary.

return this.head < this.length ? ( first = this[this.head]
                                 , delete this[this.head++]
                                 , first
                                 )
                               : void 0;

Why use the operator void that requires the additional expression 0 when you can just express undefined.

I understand the reasoning for breaking up the group, but the indent is way to great. The idiomatic style is far more readable.

return this.head < this.length ? ( 
        first = this[this.head],
        delete this[this.head++],
        first
    ) :                       
    undefined;                           

or

return this.head < this.length ?
    (first = this[this.head], delete this[this.head++], first) :                       
    undefined; 

Unsafe encapsulation

Extending the Array with the behaviors enqueue and dequeue is just asking for bugs as any of the existing functions can damage state.

Rules of code: "If it is there it will be used."

Good code enforces the rules by not exposing properties and behaviors that can damage state.

Even just the basic use of Queue is un-trusted because you expose head.

JS Queue

Complexity and performance are two side of the same coin. Though linked they are vastly difference. With shift at \$O(1)\$ its performance is still 10 times slower than pop

However you use delete to remove items. Again it is \$O(1)\$ but it is even slower than shift.

Linked list

I have found that a simple linked list is the most effective and performant solution for a queue in JS

Implementing it as a factory function allows closure to hold its state safely isolated from the code using the queue.

function Queue() {
    var head, tail;
    return Object.freeze({     
        enqueue(value) { 
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}

This style offers robust encapsulation, maintains the ideal \$O(1)\$ for enqueue and dequeue without sacrificing performance.

Test

The test compares the execution time of your Queue against a linked list version of a queue.

There are two test cycles, First for 1000 items, then when done click the button for 500,000 items.

I Have made minor changes to your code to favor performance. Not using define property and not returning the array in enqueue.

var size = 1000;
const COOL = 200;

class Queue extends Array {
  constructor(){
    super();
    this.head = 0;
  }
  enqueue(x) { this.push(x) }
  dequeue() {
    var first;
    return this.head < this.length ? 
        (first = this[this.head] , delete this[this.head++] , first) : 
        void 0;
  }
  peek() { return this[this.head] }
}

function QueueLinked() {
    var head, tail;
    return Object.freeze({     
        enqueue(value) { 
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}


function fillQueue(queue, count = size) {
    while (count--) { queue.enqueue(count) }
    return queue;
}
function testOPQueue() {
    const q = fillQueue(new Queue());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}
function testLinkedQueue() {
    const q = fillQueue(QueueLinked());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}

if (testOPQueue() !== testLinkedQueue()) { throw new Error("Test results differ") }

const funcTest = (name, call, bias = 1) => ({name, call, time: 0, cycles: 0, bias});

timeFunctions(50, 500, "1000 items:",
    funcTest("Array Queue", testOPQueue),
    funcTest("Linked Queue", testLinkedQueue),
).then(() => {
    test2.classList.remove("hide");
    test2.addEventListener("click", () => {
        test2.classList.add("hide");
        size = 500000;
        timeFunctions(50, 3, "500,000 items:",
            funcTest("Array Queue", testOPQueue),
            funcTest("Linked Queue", testLinkedQueue),
        );
    });
});


function timeFunctions(testCount, cycles, name, ...functions) {
    return new Promise(done => {
        const testGroup = () => {
            var i;
            for (const func of functions) {
                i = cycles;
                const now = performance.now();
                while (i--) { func.call() }
                func.time += performance.now() - now;
                func.cycles += cycles;
            }
        }
        const test = () => {
            testGroup();
            console.clear();
            console.log(name + " " + (testCount - count + 1) + " of " + testCount);
            for (const func of functions) {
                console.log(
                    func.name.padEnd(maxNameLen + 2,".") + ": " + 
                    (((func.time / func.cycles) / func.bias).toFixed(3) + "ms").padStart(9," ") +
                    (" Total: " + func.time.toFixed(3) + "ms") 
                );
            }
            if (--count) { setTimeout(test, COOL) }
            else { done() }
        }
        var count = testCount;
        var maxNameLen = 0
        for (const func of functions) {
            func.time = 0;
            func.cycles = 0;
            maxNameLen = Math.max(maxNameLen, func.name.length);
        }
        setTimeout(test, COOL);
    });
}

.hide { display: none }

<button id="test2" class="hide">Test 500000 items</button>

Answer 2

After thinkering a while, I really liked BlindMan67's answer except for the indentation part. This self answer is here just to show how we can use the Class abstraction to achieve a similar Queue implementation. Perhaps we can do better with modern JS while still being in the realm of Chrome v74 or Node 12.0. I mean the private instance fields.

I think this might be considered somewhat better since now you have enqueue, dequeue and peek as prototype inherited functions, you may add more to them as you wish and for some reason you may even extend this type. The performance is not second to his good solution. Here it is;

class Queue {
  #HEAD;
  #LAST;
  constructor(){
    this.#HEAD;
    this.#LAST;
  };
  enqueue(value){
    var link = {value, next: void 0};
    this.#LAST = this.#HEAD ? this.#LAST.next = link
                            : this.#HEAD      = link;
  }
  dequeue(){
    var first;
    return this.#HEAD && ( first = this.#HEAD.value
                         , this.#HEAD = this.#HEAD.next
                         , first
                         );
  }
  peek(){
    return this.#HEAD && this.#HEAD.value;
  }
};

I forgot to mention that the tail name wouldn't be my first preference as i happen to understand it like representing all those items following the head. (Haskell terminology) so my choice here is #LAST.