DEV Community

Stacks vs. Queues In JavaScript

Emma Bostian ✨ on April 26, 2019

Queues and stacks are two common data structures leveraged on technical interviews. Due to the fact that they’re quite similar in structure, they...

Read full post

Felipe Ribeiro • Apr 26 '19

Nice article!

The only issue with implementing stacks and queues on top of dynamically sized arrays is that you don't have a guarantee on the complexity of the insertion or removal of elements, as the array might need to do some copying and resizing underneath. It might still be an amortized constant time, while a linked list would actually always give you O(1).

But maybe linked lists could be the next topic on the Data Structures With JavaScript series? :)

Felippe Regazio • Apr 26 '19

Awesome post, really clear. Thanks. Just a little issue:

enqueue(item): Remove the top item from the stack

dequeue(): Add an item to the top of the stack

In this part of your post the descriptions are swaped i guess (sorry if i missunderstood your explanation).

Emma Bostian ✨ • Apr 28 '19

That's what happens when you copy & paste :P

Geompse • Apr 26 '19

It is interesting but not true : stacks and queues are native to Javascript under the Array class. While both your classes may have a more readable usage, they have a larger memory footprint and may be slower than the native one. You might be better off extending the Array prototype and creating aliases...

diek • Apr 26 '19

Well, it is not native as we should understand native.

She is sweetening the usage of queues and stacks, people creating sugar versions of native implementations it's not only an awesome training but necessary to the community to grow.

Geompse • Apr 26 '19

I agree but when I read "JavaScript doesn’t provide a native stack data structure, so we have to build our own with an array and a closure or a class." I do not understand "Let's make vanilla Javascript easier for beginners and learn more about it.".

It was meant to be constructive, much love.

PS: The fact that in an other contexts (java...) stacks are "more native" is true aswell (and can also be detailled)

Konstantin Rouda • Apr 27 '19

I think that the description is wrong here it should be swapped and be changed to queue as we are implementing queue here and not the stack.

enqueue(item): Remove the top item from the stack
dequeue(): Add an item to the top of the stack

that is it should be set like so (and it should be changed to queue, instead of the stack)

enqueue(item): Add an item to the top of the queue
dequeue(): Remove the top item from the queue

Emma Bostian ✨ • Apr 28 '19

Copy paste ftw

edA‑qa mort‑ora‑y • Apr 27 '19

I'm a bit uncertain of your characterization of the complexity of stacks. In the general sense, stacks, independent of a language implementation, don't have any particular complexity guarantees. In the context of JavaScript, I don't believe the language guarantees any kind of complexity bounds.

In other languages, like C++, a stack/vector provides push in amortized constant time, and subscript access in constant time.

Only if your stack is implemented as a linked list would you need O(N) random access.

Nested Software • Apr 27 '19 • Edited

I believe your comment is correct, though the wording may be a bit confusing for some people. I had to read it a couple of times before it made sense to me :)

You're right that the ecmascript specification doesn't seem to provide any specific guarantee. In practice, I think we can usually count on the fact that Array.prototype.push is O(1) amortized, since that's the big-O for adding an item to a hash map, which seems to be how arrays are implemented in javascript behind the scenes.

edA‑qa mort‑ora‑y • Apr 27 '19

If I were to be pedantic, and you know how I love to be when it comes to complexity, hash maps don't have O(1) amortized push time. They have O(1) average-input (possibly amortized) push time. :)

Nested Software • Apr 27 '19 • Edited

Sigh. Yes, I believe it’s both! 😅

Daniel Santana • Apr 1 '20

A slightly faster alternative for the queue would be this:

enqueue(item) { return queue.push(item); }
dequeue() { return queue.shift(); }
peek() { return queue[0]; } // no need to calculate the length of the array or any math ;)

Corey Johnson • Apr 26 '19

This is awesome! Super clean! I'm pretty much a beginner with JS but what are the benefits of using a closure implementation?

Emma Bostian ✨ • Apr 26 '19

In all honesty, I'm not sure about the benefits. Previously, JS didn't have "class" syntax, therefore closures were necessary. But when the class keyword was released with ES6, I believe, that provided a new way to write this type of data structure.

Corey Johnson • Apr 26 '19

Oh! That's makes a lot of sense. I remember trying to do something similar to this using prototypes and it was not fun.

Dilantha • Aug 17 '19

Nice article. Thanks for sharing. Considering @geompse 's suggestion, I also tried an alternative approach using es6 classes and Array class. Let me know what you think. dev.to/dilantha111/stacks-and-queu...

Nicholas Fazzolari • Apr 26 '19

Great post. I remember having to implement these data structures in C++ a few years back. I need to review that code again. No memory management/pointers in JS makes the high-level mechanism of the particular data structure easier to see. Very cool.

Pankaj Sharma • Apr 28 '19

Hello, first of all thanks for sharing this amazing article. I am new in JS and I understand both concept of Stack and Queue. I am curious to know how to use this method in real world. For Example If I want to search data from an array (Book 3) like your book example which is best way to start search LIFO or FIFO.