Data Structures: What's a Queue?

For the second article in my Data Structures series, we are going to be diving into queues. Queues are the polar opposite of the stack data structure. If you're not aware of what a stack real quickly go ahead and check out my article on them here and come on back.

Queue

Just like a stack, we can easily represent a queue's functionality with a real-world example. Think of a line of people waiting to go on a ride at your favorite amusement park. Naturally, the person that was in line first will be the first person to leave the line to go on their favorite ride. People are added to the line at the end and leave the line from the beginning.

That is very similar to how a queue operates, the first piece of data added to our queue will be the first piece of data to be removed FIFO (First In First Out). When referencing adding an element to the queue we use the term Enqueue and when referencing removing an element we use the term Dequeue. When we enqueue an element we are adding it to the tail(end) of the data structure and when we dequeue an element we are removing it from the head(beginning) of the data structure.

When creating a queue in JavaScript we have a couple of options at our disposal. Let's dive into two of them, we will be implementing a queue data structure with an array and then creating a queue from scratch.

With an array implementation of a queue we can add to the end and remove from the beginning like below:

> const queue = []

> queue.push("dog")
=> 1
> queue.push("cat")
=> 2
> queue.push("mouse")
=> 3

> queue
=> ["dog", "cat", "mouse"]

> queue.shift()
=> "dog"
> queue.shift()
=> "cat"
> queue.shift()
=> "mouse"
> queue.shift()
=> undefined

Or we can add to the beginning of the array and remove from the end:

> const queue = []

> queue.unshift("lion")
=> 1
> queue.unshift("tiger")
=> 2
> queue.unshift("bear")
=> 3

> queue
=> ["bear", "tiger", "lion"]

> queue.pop()
=> "lion"
> queue.pop()
=> "tiger"
> queue.pop()
=> "bear"
> queue.pop()
=> undefined

While both of the above implementations adhere to the queue's FIFO (First In First Out) operations think about the following:

In the first example where we are adding to the end of the array and removing from the beginning, each time we remove an element from the beginning we have to re-index the entire array.

In the second example where we are adding to the beginning of the array and removing from the end, each time we add an element to the beginning of the array we have to re-index the entire array.

This re-indexing of the array gives us a linear O(n) time complexity which can have negative performance implications when dealing with very large data sets.

Now let's create our own queue data structure from scratch which will give us a constant O(1) time complexity when we Enqueue or Dequeue elements.

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

// enqueue(val) - adds element to our queue,
// returns number of elements in queue
    enqueue(val) {
        const newNode = new Node(val);
        if (!this.first) {
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        };
        return ++this.size;
    };

// dequeue() - removes first element from queue
// returns value of element removed
    dequeue() {
        if (!this.first) return null;
        const removedNode = this.first;
        if (this.first === this.last) {
            this.last = null;
        };
        this.first = this.first.next;
        this.size--;
        return removedNode.value
    };
};


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

Console:

> const queue = new Queue;
> queue
=> Queue { first: null, last: null, size: 0 }
> queue.enqueue("dog")
=> 1
> queue
=> Queue {
  first: Node { value: 'dog', next: null },
  last: Node { value: 'dog', next: null },
  size: 1
}
> queue.enqueue("cat")
=> 2
> queue.enqueue("mouse")
=> 3
> queue
=> Queue {
  first: Node { value: 'dog', next: Node { value: 'cat', next: [Node] } },
  last: Node { value: 'mouse', next: null },
  size: 3
}
> queue.first
=> Node {
  value: 'dog',
  next: Node { value: 'cat', next: Node { value: 'mouse', next: null } }
}
> queue.first.value
=> dog
> queue.dequeue()
=> dog
> queue.dequeue()
=> cat
> queue
=> Queue {
  first: Node { value: 'mouse', next: null },
  last: Node { value: 'mouse', next: null },
  size: 1
}
> queue.dequeue()
=> mouse
> queue.dequeue()
=> null

Take some time to review the code and the sample outputs above. We have created a Queue class to create our queue data structure object which also allows us to Enqueue and Dequeue are elements. The Node class allows us to create an object housing our value and a pointer linking to the next node in our queue. While there is a lot more code in the above implementation, which may be hard to understand at first the performance gains will be worth it in the end when dealing with large data sets. When we Enqueue(adding to the tail) and Dequeue(removing from the head) in the above example we are getting a constant O(1) time complexity.

I hoped this helped you understand the queue data structure better. If you have any questions or anything to add drop them in the comments below.

Cheers!