DEV Community

Cover image for Data Structures with JavaScript: Queues
Fernando Larrañaga
Fernando Larrañaga

Posted on

Data Structures with JavaScript: Queues

Cover image by Florencia Viadana on Unsplash

¿Español? Puedes encontrar la versión traducida de este artículo aquí: Estructuras de datos con JavaScript — Parte 2: Colas (Queues)

This article is part of a series about data structures in JavaScript. The previous one can be found here:

Continuing this (not so) magical adventure with data structures in JavaScript, it is now time to talk about queues!

What is a queue?

A queue is a data structure very similar to a stack, meaning that it also operates in a linear and unidirectional way (elements are added from beginning to end). The main difference is in the way that elements are extracted from it. While a stack uses the LIFO (Last In First Out) principle, a queue uses the FIFO (First In First Out) principle instead. That means that the first element added to the queue will be the first one that will be extracted.

A common example to understand the behavior of a queue would be the line that we have to stand in when we go to the bank or a grocery store for checkout. In these lines, the person that is at the front of the line will be the first one to receive service.

graphic representation of a queue

graphic representation of a queue (sort of)

When to use a queue

Two of the most common uses for queues are present in tools and processes we probably use on a daily basis: Job queues, such as Resque, Sidekiq or Kue, and messaging services. In both cases, the data will be processed in a first-come-first-serve basis.

Complexity of a queue

The complexities of a queue are practically the same as the ones for stacks:

Time Complexity

  • Read: O(n)
  • Search: O(n)
  • Insert: O(1)
  • Delete: O(1)

Space complexity (in memory): O(n).

Methods/functionality of a queue

A well-implemented queue will need the provide methods that allow adding, remove and show elements, as well as return the current size of the queue. These methods are commonly named:

  • enqueue: Adds a new element at the end of the queue.
  • dequeue: Returns the first element, removing it from the queue.
  • peek: Returns the first element, without removing it from the queue.
  • size: Returns the number of elements of the queue.
  • print: Displays the content of the queue.

Optionally, some implementations also include a method called isEmpty. that will return a boolean (true/false) depending if the queue is empty or not. If the method is not available, we can infer such information by calling size.

How to implement a queue

The most direct way to implement a queue in JavaScript is by using an Array. Most of the methods we'll need are already implemented in its prototype, so we'll just have to create wrappers to return the values to the user.

The only additional method that we'll have to implement manually is peek, for which we'll return the first element of the array (of index 0).

class Queue {
  constructor() {
    // Initializes the queue as an empty string
    this.queue = [];
  }

  enqueue(element) {
    // Adds a new element by using push and returns the queue
    this.queue.push(element);
    return this.queue;
  }

  dequeue() {
    // Removes the first element by using shift
    return this.queue.shift();
  }

  peek() {
    // Shows the element in the first position
    return this.queue[0];
  }

  size() {
    // Returns the size of the array using length
    return this.queue.length;
  }

  isEmpty() {
    // Checks if there are no elements available by using length
    return this.queue.length === 0;
  }

  print() {
    // Displays the entire queue
    console.log(this.queue);
  }
}

const queue = new Queue();
console.log(queue.enqueue("The Rock")); // ["The Rock"]
console.log(queue.enqueue("Diamond Dallas Page")); // ["The Rock", "Diamond Dallas Page"]
console.log(queue.enqueue("Stone Cold Steve Austin")); // ["The Rock", "Diamond Dallas Page", "Stone Cold Steve Austin"]
console.log(queue.dequeue()); // "The Rock"
console.log(queue.peek()); // "Diamond Dallas Page"
console.log(queue.isEmpty()); // false
queue.print(); // ["Diamond Dallas Page", "Stone Cold Steve Austin"]
Enter fullscreen mode Exit fullscreen mode

Source Code

You can find the source code of this example here:https://github.com/Xabadu/js-data-structures

Originally published on my blog at xabadu.dev

Top comments (0)