Implementing Queues Using Linked Lists in NestJS

Introduction

One of the fundamental data structures is the queue, which follows the First-In-First-Out (FIFO) principle. Combining the flexibility of linked lists with the functionality of queues can lead to efficient and dynamic data handling. This article guides you through the implementation of queues using linked lists in NestJS.

Understanding Queues and Linked Lists

Queue Overview:

A queue is a linear data structure where elements are added at one end (rear) and removed from the other end (front). This structure is ideal for scenarios like task scheduling, request handling, and managing asynchronous operations.

Linked List Overview:

A linked list is a collection of nodes where each node contains data and a reference to the next node in the sequence. Linked lists allow for efficient insertions and deletions without the need for contiguous memory.

Combining these two, we can create a queue that efficiently handles dynamic data with minimal overhead.

Implementing the Queue Using Linked Lists

1. Node Class Each node in the linked list will contain data and a reference to the next node.

export class ListNode {
  constructor(
    public data: any,
    public next: ListNode | null = null,
  ) {}
}

1. Queue Class: The queue class manages the nodes, ensuring elements are enqueued at the rear and dequeued from the front.

export class LinkedListQueue {
  private head: ListNode | null = null;
  private tail: ListNode | null = null;

  enqueue(data: any): void {
    const newNode: ListNode = new ListNode(data);
    if (!this.tail) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  dequeue(): null | any {
    if (!this.head) return null;
    const data = this.head.data;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    return data;
  }

  isEmpty(): boolean {
    return this.head === null;
  }

  front(): null | any {
    return this.head ? this.head.data : null;
  }

  print(): void {
    let current: ListNode = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

1. NestJS Service: Encapsulate the queue operations within a NestJS service.

@Injectable()
export class QueueService {
  private queue: LinkedListQueue = new LinkedListQueue();

  enqueueElement(data: any): void {
    this.queue.enqueue(data);
  }

  dequeueElement(): any {
    return this.queue.dequeue();
  }

  isQueueEmpty(): boolean {
    return this.queue.isEmpty();
  }

  getFrontElement(): any {
    return this.queue.front();
  }

  printQueue(): void {
    this.queue.print();
  }
}

Controller Integration

Create a controller to expose the queue operations through API endpoints.
I used swagger for testing the endpoints, you need to install swagger if you want to do the same.

@Controller('queue')
@ApiTags('Queue')
export class QueueController {
  constructor(private readonly queueService: QueueService) {}

  @Post('enqueue/:data')
  @ApiParam({ name: 'data', type: 'string' })
  enqueueElement(@Param('data') data: string) {
    this.queueService.enqueueElement(data);
    return { message: 'Element enqueued successfully' };
  }

  @Delete('dequeue')
  dequeueElement() {
    const data = this.queueService.dequeueElement();
    return { data };
  }

  @Get('is-empty')
  isQueueEmpty() {
    return { isEmpty: this.queueService.isQueueEmpty() };
  }

  @Get('front')
  getFrontElement() {
    const data = this.queueService.getFrontElement();
    return { data };
  }

  @Get()
  printQueue() {
    this.queueService.printQueue();
    return { message: 'Queue printed successfully' };
  }
}

Optimizing Queue Operations

Time Complexity:

• Enqueue: O(1) – Adding an element to the tail.
• Dequeue: O(1) – Removing an element from the head.
• Front: O(1) – Accessing the front element.
• IsEmpty: O(1) – Checking if the queue is empty.

Use Cases:

• Task scheduling systems.
• Managing asynchronous operations in web applications. ...and many more.

Conclusion

Implementing queues using linked lists in NestJS provides a dynamic and efficient way to manage data. By encapsulating queue operations within services and exposing them through controllers, you can create robust solutions for various real-world scenarios. Experiment with these implementations to enhance your NestJS applications' performance and scalability.

My way is not the only way!