Queues and stacks are two common data structures leveraged on technical interviews. Due to the fact that they’re quite similar in structure, they can be a bit confusing to differentiate. So today we’ll build a stack and a queue in JavaScript.
Stacks
Stacks are data structures that follow the “last-in-first-out” or “LIFO” paradigm. We can think of them like a stack of books. In order to retrieve the third book in the stack, we have to take the fifth book off first, then the fourth book, until we retrieve the third book.
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.
Benefits
Stacks allow for constant-time adding and removing of an item. This is due to the fact that we don’t need to shift items around to add and remove them from the stack.
Constraints
Stacks, unfortunately, don’t offer constant-time access to the nth item in the stack, unlike an array. This means it can possible take O(n) where n is the number of elements in the stack, time to retrieve an item.
Methods
Stacks leverage the following methods:
-
pop()
: Remove the top item from the stack -
push(item)
: Add an item to the top of the stack -
peek()
: Return the item at the top of the stack -
isEmpty()
: Returns true if the stack is empty
Let’s Build
Let’s build a BookStack which will contain a stack of our favorite novels. What’s great about stacks is that the push and pop methods are the same name as the corresponding array methods we’ll use.
Constructor
We’ll define a class BookStack and give it a constructor method that has one property:
this.stack = [];
constructor() {
this.stack = [];
}
Get
I’ll be adding a getter which returns the length of the stack. We’ll use this throughout our other methods.
get length() {
return this.stack.length;
}
Push
We want to add the item to the end of the array, so we can use the array.push()
method. The array.push()
method returns the new length array.
push(item) {
return this.stack.push(item);
}
Pop
We want to remove the last item in the array, so we can use the array.pop()
method. The array.pop()
method returns the item which was added, or undefined if the array is now empty.
pop() {
return this.stack.pop();
}
Peek
We want to return, or peek at, the last item in the stack. Thus we just need to access the value at the last index.
peek() {
return this.stack[this.length - 1];
}
isEmpty
We want to return true if there are no items in the stack. So if the length is zero, return true.
isEmpty() {
return this.length === 0;
}
Putting It All Together
Our final BookStack code looks like this:
class BookStack {
constructor() {
this.stack = [];
}
push(item) {
return this.stack.push(item);
}
pop() {
return this.stack.pop();
}
peek() {
return this.stack[this.length - 1];
}
get length() {
return this.stack.length;
}
isEmpty() {
return this.length === 0;
}
}
You can also create this with a closure.
function BookStack() {
const stack = [];
return {
push(item) {
return stack.push(item);
},
pop() {
return stack.pop();
},
peek() {
return stack[this.length - 1];
},
get length() {
return stack.length;
},
isEmpty() {
return this.length === 0;
}
}
}
Let’s test it out with some book data.
let myBookStack = new BookStack();
myBookStack.push('Oathbringer');
myBookStack.push('The Stand');
console.log(myBookStack.length); // 2
console.log(myBookStack.peek()); // The Stand
myBookStack.pop();
console.log(myBookStack.length); // 1
console.log(myBookStack.peek()); // Oathbringer
console.log(myBookStack.isEmpty()); // false
myBookStack.pop();
console.log(myBookStack.isEmpty()); // true
You can view the CodePen here.
Queues
A queue is similar to a stack in structure and methods, however the paradigm is different. Queues use the “first-in-first-out” or “FIFO” method. This can be thought of like a queue, or line, of people waiting to buy movie tickets.
The person who’s been waiting the longest in line gets served before the person who just joined.
Use Cases
Queues are very similar to linked lists and are typically used in breadth-first searches or when implementing a cache.
Constraints
Queues are much harder to update when adding and removing nodes.
Methods
Queues leverage the following methods:
-
enqueue(item)
: Remove the top item from the queue -
dequeue()
: Add an item to the top of the queue -
peek()
: Return the item at the top of the queue -
isEmpty()
: Returns true if the queue is empty
Let’s Build
For this example, we’ll be using JavaScript classes. Please refer to the stack section if you’d like to see the function closure in action.
Constructor
We’ll define a class MovieQueue and give it a constructor method that has one property:
this.queue = [];
constructor() {
this.queue = [];
}
Get
I’ll be adding a getter which returns the length of the queue. We’ll use this throughout our other methods.
get length() {
return this.queue.length;
}
Enqueue
We want to add an item to the first index in an array (the back of the queue). So let’s use the array.unshift()
method.
enqueue(item) {
return queue.unshift(item);
}
Dequeue
We want to remove the first item in the queue, or the last item in the array. We can simply use the array.pop()
method to do this.
dequeue() {
return queue.pop();
}
Peek
We want to see what the first item in the queue is. Remember this is the last item in the array. We’ll use queue[this.length — 1]
to grab this value.
peek() {
return queue[this.length - 1];
}
isEmpty
We want to return true if the queue is empty. We can use the length method to grab this information.
isEmpty() {
return this.length === 0;
}
Putting It All Together
Our final MovieQueue code looks like this:
class MovieQueue {
constructor() {
this.queue = [];
}
enqueue(item) {
return this.queue.unshift(item);
}
dequeue() {
return this.queue.pop();
}
peek() {
return this.queue[this.length - 1];
}
get length() {
return this.queue.length;
}
isEmpty() {
return this.queue.length === 0;
}
}
Let’s test it out with some names.
const myMovieQueue = new MovieQueue();
myMovieQueue.enqueue('Sandra');
myMovieQueue.enqueue('Rob');
myMovieQueue.enqueue('Lisa');
myMovieQueue.enqueue('Kai');
console.log(myMovieQueue.length); // 4
console.log(myMovieQueue.peek()); // Sandra
myMovieQueue.dequeue();
myMovieQueue.dequeue();
console.log(myMovieQueue.peek()); // Lisa
You can view the CodePen here.
I hope this tutorial gave you a better view on the differences between queues and stacks!
Top comments (23)
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? :)
Awesome post, really clear. Thanks. Just a little issue:
In this part of your post the descriptions are swaped i guess (sorry if i missunderstood your explanation).
That's what happens when you copy & paste :P
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...
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.
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)
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
Copy paste ftw
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.
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.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. :)
Sigh. Yes, I believe it’s both! 😅
A slightly faster alternative for the queue would be this:
This is awesome! Super clean! I'm pretty much a beginner with JS but what are the benefits of using a closure implementation?
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.
Oh! That's makes a lot of sense. I remember trying to do something similar to this using prototypes and it was not fun.
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...
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.
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.