Queues

Today we're here to talk about the exact opposite of stacks (btw you can find my blog post on stacks), you probably guessed it, QUEUES! So what are queues exactly, well a queue is essentially a data structure which allows the FIFO approach (first in first out), think of it like a queue for a concert the first one that gets in the queue is the first one to get out.

Implementation

Now that we know what they are, let's see how we can implement them. We essentially have two possibilities, one which consists of simply using an array with it's built in capabilities and its drawbacks and the second one with a custom data structure.

Built in array

What built in methods could we use from array to build a queue? Keep in mind that we should apply the first in, first out strategy. Well i know two perfect methods for this:

• push: method that adds an item to the end of the array
• shift: method which removes the first item from the array

const queue = [];
queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.shift(); // 1

It's simple that's for sure, we don't have to implement anything we can just use a built in data structure, but there are a few drawbacks to keep in mind:

• memory: arrays have a lot of built in methods we won't need in this case
• index based: shift is not the most efficient way of dequeing because every items are indexed based meaning we need to reassign every item's index after every shift.

Custom data structure

Now on to our second solution, creating our own data structure, the queue class which is essentially a linked list, meaning it has a first (storing the first item), a last (storing the last one) and a length property (I'll let you guess this one).

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.length = 0;
  }
}

As mentioned, a queue is composed of items and more specifically nodes which are represented like that:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

Here, every node has two properties a value and a next which holds the next item. Now from there we only need two methods, we'll call them queue and dequeue but you can call them however you want.

Queue

function queue(value) {
  const newNode = new Node(value);
  if (!this.length) {
    this.first = newNode;
    this.last = newNode;
  } else {
    this.last.next = newNode;
    this.last = newNode;
  }
  this.length++;
  return this.length;
}

Explanation

Here we create a node with the value parameter from there we have two cases to handle:

• the queue is empty, we have to set both the first and the last to be the newNode
• otherwise, we have to override our last property but before that to avoid any data lose we set last.next to be the newNode and then we override the last.

Once done we take care of bookkeeping by increasing the length and return it.

Dequeue

function dequeue() {
  if (this.length === 0) return;
  const toRemove = this.first;
  if (this.length === 1) {
    this.last = null;
  }
  this.first = this.first.next;
  this.length--;

  return toRemove.value;
}

Explanation

Again we have a few cases to handle:

• there is no nodes in the queue, we simply return
• there is only one node? we simply set last to null
• there is more than one node? we simply set first to be the second node or first.next (note that when we only have one node first.next will be null so we're also taking care of first)

Once done we take care of bookkeeping by decreasing the length and returning the node we just removed.

So that's all we need:

const queue = new Queue();
queue.queue(1); // 1
queue.queue(2); // 2
queue.dequeue(); // 1

Performance considerations

• Enqueue: O(1) for adding an element to the end of the queue.
• Dequeue: O(1) for removing an element from the front of the queue.
• Push: O(1) for adding an element to the end of the array.
• Shift: O(n) for remove an element from the start of the array, because as mentionned we have to reassign every item's index.

Practical Use Cases

Queues are widely used in programming. One common example is when you're on Ticketmaster trying to purchase a ticket for a popular event, you are essentially placed in a queue to manage the high demand and ensure fair access to the tickets. Many other use cases including:

• Task scheduling in operating systems.
• Handling requests in web servers.
• Breadth-first search (BFS) in graphs and trees.
• Managing print jobs in a printer spooler.
• Implementing buffers in streaming data applications.

Conclusion

Congrats 🎉 you made it through I hope you learned a lot, I certainly did and if you have any suggestions, improvements or anything that comes to your mind don't hesitate to write! I'll reply asap!

Happy coding