Run results for: Linked List Queue vs Double Array Queue vs Queue with Map v3

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/114.0.0.0 YaBrowser/23.7.0.2564 Yowser/2.5 Safari/537.36

Browser: Yandex Browser 23

Operating system: Mac OS X 10.13.6

Device Platform: Desktop

Date tested: one year ago

Test name	Executions per second
Double Array enque	61.1 Ops/sec
Linked List enque	19.7 Ops/sec
Queue enqeue	19.1 Ops/sec
Array deque	34.1 Ops/sec
LinkedList deque	20.1 Ops/sec
Queue deque	29.6 Ops/sec

Script Preparation code:

class LinkedListQueue {
  constructor() {
    this.length = 0;
    this.head = undefined;
    this.tail = undefined;
  }

  enqueue(value) {
    this.enqueueNode(value);
  }

  dequeue() {
    return this.dequeueNode();
  }

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  enqueueNode(value) {
    const node = {
      value,
      next: undefined
    };

    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length += 1;
  }

  dequeueNode() {
    if (this.head) {
      const value = this.head.value;
      this.head = this.head.next;
      this.length -= 1;
      return value;
    }

    this.tail = undefined;
    return undefined;
  }
}


class DoubleArrayQueue {
  constructor() {
    this.input = [];
    this.output = [];
  }

  enqueue(element) {
    this.input.push(element);
  }

  dequeue() {
    if (this.output.length === 0) {
      this.pivot();
    }
    return this.output.pop();
  }

  pivot() {
    this.output = this.input.reverse();
    this.input = [];
  }

  isEmpty() {
    return this.input.length === 0 && this.output.length === 0;
  }
}


class Queue {
    #queue = new Map()
    #head = 0
    #tail = 0

    enqueue(item) {
        this.#queue.set(this.#tail, item)
        this.#tail++
    }

    dequeue() {
        if (this.#head === this.#tail) return;

        const value = this.#queue.get(this.#head)
        this.#queue.delete(this.#tail)
        this.#head++

        return value
    }

    size() {
        return this.#tail - this.#head
    }
}

var doubleQ = new DoubleArrayQueue()
var linkedListQ = new LinkedListQueue()
var queue = new Queue()
var queueSize = 100000

Tests:

Double Array enque
for(let i = 0; i < queueSize; i++) { doubleQ.enqueue(i) }
Linked List enque
for(let i = 0; i < queueSize; i++) { linkedListQ.enqueue(i) }
Queue enqeue
for(let i = 0; i < queueSize; i++) { queue.enqueue(i) }
Array deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }

Run results for: Linked List Queue vs Double Array Queue vs Queue with Map v3

Testing a linked list queue vs a double list queue vs Queue with Map for different performance scenarios.

Double Array enque

Linked List enque

Queue enqeue

Array deque

LinkedList deque

Queue deque