Queue Data Structure in JavaScript

Kyle Shevlin
InstructorKyle Shevlin

Share this video with your friends

Send Tweet

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.

Jamal Butler
Jamal Butler
~ 3 years ago

Hi Kyle. I'm trying to run this in my own text editor. How can I do that? Thank you.

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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.

Jamal Butler
Jamal Butler
~ 3 years ago

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

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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.

Alex Mrynsky
Alex Mrynsky
~ 3 years ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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.

Abdulazeez
Abdulazeez
~ 3 years ago

Kyle! Thanks for this course. I actually have been finding it hard to understand data structures all these years. ! Thanks :tada:

Teddy Odhiambo
Teddy Odhiambo
~ 3 years ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

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

Teddy Odhiambo
Teddy Odhiambo
~ 3 years ago

Thanks so much Kyle! I get it now. Thanks for taking the time

Brendan Whiting
Brendan Whiting
~ 3 years ago

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?

Kyle Shevlin
Kyle Shevlininstructor
~ 3 years ago

I literally have no better answer than, "Why not? ¯_(ツ)_/¯" Both are fine.

Trung Hoang
Trung Hoang
~ 3 years ago

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.

Trung Hoang
Trung Hoang
~ 3 years ago

So we prefer "read property" to "call method"? Is it performance or other reason? Thank you.

David
David
~ 2 years ago

Curious, how come you are using unshift() and pop(), instead of add() and shift(). Aren't queues fifo?

Krono-Safe
Krono-Safe
~ 2 years ago

you mean PUSH() and shift(), david? it's the same result, in both cases, it's a fifo

Tina
Tina
~ a year ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ a year ago

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.

Kyle Shevlin
Kyle Shevlininstructor
~ a year ago

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.

Timur
Timur
~ a month ago

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

Kyle Shevlin
Kyle Shevlininstructor
~ a month ago

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.