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 (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("John Cena")); // ["The Rock", "John Cena"]
console.log(queue.enqueue("Stone Cold Steve Austin")); // ["The Rock", "John Cena", "Stone Cold Steve Austin"]
console.log(queue.dequeue()); // "The Rock"
console.log(queue.peek()); // "John Cena"
console.log(queue.isEmpty()); // false
queue.print(); // ["John Cena", "Stone Cold Steve Austin"]Source Code
The source code for this example can be found here: https://github.com/Xabadu/js-data-structures