Photo belongs to Xiangkun ZHU in Unsplash
Have you ever waited in line for an artist’s autograph? If so, you know what I’m talking about. You wake up early in the morning to be first in line and get your favorite record, poster, or book signed.
Well, that’s FIFO in action. And the data structure we’re going to review this week follows this principle. We are learning how to implement Queues.
First In First Out
Queues implement FIFO (First In First Out) ordering. This means items are removed from the queue in the same order that they are added.
Unlike the stack data structure, queue ordering works like waiting in line to meet your favorite idol. The position you get in line is the position in which you’ll get to shake those famous hands.
Hold the Line
This week we are going to implement a Queue. Like a stack, it can be implemented with a linked list, as they are essentially the same structure — just with items added and removed from opposite sides.
We’ll reuse the Node class we created earlier in the stack post:
export class Node<T> {
value: T;
next: Node<T> | null;
constructor(value: T) {
this.value = value;
this.next = null;
}
}
This Node class will store each item in the Queue, holding the actual value along with a reference to the next item.
Now for our Queue class, we’ll follow the same approach, taking advantage of TypeScript Generics. Unlike a stack, however, we’ll keep track of both the first and last items in our queue.
export class Queue<T> {
first: Node<T> | null;
last: Node<T> | null;
size: number;
}
In our constructor, we need to initialize the first and last node references. This ensures that each time a new Queue is instantiated, we have default values for our first and last items in the Queue.
constructor(value: T) {
this.first = new Node(value);
this.last = this.first;
this.size = 1;
}
Enqueueing an Item
The enqueue operation adds an item to the end of the queue. The first step is to create a new node.
const newNode = new Node(value);
Since this new node will become the last item in the queue (as it’s the newest to join), we need to check if the last variable is not null. If it has a value, we connect its next pointer to this new node.
if(this.last !== null) this.last.next = newNode;
Next, we update the last pointer to reference our newly created node.
this.last = newNode;
We also need to ensure that the first variable has a value. If it’s null, it means this new node is the first element in the queue.
if(this.first === null) this.first = this.last;
Finally, we increment the queue size. And voila! Our queue can now enqueue new items.
Dequeueing an Item
This operation removes the first item in the queue. The first step is to verify that the first variable is not null. If it is null, we simply return null because there are no items in the queue.
if(this.first === null) return null;
Now that we’ve verified the first variable has a value, we assign this value to a new constant called nodeToDequeue to keep track of the node we’ll remove.
const nodeToDequeue = this.first;
Next, we need to reassign the first variable to point to the next item (node) in the queue, as this will become our new first element.
this.first = this.first.next;
Next, we need to check if there are any nodes left in the queue. If the first pointer is now null, it means our queue is empty and we must also clear the last pointer.
if(this.first === null) this.last = null;
Finally, we decrement the queue size and return the value of the removed node.
this.size--;
return nodeToDequeue.value;
And voila! Our queue now has the capability to dequeue its elements. Simple, isn’t it?
Peeking the Top
This operation returns the first item in the queue while ensuring it has a value. It’s straightforward since we’ve already created our first variable — we simply return its value if it exists, or null if it doesn’t.
return this.first ? this.first.value : null;
As you can see, we resolved this with an elegant one-liner. This simple operation allows us to peek at the first item in our queue without removing it.
Is the Queue Empty?
This operation checks if our queue is empty by examining its size. If the size equals 0, it means there are no items in our queue, indicating it’s empty. The method simply returns this evaluation.
return this.size === 0;
Complete Typescript Implementation
export class Queue<T> {
first: Node<T> | null;
last: Node<T> | null;
size: number;
constructor(value: T) {
this.first = new Node(value);
this.last = this.first;
this.size = 1;
}
enqueue(value: T): void {
const newNode = new Node(value);
if(this.last !== null) this.last.next = newNode;
this.last = newNode;
if(this.first === null) this.first = this.last;
this.size++;
}
dequeue(): T | null {
if(this.first === null) return null;
const nodeToDequeue = this.first;
this.first = this.first.next;
if(this.first === null) this.last = null;
this.size--;
return nodeToDequeue.value;
}
peek(): T | null {
return this.first ? this.first.value : null;
}
isEmpty(): boolean {
return this.size === 0;
}
}
Final Thoughts
In this post, we have explored the Queue data structure and its FIFO (First In, First Out) principle. We reviewed how to implement a Queue in TypeScript, using linked nodes similar to those we used in stacks, but with the crucial difference of adding elements to the end and removing them from the beginning.
We implemented four fundamental operations: enqueue to add elements, dequeue to remove them, peek to check the first element without removing it, and isEmpty to verify if the queue is empty. These operations allow us to manipulate the queue efficiently, always maintaining the order of arrival.
Queues are fundamental data structures that appear in numerous programming contexts and in everyday situations, like waiting in line for your favorite artist’s autograph. Understanding their operation and implementation gives us powerful tools to solve problems that require processing elements in the same order they were received.
As alway you can find the code in my Data Structures repository: https://github.com/RubenOAlvarado/data-structures
Until the next one!
