Stacks and queues. How fun. I'm sure you've heard of these in coding interviews or while learning computer science (ew, why were you?). They're two of the easiest data structures out there, and in this article, I'll be explaining each one of them to you along with their JavaScript implementation.
Stacks and queues are very important for you if you're looking to get hired, since most "traditional" programming interviews ask you about DSA, and DSA content isn't easy to come by. Read the article carefully, take plenty of notes and don't forget to wear your seatbelt!
What are Stacks?
Stacks are LIFO data structures, meaning Last In First Out. If you imagine a bunch of plates stacked over each other, you can't directly take out the one at the bottom. That would topple the entire structure. Rather, you must take out the last one put on top, and the one before that, and the one before that.
Where are stacks used?
Undo/redo features - Often, applications remember the last user action and that action is the first one to be 'undo'-ed.
Routing - The history in our browser is treated like a stack, since when we click the back button, we're taken to the previous page, the one before that, and the one before that, just like a stack.
Implementing Stacks
For implementation, I'll be making a class in JavaScript called Stack, since it's a lot more modular and easier to understand visually. We'll also be having a common class called Node for implementing both stacks and queues.
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
A Node simply acts as an element inside a data structure. Our node has two properties: val, which is the value of the Node, which could be an integer or string or whatever, and next, a way of expressing the element right after it (or below it, as in a stack).
Our Stack constructor will be as such:
class Stack {
constructor() {
this.first = null
this.last = null
this.size = 0
}
}
Stack has three properties: first, indicating the first element that will be withdrawn, last, indicating the element at the very bottom of the stack, and size, which we'll be returning to the user after every operation on the stack.
What functions will our stack be needing?
Push - We need to be able to add an element on top of the stack.
Pop - We need to be able to take away the element on top.
Let's write these functions one-by-one, inside the Stack class itself.
push(val) {
const newNode = new Node(val);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
let temp = this.first;
this.first = newNode;
this.first.next = temp;
}
return ++this.size;
}
In push(), we're first creating a new instance of Node. Next, we check if this.first is null. Since at initialization that is the case, the if-block will only run if we're adding our first element to the stack. In that case, we're setting both this.first and this.last to be our new node.
If we already have elements in our stack, we assign the current this.first to some temporary variable. We set the stack's first to now be our new node, and our new first's .next to be temp, which is our previous stack. Lastly, we return the incremented stack size.
So in essence, instead of putting a plate directly on top, we're shifting our previous plates' stack, placing our new plate on the bottom, lifting it and placing our previous plates below it. Pretty confusing, I know. If you're having trouble visualizing this, get a pen and paper, and manually try to implement our newly created push() function.
pop() {
if (!this.first) return null;
const temp = this.first;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.val;
}
In pop(), we first check if there's no this.first. If that is the case, we return null, since we can't return any item by popping the stack. Next, we assign this.first to a temporary variable, to preserve its value. Next, we check if this.first equals this.last. Why? If you recall, the only time they're equal is when only one element in present in the stack. So we just set this.last to be null. What about this.first?
We're setting this.first to equal its next element, so everything right after it. If this.first is the only element remaining, its next property would be null, meaning the new this.first would be null, hence resetting our stack. We decrement the stack size and return the value of our previous element on top.
I recommend you try out the code in the browser console on this very tab and experiment with it.
Hopefully, you've understood my rather cryptic explanation. If you haven't, please comment, I'd love to help you out.
Well, that's stacks for you, next up: queues.
What are Queues?
A queue is a FIFO data structure, meaning First In First Out. You can relate this to a queue in real-life. If a queue in real life was a stack, meaning the last one in gets out first, it would be pretty darn unfair! Queues are often used in background tasks on your computer, resource allocation and task completion too.
For the Queue, we'll also be using our Node class. Here's the constructor for our Queue:
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
}
Very similar to Stack. Now, the push() and pop() methods. Actually, for queues, the terminology is a little different. Push is called Enqueue and Pop is called Dequeue. So let's make these functions now!
enqueue(val) {
const newNode = new Node(val);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
We check if there's no element already in the queue, and if so we set both this.first and this.last to be our new node. Very similar to a stack so far. However, if there are already elements in the queue, we change the next property of the current last element to be our newly created element and we set this.last to our new node. Lastly, we return the incremented queue size.
dequeue() {
if (!this.first) return null;
const temp = this.first;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.val;
}
For dequeue, we're first checking if this.first is null, and so we're returning null. We assign our current first element to some temporary variable. this.last is being set to null if both this.first and this.last are equal, which, as you know, only happens when there's one element in the queue. Next, we set this.first to be the next element of the current this.first. Lastly, we decrement the size of the queue and return the value of our extracted element.
Conclusion + Finished Code
I hope I've been able to explain to you the intricacies of data structures like stacks and queues. If you have any knowledge about stacks and queues and would like to share them, please write a comment.
Here's the complete code:
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class Stack {
constructor() {
this.first = null
this.last = null
this.size = 0
}
push(val) {
const newNode = new Node(val)
if (!this.first) {
this.first = newNode
this.last = newNode
} else {
let temp = this.first
this.first = newNode
this.first.next = temp
}
return ++this.size
}
pop() {
if (!this.first) return null
const temp = this.first
if (this.first === this.last) {
this.last = null
}
this.first = this.first.next
this.size--
return temp.val
}
}
class Queue {
constructor() {
this.first = null
this.last = null
this.size = 0
}
enqueue(val) {
const newNode = new Node(val)
if (!this.first) {
this.first = newNode
this.last = newNode
} else {
this.last.next = newNode
this.last = newNode
}
return ++this.size
}
dequeue() {
if (!this.first) return null
const temp = this.first
if (this.first === this.last) {
this.last = null
}
this.first = this.first.next
this.size--
return temp.val
}
}
Thanks for reading this article, I hope you learnt something new and enjoyed it! If you'd like more content, consider pressing the favourite button and giving some feedback in the comments section. If you're interested in more content, check out my blog and subscribe to my newsletter if you don't want to miss future articles!