Queues in JavaScript

by kirupa   |   31 August 2017

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!

Meet the Queue

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.

A JavaScript Implementation

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() {
        var item = null;

        if (this.items.length > 0) {
            item = this.items[0];
        }
        
        return item;
    }
    dequeue() {
        var 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
var myQ = new Queue();

// add two items
myQ.enqueue("Item 1");
myQ.enqueue("Item 2");

// remove item
var 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.

Conclusion

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!

If you have a question about this or any other topic, the easiest thing is to drop by our forums where a bunch of the friendliest people you'll ever run into will be happy to help you out!

THE KIRUPA NEWSLETTER

Get cool tips, tricks, selfies, and more...personally hand-delivered to your inbox!

( View past issues for an idea of what you've been missing out on all this time! )

WHAT DO YOU THINK?

NEWSLETTER

No spam. No fluff. Just awesome content sent straight to your inbox!

Awesome and high-performance web hosting!
BACK TO TOP
new books - yay!!!