Stacks n Queues

Hey guys! This week I wanted to keep on the trend of covering some Data Structures in JavaScript as I got some good feedback on my last post. Last week we covered Linked Lists, which you can find here.

I believe Stacks and Queues are some of the more straightforward data structures, so maybe I should have led with these. Nonetheless, lets define them, walk through an example of creating them, and take a surface look at a practical case.

Queues

A queue can be thought of as a container where data goes in one side and out the other. I would say it is very similar to a lunch line. You get in the line and you will stay in that spot as the line moves forward, until you are done and leave the line… they say it is FIFO or “First In First Out”. The first record that goes into the queue will also be the first record out. Here, there is no idea of skipping or cutting the line. So, a Queue functions in this way. You can add records to the front and remove records from the back.

In JS when we want to implement a queue we usually use an array that we can restrict to just being able to add or remove elements. Why would we purposefully handicap this array to only being able to add an element to the front of the line and remove an element from the back? In a practical setting, I would say that it mainly comes down to writing clear code, so that another engineer does not misinterpret your algorithm and think they can manipulate it like any other array. But, it is more common to see queue questions in an interview.

Getting closer to writing some code, let’s think about how we would manipulate an array to add the first element and remove the last one. Well, we are in luck because there are array methods for that… QUEUE (we all knew it was coming) Array.unshift() and Array.pop(). If you’re unaware of what they do exactly, please refer to the docs linked. But, if you want to trust me, unshift will add an element to the front of an array and pop will remove the last element.

Let’s make a Queue from scratch.

We will start by creating out Queue and setting it's inner data to an array.

function Queue() {
  this.data = []
}

We will then work on our add function. Here we will simply add an element to the beginning of the queue with .unshift.

Queue.prototype.add = function(element) {
  this.data.unshift(element)
}

Finally, let's remove the last element from the queue using .pop.

Queue.prototype.remove = function() {
  return this.data.pop()
}

Stacks

A stack is very very similar to a queue. So, much of the same from above applies. You are still dealing with an ordered list of records, only this time it is FILO or “First In Last Out”. I would think about this as a stack of plates. When you stack plates one by one, the first plate ends up being at the bottom of the stack. So, if you want to get that first plate again, you have to remove every plate off of the top of the stack one by one until you are back to that first plate again.

Again, as we approach implementing our own stack, let’s think about how we would manipulate an array to look like what we described above. There are some more methods in mind for sure. How about we use Array.push() to add a record to the stack, Array.pop() again to remove the top record, and to return the top record without popping it we will need to create out own solution.

Just like as we did above, we will start off by defining our stack as having an empty array of data.

function Stack() {
  this.data = []
}

Now, we want to be able to add an element to the end of the stack instead of the beginning, so we use .push.

Stack.prototype.add = function(element) {
  return this.data.push(element)
}

When we remove an element, we still want to remove the "top" or last element, so we can use .pop again!

Stack.prototype.remove = function() {
  return this.data.pop()
}

And finally, if we want to be able to see what is on the top of the stack, we can peek at our stack.

Stack.prototype.peek = function() {
  return this.data[this.data.length - 1]
}

Practical Uses

It seems that interviews will, most often, be where you will encounter stacks and/or queues. However, a place that comes to mind where you see them both used is within the event loop. This is definitely not a topic to take a deep dive in right here, but it is also another common interview question. The event loop contains, the call STACK, the event table, and the event QUEUE. I wrote a blog a while ago called “Breaking Down the Call Stack” for a little more info on that, but I would also highly recommend you check out this article for more of a rundown on the event loop if you are curious.

Conclusion

Stacks n Queues are two very simple and similar data structures, the biggest difference being the way data is input into either, effecting how it is removed in the end.