Instantly share code, notes, and snippets.

@OllieJones OllieJones/queue.js
Created Feb 9, 2019

Embed
What would you like to do?
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);
};
/**
* 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