Preparation Code Preparation HTML (this will be inserted in the <body> of a valid HTML5 document in standards mode)
Setup JS class ArrayQueue {
constructor (capacity ) {
if (capacity === undefined ) {
this .array = [];
} else {
this .array = new Array (capacity);
}
}
push (element ) {
this .array .push (element);
}
shift (return this .array .shift ();
}
}
class LinkedListQueue {
constructor (this .head = { previous : undefined };
this .tail = { next : this .head };
this .head .previous = this .tail ;
}
push (element ) {
const newEntry = { previous : this .tail , next : this .tail .next , element : element };
this .tail .next .previous = newEntry;
this .tail .next = newEntry;
}
shift (const currentHead = this .head .previous ;
if (currentHead === this .tail ) {
throw new Error ('Queue is empty' );
}
this .head .previous = currentHead.previous ;
this .head .previous .next = currentHead.next ;
return currentHead.element ;
}
}
class CircularQueue {
headIndex = 0 ;
tailIndex = 0 ;
length = 0 ;
constructor (capacity ) {
if (Math .log2 (capacity) % 1 !== 0 ) {
throw new Error ('Capacity must be a power of two' );
}
this .capacity = capacity;
this .capacityBitmask = capacity - 1 ;
this .array = new Array (capacity);
}
push (element ) {
if (this .length >= this .capacity ) {
throw new Error ('Capacity exceeded' );
}
this .array [this .tailIndex ] = element;
this .tailIndex = (this .tailIndex + 1 ) & this .capacityBitmask ;
this .length ++;
}
shift (if (this .length <= 0 ) {
throw new Error ('Queue is empty' );
}
const element = this .array [this .headIndex ];
this .array [this .headIndex ] = undefined ;
this .headIndex = (this .headIndex + 1 ) & this .capacityBitmask ;
this .length --;
return element;
}
}
const QUEUE_ELEMENT = new Uint 8Array ();
function testQueue (queue, initialQueueSize, queueOperationCount ) {
for (let i = 0 ; i < initialQueueSize; i++) {
queue.push (i);
}
const iterationCount = initialQueueSize + queueOperationCount;
for (let i = initialQueueSize; i < iterationCount; i++) {
queue.push (i);
queue.shift ();
}
}
const INITIAL_QUEUE_SIZE = 127 ;
const QUEUE_OPERATIONS = 5000 ;
Teardown JS