Skip to content

Instantly share code, notes, and snippets.

@sebinsua
Created Aug 11, 2022
Embed
What would you like to do?
Implementing a basic FIFO queue using a DoublyLinkedList. See: https://gist.github.com/sebinsua/d0d15ad44b721d5210a6dc1dd3a1bf7e
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());
@sebinsua
Copy link
Author

sebinsua commented Aug 11, 2022

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment