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

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	64.6 Ops/sec
Linked List enque	28.2 Ops/sec
Queue enqeue	20.0 Ops/sec
Array deque	66.1 Ops/sec
LinkedList deque	30.3 Ops/sec
Queue deque	34.8 Ops/sec
Array deque from Tails	60.6 Ops/sec
Linked from Tail	31.8 Ops/sec
Queue from tail	68.9 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