Skip to content

Instantly share code, notes, and snippets.

@jonsmithers
Created May 8, 2018 16:33
Show Gist options
  • Save jonsmithers/cf9f6535abef46275df62e90a11456eb to your computer and use it in GitHub Desktop.
Save jonsmithers/cf9f6535abef46275df62e90a11456eb to your computer and use it in GitHub Desktop.
A missing queue implementation for JavaScript, implemented with a linked list
/**
* Simple Queue implementation based on a linked-list
*/
class Q {
/**
* Construct a queue
* @param {array} [items] - Items to put in the queue (in left-to-right order)
*/
constructor(items) {
this._size = 0
this._head = null
this._tail = null
if (items) {
this.enqueue(...items)
}
}
/**
* Elements currently in queue
*/
get size() {
return this._size
}
/**
* Add item(s) to queue
* @param {...*} items - Items to put in the queue (in left-to-right order)
*/
enqueue(...items) {
for (let item of items) {
if (!this._tail){
this._tail = this._head = { item, next: null}
} else {
this._tail.next = { item, next: null}
this._tail = this._tail.next
}
this._size++
}
}
/**
* Remove item in FIFO order
* @return {*} item
* @throws {Error} Queue must not be empty
*/
dequeue() {
if (!this._size) {
throw new Error("queue is empty")
}
let result = this._head.item
this._head = this._head.next
this._size--
if (this._head === null) {
this._tail = null
}
return result
}
/** for debugging in node */
inspect() {
let node = this._head
let items = []
while (node) {
items.push(node.item)
node = node.next
}
return `queue -> ${items.map(i => require('util').inspect(i)).join(',')} ->`
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment