Run results for: Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail

Test name	Executions per second
✓ Queue from tail	706 Ops/sec
Linked from Tail	686 Ops/sec
LinkedList deque	546 Ops/sec
Array deque	435 Ops/sec
Array deque from Tails	310 Ops/sec
Double Array enque	231 Ops/sec
Linked List enque	74 Ops/sec
Queue deque	41 Ops/sec
Queue enqeue	22 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();
  }

  dequeueFromTail() {
    return this.dequeueNodeFromTail();
  }

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  enqueueNode(value) {
    const node = {
      value,
      next: undefined,
      prev: this.tail
    };

    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;

      if (this.head) {
        this.head.prev = undefined;
      } else {
        this.tail = undefined;
      }

      this.length -= 1;
      return value;
    }

    return undefined;
  }

  dequeueNodeFromTail() {
    if (this.tail) {
      const value = this.tail.value;
      this.tail = this.tail.prev;

      if (this.tail) {
        this.tail.next = undefined;
      } else {
        this.head = undefined;
      }

      this.length -= 1;
      return value;
    }

    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();
  }

  dequeueFromTail() {
    if (this.input.length === 0) {
      this.pivot();
    }
    return this.input.pop();
  }

  pivot() {
    this.output = this.input.reverse();
    this.input = [];
  }

  isEmpty() {
    return this.input.length === 0 && this.output.length === 0;
  }
}


class Queue {
    constructor() {
        this.queue = new Map();
        this.head = 0;
        this.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;
    }
            
    dequeueFromTail() {
        if (this.head === this.tail) return;
        this.tail--;
        const value = this.queue.get(this.tail);
        this.queue.delete(this.tail);
        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++) { doubleQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }
Array deque from Tails
for(let i = 0; i < queueSize; i++) { doubleQ.dequeueFromTail() }
Linked from Tail
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeueFromTail() }
Queue from tail
for(let i = 0; i < queueSize; i++) { queue.dequeueFromTail() }

Run results for: Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail

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

Array deque from Tails

Linked from Tail

Queue from tail