Data Structures: Queue

Data Structures: Queue

A simple guide to understanding Queue data structure ๐Ÿš€

Introduction

A Queue is a First In First Out - FIFO Data structure that is used to store a collection of items. The FIFO system means the first element inserted into the queue will be the first item removed.

queue image A really good illustration from programiz.com/dsa/queue

Important Concepts

  • In the queue, we perform insertion from the rear or end of the queue and deletion from the top or front of the queue.
  • Inserting an element in a queue is called enqueue.
  • Deleting an element from the queue is called dequeue.
  • Queue is a Linear type of data structure.

Time Complexity

OperationTime Complexity
enqueueO(1)
dequeueO(1)
get/accessO(n)
searchO(n)

Applications Of Queue

  • Queues are highly used in scheduling. Since this data structure works in an orderly manner, we can schedule tasks in it and all of them will be executed one by one.
  • Operating systems often maintain a queue of ready-to-execute processes or that are waiting for a particular event to occur. Therefore it acts as a holding area as well.

  • When multiple requests are initiated to a single resource such as a printer or a server, it can maintain all of them in a queue and execute them one by one.

  • This data structure is also used in messaging queues. A message queue is a form of asynchronous service-to-service communication used in serverless and microservices architectures. Messages are stored on the queue until they are processed and deleted. Each message is processed only once, by a single consumer.

Coding A Queue In JavaScript

class Queue {
  constructor() {
    this.queue = [];
  }
}

isEmpty

isEmpty is used to check the state of the queue. Either it's empty or not.

isEmpty() {
  return this.queue.length === 0;
}

enqueue

We add an item at the rear of the queue. This operation is called enqueue

enqueue(item) {
  this.queue.unshift(item);
  return item;
}

dequeue

We remove an item from the front of the queue. This operation is called dequeue. We also check if the queue is empty before removing an element to avoid underflow.

dequeue() {
  if (this.isEmpty()) {
    return 'Queue is already empty.';
  }
  return this.queue.pop();
}

Another useful operation is search. Please make sure the searching criteria and algorithm have to be decided concerning the scenario. In this case, I'm using linear search which is pretty common and simple.

search(item) {
  /**
   * We are going to use .find() here but you can write down your search
   * logic here. It's total up to you and you can choose the best with
   * Respect to the use case
   */

  return this.queue.find(queueItem => queueItem === item) ? true : false;
}

printQueue

This is just a method to print the queue.

printQueue() {
  return this.queue.join(' -> ');
}

Let's test our queue and the results:

const queue = new Queue();
queue.enqueue(1);
queue.enqueue('Rehan sattar');
queue.enqueue(false);
queue.enqueue(1.23);

console.log(queue.printQueue()); // 1.23 -> false -> "Rehan sattar" -> 1
queue.dequeue();
console.log(queue.printQueue()); // 1.23 -> false -> Rehan sattar
queue.dequeue();
console.log(queue.printQueue()); // 1.23 -> false

const foundOne = queue.search(1.23);
console.log(foundOne);           // true

const foundSomething = queue.search('Something else');
console.log(foundSomething);      // false

That's all folks!

That's it, folks! hope it was a good read for you. Thank you! โœจ

๐Ÿ‘‰ Follow me: Github Twitter LinkedIn Youtube

ย