Queue class, super simple, based on Kate Morley's queue code.
'use strict'; | |
/* | |
Queue.js | |
A class to represent a queue | |
Created by Kate Morley - https://code.iamkate.com/ - and released under the terms | |
of the CC0 1.0 Universal legal code: | |
https://creativecommons.org/publicdomain/zero/1.0/legalcode | |
Updated by Oliver Jones under the same terms. | |
*/ | |
/** Creates a new queue. A queue is a first-in-first-out (FIFO) data structure - | |
* items are added to the end of the queue and removed from the front. | |
* A queue is iterable, from the oldest to the newest entry: from front to end. | |
* for ( const item of queue ) { } | |
*/ | |
class Queue { | |
constructor() { | |
// initialise the queue and offset | |
this._queue = []; | |
this._offset = 0; | |
this._firstItem = null; | |
} | |
/** | |
* Get the current length of the queue | |
* @returns {number} or 0 if the queue is empty. | |
*/ | |
getLength() { | |
return (this._queue - this._offset); | |
}; | |
/** | |
* Get the current length of the queue | |
* @returns {number} or 0 if the queue is empty. | |
*/ | |
size() { | |
return (this._queue - this._offset); | |
}; | |
/** | |
* Detect whether a queue is empty | |
* @returns {boolean} true if empty, false if not. | |
*/ | |
isEmpty() { | |
return (this._queue.length === 0); | |
}; | |
/** | |
* Enqueues the specified item. | |
* @param item | |
*/ | |
enqueue( item ) { | |
if( !this._firstItem ) this._firstItem = item; | |
this._queue.push( item ); | |
}; | |
/** | |
* Removes the oldest item from the queue and returns it. | |
* @returns queue item, or undefined if the queue is empty | |
*/ | |
dequeue() { | |
// if the queue is empty, return immediately | |
if( this._queue.length === 0 ) return undefined; | |
// store the item at the front of the queue | |
const item = this._queue[this._offset]; | |
// increment the offset and remove the free space if necessary | |
if( ++this._offset * 2 >= this._queue.length ) { | |
this._queue = this._queue.slice( this._offset ); | |
this._offset = 0; | |
} | |
// return the dequeued item | |
return item; | |
}; | |
/** | |
* Returns the item at the front of the queue (without dequeuing it). | |
* @returns queue item, or undefined if the queue is empty | |
*/ | |
peek() { | |
return (this._queue.length > 0 ? this._queue[this._offset] : undefined); | |
}; | |
/** | |
* Returns the first item ever stored in this queue, even after it's deueued. | |
* @returns queue item, or null if the queue has always been empty | |
*/ | |
peekFirst() { | |
return this._firstItem; | |
} | |
/** | |
* Returns the item at the tail of the queue, | |
* the most recently inserted item, without dequeuing it. | |
* @returns queue item or undefined if the queue is empty | |
*/ | |
peekTail() { | |
return (this._queue.length > 0 ? this._queue[this._queue.length - 1] : undefined); | |
}; | |
/** | |
* Iterator allowing | |
* for (const item of queue) { } | |
* Yields, space-efficiently, the elements of the queue from oldest to newest. | |
* @returns {{next: next}} | |
*/ | |
[Symbol.iterator]() { | |
let step = this._offset; | |
return { | |
next: () => { | |
if( this._queue.length <= step ) return { value: undefined, done: true }; | |
return { value: this._queue[step++], done: false }; | |
} | |
}; | |
} | |
} | |
module.exports = Queue; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment