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

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	6057.7 Ops/sec
Linked List enque	2741.1 Ops/sec
Queue enqeue	2089.2 Ops/sec
Array deque	3609.3 Ops/sec
LinkedList deque	1949.5 Ops/sec
Queue deque	3510.1 Ops/sec

Script Preparation code:

function createLinkedListQueue() {
	let length = 0
	let head = undefined
	let tail = undefined
	return {
		enqueue(value) {
			enqueueNode(value)
		},
		dequeue() {
			return dequeueNode()
		},
		size() {
			return length
		},
		head() {
			return head
		},
		tail() {
			return tail
		}
	}
	function enqueueNode(value) {
		const node = {
			value,
			next: undefined 
		}
		if(!head) {
			head = node
			tail = node
		}
		else {
			tail.next = node
			tail = node
		}
		length += 1	
	}
	function dequeueNode() {
		if(head) {
			const value = head.value
			head = head.next
			length -= 1
			return value
		}
		tail = undefined
		return undefined
	}
}

function createDoubleArrayQueue() {
	return {
		input: [],
		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 = createDoubleArrayQueue()
var linkedListQ = createLinkedListQueue()
var queue = new Queue()
var queueSize = 1000

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

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