Queue Data Structure

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

If you already have a subscription, you can sign in.

Queue Data Structure

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

/**
* First In First Out (FIFO)
* with time complexity of O(1) for key operations
*/
export class Queue<T>{

/** Enqueues the item in O(1) */
enqueue(item: T): void {

}

/**
* Dequeues the first inserted item in O(1)
* If there are no more items it returns `undefined`
*/
dequeue(): T | undefined {

}
}

Solution

/**
* First In First Out (FIFO)
* with time complexity of O(1) for key operations
*/
export class Queue<T>{
private data: { [index: string]: T } = Object.create(null);
private nextEnqueueIndex = 0n;
private nextDequeueIndex = 0n;

/** Enqueues the item in O(1) */
enqueue(item: T): void {
this.data[this.nextEnqueueIndex.toString()] = item;
this.nextEnqueueIndex++;
}

/**
* Dequeues the first inserted item in O(1)
* If there are no more items it returns `undefined`
*/
dequeue(): T | void {
if (this.nextDequeueIndex !== this.nextEnqueueIndex) {
const dequeued = this.data[this.nextDequeueIndex.toString()];
delete this.data[this.nextDequeueIndex.toString()];
this.nextDequeueIndex++;
return dequeued;
}
}

/**
* Returns the number of elements in the queue
*/
size(): bigint {
return this.nextEnqueueIndex - this.nextDequeueIndex;
}
}

Transcript

00:00 Creating a well performing stack within JavaScript is

00:03 super simple and you can pretty much get away

00:04 by using the built in JavaScript array.

00:06 However, the same is not true

00:08 for creating a well performing queue within JavaScript.

00:11 And in this lesson, we will look at the reason why

00:13 and follow that up by creating your

00:15 own high performance queue.

00:17 So let's go. First,

00:19 let's take a quick look at the built-in methods within

00:22 JavaScript arrays that can be used

00:24 for creating your own stacks and queues.

00:26 Now to add items to an array one by one, the best method

00:29 that we have available is the push method.

00:31 Each call to push adds a new item at the end

00:34 of the JavaScript array.

00:36 Now, if you want to remove the last item that we added,

00:38 this will essentially give us a stack

00:40 that is the last in first out,

00:43 and we can do that with the JavaScript pop method.

00:46 Now, JavaScript arrays have another method called Shift,

00:48 which removes the first item within the array

00:51 and shifts all the other elements one index down.

00:54 However, because it has to update the index

00:57 of all the other elements

00:58 that will still be within the array,

01:00 it is not exactly highly performant.

01:02 Let's look at a quick demo

01:03 to demonstrate this performance issue.

01:06 Here we have a piece of code that creates a JavaScript array

01:09 and then simulates creating a bunch of JavaScript items

01:11 and adding them to the array using the push method,

01:14 and then removes these items in a last in first out order

01:18 using the pop method.

01:20 All of this code is wrapped in consult time,

01:23 so we get a time notification of

01:24 how much time this particular simulation is going to take.

01:28 Now we can repeat the process in a first,

01:29 in first out order, which is required

01:32 by a queue using the JavaScript shift method.

01:35 Now the performance difference over here is highly dependent

01:38 on the number of iterations that we do,

01:40 and over here we're doing a hundred thousand.

01:42 And you can see that the performance difference

01:44 between pop versus shift is quite significant.

01:47 It's five millisecond versus 389.

01:52 Now, even though the performance difference in this

01:54 particular case is quite aggressive

01:56 for most real world applications,

01:58 you probably wouldn't care.

01:59 However, if you are working in a performance intensive

02:02 application or are creating a library for someone

02:04 who cares about performance, then this is a difference

02:07 that you definitely should be aware of PAC

02:09 and create our own Q data structure,

02:11 which performs much better.

02:14 First, we will lay down the structure of

02:17 what we want our Q data structure to be.

02:19 It'll be a generic class,

02:20 just like the built-in JavaScript array.

02:23 It'll have an inq method which can add items in OF one.

02:26 It'll have a DQ method which will remove items in the first,

02:29 in first out order in OF one.

02:32 And that's pretty much it.

02:33 Now, if we didn't know any better,

02:35 we would probably start off

02:36 by creating a JavaScript array for the INQ method.

02:39 We will push it at the end of the array

02:40 and for the DQ method, we will remove it from the start

02:43 of the array using the JavaScript shift method.

02:45 But as we do know better, we know

02:47 that shift is not exactly O fun.

02:49 So let's get rid of this naive implementation.

02:52 Now, one observation that you can make over here is the fact

02:55 that you need some form of O one data structure

02:57 for your DQ operation.

02:59 And whenever you have to think of O one,

03:01 you should probably start thinking about hash maps.

03:03 And the cheapest hash map

03:04 that you can create within JavaScript is just

03:06 using a JavaScript object.

03:08 And that's exactly what we are going to do. Over here.

03:10 We create this JavaScript object that we are going to index

03:13 with a given number and the items within the object are

03:16 going to be of the type T that we want

03:18 to store within the queue.

03:20 Now, the reason why we are using a number index

03:22 for this particular object is that we are going

03:24 to track the items that have been queued

03:26 and D queued from this particular object using two

03:29 simple number variables.

03:31 Now, before we jump into more code,

03:33 let's look at a visualization to explain the strategy

03:36 that we will have for these three variables.

03:38 Think of the items that we are going to add

03:41 as indexes represented

03:42 by a line within this TETA object. We start off

03:45 With both next inq index as well as next

03:49 DQ index initialized to the value zero.

03:52 As we add new item, we will increment the next INQ index

03:56 so that we can add more items to more portions of this line.

03:59 And as we remove items,

04:01 we will increment the next DQ index

04:04 and essentially delete those items

04:06 by deleting the index in the data object,

04:08 which is represented by this line

04:10 and start returning undefined.

04:12 If the next DQ index ever catches up to the next inq index.

04:16 As this means we have run out of items to dq.

04:19 Now with that visualization out of the way, you can see

04:21 that the code for the inq method

04:23 is going to be pretty simple.

04:25 We are going to store the item at the next inq index

04:28 and then increment the next queue index

04:30 for the next inq operation.

04:32 The DQ method is going to be a bit more involved,

04:35 but nothing more complicated beyond basic programming.

04:38 The first thing that we are going to do is to make sure

04:40 that next DQ index has not caught up to the next inq index.

04:45 If it has, then outside of the F block,

04:47 the function is automatically going to return undefined.

04:51 Otherwise, we grab

04:52 The item that we plan to DQ using the next DQ index,

04:56 Delete this item from the data to free up the memory,

04:59 And then increment the next DQ index so it gets closer

05:02 and closer to the next inq index.

05:05 And finally, return the item

05:06 that we have successfully D queued.

05:09 Now that's it for the vital required methods

05:11 for the queue data structure,

05:13 and we can add a lot more methods.

05:14 For example, we can add a method called size

05:17 that returns the number of items

05:19 that are currently within the queue.

05:20 And all that we have to do for this particular case is

05:23 to simply return the difference

05:24 of the next in queue index versus the next DQ index.

05:29 Now let's jump back to a performance test to verify

05:31 that all of this work is not a complete waste.

05:34 We add a new test for the queue data structure.

05:37 We queue items using inq, and then we dq them using dq.

05:41 And if we run this, you can see that the pop

05:44 and the queue are quite similar in performance

05:47 and shift is much, much slower.

05:49 Now, even though for most particular applications,

05:51 this implementation is going to be sufficient,

05:53 there is one minor modification that we can still make.

05:57 JavaScript has this value known as max safe integer,

06:00 which is the maximum integer

06:02 that can be safely represented within JavaScript

06:05 anywhere greater than that might be clipped.

06:07 For example, max Safe integer plus one

06:09 and Max Safe integer plus two are both clipped

06:12 to the same integer value and

06:13 therefore it is not safe

06:15 to use values greater than max safe integer.

06:19 Now this can be problematic as we are using a number index

06:22 and we are implementing it arbitrarily,

06:25 but take an easy fix in modern JavaScript.

06:27 Instead of using the number type, we can use a big INT

06:30 and index by the string representation of that big int.

06:34 So we modify our data to use the string index,

06:37 change our next inq index, as well as the next DQ index

06:41 to big ins by adding the N suffix.

06:44 And then whenever we want to index the data object,

06:47 we make sure to convert the next inq index as well

06:49 as the next DQ index to the string representations.

06:54 Now because theoretically this data structure can hold more

06:57 than number, amount of items, we have

06:59 to modify the return type of the size method to be big int.

07:05 As always, you can find the code

07:06 for this particular lesson on GitHub,

07:08 and this is just one of the many ways

07:10 that you can create your own queue data

07:12 structure within JavaScript.

07:13 And in fact, we looked at another method when we created our

07:16 own W Link list.

07:18 The objective of this particular lesson was to get you

07:20 to create your own queue in the simplest way possible.