Data Structures & Algorithms in JavaScript(Queue)





Hello Everyone, This is part 3 in the series of blogs about data structures and Algorithms in JavaScript, In this blog, I will cover Queue data structure.


What is Queue?


A Queue is a linear structure which follows a particular order in which the operations are performed. The order is FIFO(First In First Out)
-geeksforgeeks.org
A real-world example of a queue can be people standing at the bus stop where the first standing in the line will be the first person to get out of the line i.e. first in first out. If you compared it to a stack, the last person will be the first to leave.









   

This article will go through a list of following Queue DS,
  1. Queue.
  2. Deque(Double-ended queue).

List Of Operations Available

  1. Enqueue: Insert an element at the end of the queue.
  2. Dequeue: Remove an element from the front of the queue.
  3. Front: Return the first element of the queue.
  4. Size: Return Size of the queue.
  5. isEmpty: Check if the queue is empty if empty return true else false.
  6. Clear: Reset the queue.







Implementation of Stack in Javascript

let’s define ES6 class name Queue, with properties, a count which will keep track of the number of elements in the queue and items object which will store the elements. since we will be removing elements from the front of the queue, we also need a variable to help us track the first element. For this purpose, we declare the lowestCount variable
class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}

Enqueue

Insert an element in the queue is same as the push method of the stack or as Array push method.
enqueue(element){
         this.items[this.count] = element;
         this.count ++;
     }

Dequeue

To remove an element from the Queue, we first check if the Queue is empty if empty return undefined else store the lowestCount property element in a variable, To return the element after deletion, Delete the lowestCount item & increment the count by one. Dequeue method is same as the Array shift method which removes the first element.
dequeue(){
         if (this.isEmpty()) {
             return undefined;
         }
         let result = this.items[this.lowestCount]; 
         delete this.items[this.lowestCount]; 
         this.lowestCount ++; 
         return result; 

     }

Front

This method will return the item from the front of the queue (using the lowestCount as a key to retrieve the element value)
front(){
         if (this.isEmpty()) {
             return undefined;
         }
         return this.items[this.lowestCount];

     }

Size

This method will return the size of the queue which is count minus the lowestCount.
size() {
        return this.count - this.lowestCount;
    }
Example:-In the below queue items object, If the zeroth element was removed from the front of the queue, the lowest count will be one. The total count of the element will be two, therefore, the size of the queue will count-lowest count
let queue = {
   1: "1",
   2: "2",
}

isEmpty

isEmpty will return true if the queue is empty.
isEmpty() {
         return this.size() === 0;
    }

Clear

To clear all the elements from the queue, we can evoke the dequeue method until it returns undefined or we can simply reset the value of the Queue class properties to the same values as declared in its constructor
clear() {
    this.items = {}
    this.count = 0;
    this.lowestCount = 0;
    return this.items;
    }
you get the full source here

Conclusion :










The complexity of Queue Methods

So, stay tuned for the next blog, in which cover another DS Deque.

Data Structures & Algorithms in JavaScript(Queue) Data Structures & Algorithms in JavaScript(Queue) Reviewed by RS Coder on April 22, 2020 Rating: 5

No comments:

Powered by Blogger.