Queue Data Structure in JavaScript
In this lesson, you will learn how to create a queue in JavaScript. A queue is a first-in, first-out data structure (FIFO). We can only remove items from the queue one at a time, and must remove items in the same sequence as they were placed in the queue.
Instructor: [00:00] To create our queue data structure, we're going to use a factory function that returns our queue as a plain JavaScript object.
[00:08] A queue is a collection of items that obeys the principle of first-in/first-out. When we place an item into the queue, we can only get it out after all the other items that have been added before it have been removed.
[00:20] Our queue will have several methods and properties -- an add or enqueue method, a remove or dequeue method, a peek method to look at what's next to be removed, a length property, and lastly, an is-empty method.
[00:36] In order to store our items, we'll use an array-held enclosure. Let's start with our enqueue method. We want to keep our collection in the correct order, so we always want to add to the array from one side of it and remove items from the other.
[00:52] We'll add items to the front of our array for enqueue with the array unshift method. Next, we'll create our dequeue method using array.pop to remove the final item from the array. This ensures we maintain order in our queue and every good queue is orderly.
[01:08] Next, we'll create our peek method that will return the item that's next to be removed. Now we'll create our length property. We need to use a getter for this.
[01:18] If we just associate queue.length with our length key, we'll get the value zero because that's the value of queue.length when our object is created. Instead, we want to use a getter function that always returns us the current queue's length.
[01:34] Lastly, let's create our is-empty method. Now we can try our queue out. A great use for a queue is a plan. A plan is a collection of steps that needs to happen in a particular order, so let's use a queue to make our plan.
[01:48] We'll create our queue, and just for good measure, let's test out our is-empty method right away. When we log it out in the terminal, we see that it's true. Our queue is empty. Let's add a few items to our queue. How about "Make an Egghead Lesson," "Help Others Learn," and "Be Happy"?
[02:06] Now if we peek into our queue, we should see "Make an Egghead Lesson." Yeah, that works. Now I've made the lesson. You're watching it, so let's dequeue it.
[02:15] If we peek again, we should say, "Help Others Learn." Since I'm almost done with the lesson, and I've taught you how to build a queue, I think I've helped you learn. Let's dequeue that as well.
[02:25] If we peek one more time, it says, "Be Happy." I think we're all happy that we learned how to make a queue. Let's dequeue that and then verify that our queue is empty.
Probably the best way to do so would be to get the code from the repo and copy it into your editor. You can find the code at https://github.com/kyleshevlin/intro-to-data-structures-and-algorithms and it's in the queues directory.
I got through 1:57 of the first video and didn’t know hoe to run it in the terminal.
jamals-MacBook-Pro:data_structures_and_algorithms_javascript jamalbutler$ node index.js jamals-MacBook-Pro:data_structures_and_algorithms_javascript jamalbutler$ npm start
Assuming you have Node installed, and you're in the correct directory and have copied the code to an index.js file, node index.js should be sufficient. My guess is you haven't named your file correctly or you don't have Node installed, problems that I unfortunately can't really address.
I would be great to mention time complexity for data structures that usually is very important on the interview. For example, the time complexity for the enqueue method is O(n) because of unshift method that is not optimal for the queue. We could achieve O(1) time complexity by using a linked list.
I agree Alex, and that's a great point. Explaining Big O notation is challenging to do in the screencast format, since we strive for showing instead of explaining (no one wants to stare at a screen that's not changing while someone talks at length about something). It's one of the philosophies of egghead to direct the user. If I can come up with a quality way to explain big O while directing the user, I will be glad to make that update to the course. That being said, in the sorting lessons, I talk about Big O in the descriptions. Perhaps I can add a note about them here as well.
Kyle! Thanks for this course. I actually have been finding it hard to understand data structures all these years. ! Thanks :tada:
hi Kyle, I did not quite get the reason for the length being implemented as a getter vs a normal method. Could you help me understand? I tried both approaches, and they both seem to work well.
Yeah, the reason is simple. If you write it as a property such as length: arr.length the value of length is 0 when the object is created and arr.length is never read again when you read from the queue's length property. You can enqueue all you want and you'll still get 0.
By using the getter, we now read the internal array's length property every time, guaranteeing it's correctness. You could accomplish this by making the queue's length key a method instead of a property, but you'd have to call it rather than read from it.
I made a small JSBin to demonstrate the issue: https://jsbin.com/zayikiqobe/edit?js,console
Thanks so much Kyle! I get it now. Thanks for taking the time
I know this isn't exactly the subject of the course, but why are we choosing to use a factory function and keep the array of queue elements in a close, as opposed to a class with a class property and methods?
I literally have no better answer than, "Why not? ¯_(ツ)_/¯" Both are fine.
By using the getter, we now read the internal array's length property every time, guaranteeing it's correctness. You could accomplish this by making the queue's length key a method instead of a property, but you'd have to call it rather than read from it.
So we prefer "read property" to "call method"? Is it performance or other reason? Thank you.
Curious, how come you are using unshift() and pop(), instead of add() and shift(). Aren't queues fifo?
you mean PUSH() and shift(), david? it's the same result, in both cases, it's a fifo
How would you call the "get length" function? console.log(q.length())? But this will gives me an error in the output saying q.length is not a function.
How would you call the "get length" function? console.log(q.length())? But this will gives me an error in the output saying q.length is not a function.
Hi Tina, getters are accessed like properties and aren't called like methods. So use q.length instead of q.length(). Hope that helps.
Getting back to people, sorry it's been so long.
Trung, I just like factory functions. I think they're more natural for JavaScript. You can have actual private methods and variables. We'll soon have private methods and values on JS classes, but traditionally JS classes did not have this feature.
David, add is not an array method. unshift adds an item at the start of an array and pop removes the item at the end of the array, leading to FIFO. We could just as easily do the opposite by pushing on the end of the array and shifting off the front. Either way, you get a FIFO.
Hello! I don't understand that moment: why for getLength method we are using getter (to dynamically get relevant value of length, i red comments above, BUT 👇). And meanwhile for the isEmpty method we call queue.length without getter, so according to logic that length never will be read again after declaration. Thanks
Hi Timur,
queue.length will get the current length of the queue from a method or function. It will access the queue held in closure and get that property.
The difference for the queue's length property is that we're setting the length key to the value of queue.length at creation of the object. I chose to use get length() so that when someone wants to get the length of a queue they created, like const q = createQueue() and q.length, they could use length like a property and not a method.
If I wrote queue.length() instead, that is as a method, like so:
length() {
return queue.length
}
Then this would also always be correct, as it would be accessing the queue in closure and getting the current length. The difference being, the user of createQueue would have to do q.length() to get the length, instead of just q.length.
Hi Kyle. I'm trying to run this in my own text editor. How can I do that? Thank you.