Created
August 11, 2022 22:40
-
-
Save sebinsua/5793e35ee6befa7e994c0a1001f21382 to your computer and use it in GitHub Desktop.
Implementing a basic FIFO queue using a DoublyLinkedList. See: https://gist.github.com/sebinsua/d0d15ad44b721d5210a6dc1dd3a1bf7e
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class QueueItem { | |
constructor(value) { | |
this.value = value; | |
this.head = null; | |
this.tail = null; | |
} | |
valueOf() { | |
return this.value; | |
} | |
get left() { | |
return this.head; | |
} | |
get right() { | |
return this.tail; | |
} | |
} | |
class Queue { | |
constructor(values = []) { | |
this.head = null; | |
this.tail = null; | |
this.length = 0; | |
for (const value of values) { | |
this.push(value); | |
} | |
} | |
get size() { | |
return this.length; | |
} | |
get isEmpty() { | |
return this.length === 0; | |
} | |
toString() { | |
const values = Array.from(this); | |
return `${this.constructor.name}: ${values.join(" <-> ")}`; | |
} | |
peek() { | |
const currentHead = this.head; | |
const value = currentHead ? currentHead.value : null; | |
return value; | |
} | |
enqueue(value) { | |
return this.push(value); | |
} | |
dequeue() { | |
return this.shift(); | |
} | |
push(value) { | |
const node = new QueueItem(value); | |
if (!this.tail) { | |
this.head = node; | |
this.tail = node; | |
this.length++; | |
return; | |
} | |
const currentTail = this.tail; | |
currentTail.tail = node; | |
node.head = currentTail; | |
this.tail = node; | |
this.length++; | |
} | |
shift() { | |
const currentHead = this.head; | |
const value = currentHead ? currentHead.value : null; | |
const newHead = currentHead.tail; | |
newHead.head = null; | |
this.head = newHead; | |
this.length--; | |
return value; | |
} | |
clear() { | |
this.head = null; | |
this.tail = null; | |
this.length = 0; | |
} | |
*[Symbol.iterator]() { | |
yield* this.values(); | |
} | |
*keys() { | |
let currentNode = this.head; | |
if (!currentNode) { | |
return; | |
} | |
while (currentNode) { | |
yield currentNode; | |
currentNode = currentNode.tail; | |
} | |
} | |
*values() { | |
let currentNode = this.head; | |
if (!currentNode) { | |
return; | |
} | |
while (currentNode) { | |
yield currentNode.value; | |
currentNode = currentNode.tail; | |
} | |
} | |
*entries() { | |
let currentNode = this.head; | |
if (!currentNode) { | |
return; | |
} | |
while (currentNode) { | |
yield [currentNode, currentNode.value]; | |
currentNode = currentNode.tail; | |
} | |
} | |
} | |
const q = new Queue(); | |
q.enqueue(1); | |
q.enqueue(2); | |
q.enqueue(3); | |
q.dequeue(); | |
q.enqueue(4); | |
q.enqueue(5); | |
console.log("peeking at the next in line", q.peek()); | |
q.dequeue(); | |
console.log(q.toString()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See CodeSandbox: https://codesandbox.io/s/gracious-matsumoto-8jmiqg?file=%2Fsrc%2Findex.js