Earlier, we saw that stacks are are a Last In First Out (LIFO) data structure where items are added and removed from the end. Contrasting that, we have the other popular data structure, the queue. This is an interesting one that we'll learn more about in the following sections.
Onwards!
Living up to its name, a queue is very similar to standing in line for something:
The person standing at the front of the line is the first one to have shown up, and they are the first ones to leave as well. New people show up and stand at the end of the line, and they don't leave until the person in front of them has reached the beginning of the line and has left:
Given that behavior, a queue follows a First In First Out policy more commonly shortened to FIFO. Except for the little big detail about which items get removed first, queues and stacks are pretty similar otherwise.
When adding items, the behavior with stacks is identical:
Items are added to the end. When removing items, it is the first item that gets removed in a queue-based world:
Now, you may be wondering when you'll ever end up needing to use of a queue. Besides helping you appreciate standing in line, queues have a lot of practical uses in the digital world. Pretty much any situation that requires you to maintain an order of something relies on a queue like data structure. High traffic situations like travel booking, waiting to purchase a ticket for a popular concert, prioritizing e-mails by an e-mail server, and more are all situations a queue is used. You'll see queues used a lot by various search algorithms as well, so queues are here to stay! Get friendly with them.
To use a queue in your own web projects, just add the following Queue class to your code:
class Queue {
constructor(...items) {
this.items = items;
}
clear() {
this.items.length = 0;
}
clone() {
return new Queue(...this.items);
}
contains(item) {
return this.items.includes(item);
}
peek() {
let item = null;
if (this.items.length > 0) {
item = this.items[0];
}
return item;
}
dequeue() {
let removedItem = this.items.shift();
return removedItem;
}
enqueue(item) {
this.items.push(item);
return item;
}
}
The way you use it is by creating a Queue object, using the enqueue method to add items to the queue, and using the dequeue method to remove items from the queue:
// create new Queue object
let myQ = new Queue();
// add two items
myQ.enqueue("Item 1");
myQ.enqueue("Item 2");
// remove item
let removedItem = my.dequeue(); // returns Item 1
You can easily create a copy of your queue by using the clone method, check whether an item exists using contains, and peek at what the removed item might be (without actually removing it) by using...um...peek! It's a really simple implementation, and you can read more about how it was created in this thread.
Just like with stacks, our queue implementation is also based on an array under the covers. With arrays, removing (Array.pop) and adding items (Array.push) at the end is a ridiculously fast operation. With queues, we are removing items from the beginning using Array.shift. While that seems like it would be a slower operation, in reality many browser engines have optimized it so that operation is reasonably fast for many scenarios. If you really want to check out a version that I manually optimized to avoid removing an item from the beginning of the array, check out this alternative Queue implementation. Don't forget to test the performance while you are at it. For bonus points, run the test across multiple browsers. Comment below on what you find out!
Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!