Martins Onuoha

Posted on May 10, 2023

Queue Data Structure in JavaScript

#javascript #frontend

Data Structure

Yeah, Data Structure. A Data Structure in computing is a “structure” (the arrangement and relations between the parts or elements of something) of data values that outlines the existing relationships between these values and the functions or operations that can be applied to all or some of these values.

Okay, So what are Queues

Well, Queues are a type of data structure that holds a collection of data in a linear/sequential (a set of related events, movements, or items that follow each other in a particular order) form, where modification is made by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.

Where modification is made by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.

This might sound familiar to you if you have basic computer science or accounting knowledge. It’s the concept of FIFO (First In, First Out).

FIFO in computing and systems theory is a method for organizing the manipulation of a data structure — often, specifically, a data buffer — in which the first items entered are the first ones to be removed.

A Practical Example

So far, we’ve only talked about the theoretical definitions. Let’s take a Pizza shop as a practical illustration. Que-Minos is the name of this shop — they make pizza. Ideally, they take and deliver orders sequentially on a “first come, first serve” basis (FIFO). Each customer walks in, heads over to the counter, places an order, and sits to wait. Once the first order is complete, the pizza is delivered, and the next in line is handled.

With JavaScript, it’s almost obvious that queues must be implemented using the Array object (Arrays are JavaScript’s strongest data structure — arguably, of course).

We would be implementing a Queminos class to represent our Queue Structure. This class would have some important methods to:

placeOrder (enqueue): This method adds a new order to the list of orders. Also referred to as Enqueue — adding (an item of data awaiting processing) to a queue.
deliverOrder (dequeue): This method delivers an order to a customer after completion. It performs the Dequeue function since it removes an element from the queue after settlement.
upNext: This method returns the next customer that should be attended to after the current order is delivered (ideally, that order should be at index 1).
hasOrders: This is a helper method that would allow Queminos to determine if any orders are available.
orders: This would be a getter method. This method would help us see all of the available orders.

Folder Structure

We’ll have a simple folder structure, one file to hold our Queminos class, another to import and use the class, and one more to hold the orders data.

    |-- Queminos.js
    |-- app.js
    `-- data.json

Queminos Class

class Queminos {
  #orders = []

  get orders() {}

  placeOrder(order) {}

  deliverOrder() {}

  upNext() {}

  hasOrders() {}
}

Here we’re using the class declaration to create the Queminos class. We then declare a private class property “orders” and set the value to an empty array. This would hold all the orders received by Queminos.

In ES2019, private class fields are defined using a hash # prefix: This is required so certain fields/properties of a class would not be mutable or accessible outside that class (e.g. from an instance of the class). This is designed around the idea of Encapsulation in OOP.

Alright, Let’s implement each of the methods:

Since we’re unable to access/mutate the “orders” property outside the class (because it’s private), we’ll implement a getter method “orders” that returns the private “orders” property.

get orders() {
    return this.#orders
}

The placeOrder method takes a single parameter, “order”, and adds it to the array of orders. This is basically our enqueue method.

placeOrder(order) {
    this.#orders.push(order)
}

The deliverOrder method, which serves as an implementation of the dequeue method, removes the first element in the orders array (remember FIFO?). First, we use the hasOrders method to check if orders exist in the queue before attempting to remove any.

deliverOrder() {
  return this.hasOrders() ? this.#orders.shift() : false
}

Here’s a list of practical examples of Array methods in JavaScript.

Understanding and Applying Array Methods in JavaScript | DevjavuUnderstanding and Applying Array Methods in JavaScript | Devjavu

Mutator, Accessor, and Iterator Groups.

devjavu.space

The upNext method, as mentioned earlier, returns the next order in the queue to be addressed. First, we need to check if there are orders, then check if there’s an order right behind the current one.

upNext() {
    return this.hasOrders() && this.#orders.length > 1
        ? this.#orders[1]
        : this.#orders[0]
}

Finally, the hasOrder method simply checks for orders in the #orders array.

hasOrders() {
    return this.#orders.length ? true : false
}

Our Queminos class should now look like this:

class Queminos {
  #orders = []

  get orders() {
    return this.#orders
  }

  placeOrder(order) {
    this.#orders.push(order)
  }

  deliverOrder() {
    return this.hasOrders() ? this.#orders.shift() : false
  }

  upNext() {
    return this.hasOrders() && this.#orders.length > 1
      ? this.#orders[1]
      : this.#orders[0]
  }

  hasOrders() {
    return this.#orders.length ? true : false
  }
}

module.exports = Queminos

Note that we’re exporting the Queminos class to use it outside of this file.

Data

Our JSON data is pretty basic. It’s a list of received orders in object format. You could make it simpler and use strings if you wish.

{
  "orders": [
    { "type": "Grand Pizza", "qty": 1, "customer_id": "10_000"},
    { "type": "Queminos Special", "qty": 2, "customer_id": "10_001"},
    { "type": "Grand Pizza", "qty": 3, "customer_id": "10_002"},
    { "type": "Grand Pizza", "qty": 1, "customer_id": "10_003"}
  ]
}

We’ll import our class into the app.js file as well as our JSON data. From here, we can test our Queueing system.

const Queminos = require('./Queminos')
const data = require('./data.json')

const pizzaShop = new Queminos

// place orders
data.orders.forEach(order => pizzaShop.placeOrder(order));

console.log(pizzaShop.deliverOrder()) // dequeue
console.log(pizzaShop.upNext()) // get upnext
console.log(pizzaShop.orders)

There you have it, a practical implementation of Queues in JavaScript.

Here’s a link to the source code:

MartinsOnuoha / js-queue-example

A basic example of Queue Data Structure in Javascript