Musings on Data Structures: Part 4 — Stacks & Queues — Javascript

Data Structures: Stacks & Queues — from a Javascript perspective.

Stacks and queues are extremely common data structures. Now, there are differing views as to whether stacks and queues are actually data structures or if they are ‘more of a pattern that is implementable…with other data structures.’¹ This article will stick with the school that views them as data structures, even though I fully understand the train of thought that when we use stacks and queues while working with other structures, they become more of a pattern of usage.

Stacks and queues are both linear data structures and are collections, or storage units, for data. Linear data structure[s] have data elements arranged in sequential manner and each member element is connected to its previous and next element.² Stacks and Queues are part of a subset of Sequential Access Data Structures called Limited Access Data Structures. Like linked lists, their information can only be accessed in a certain order.³ Both stacks and queues are flexible in their sizes, meaning you do not have to first declare the size of either, they can grow as necessary, if elements are added. The biggest difference between the two comes to how elements are removed from each structure.

With the data structure of a Stack, the principle of last in, first out is followed (LIFO) (or some even less commonly say first in, last out (FILO)). So many posts use the example of plates when talking about stacks, but my favorite reference is to that of a Pringles can: Each crisp is added to the can one on top of the other, and in order to take one out, we take a crisp off the top, the last one that was added to the can or stack. We don’t want to (and usually can not or should not) take an element from lower down or the bottom of the stack, this would be a lot of work even if we could. Although there are many data structures that rely on the pattern of a stack, I think it’s important to point out that we use stacks all the time in Javascript → our call stacks in js for our async methods!

The most common methods that we use on stacks are .push() and .pop(), with .push() being used to add elements to our stack, and .pop() used to remove elements from the top (or end) of our stack.

Below I will create a stack using Javascripts’ Classes. There are many examples of constructing the data using an array, but I really appreciated how Beiatrix constructs the class with the storage container being an object⁴. I am going to follow her example and then add some other methods that pertain to stacks. If you’d like to see how to construct this using an array, this blog has a great example here.

Let’s set up a quick example below and show the return values of each method.

With the data structure of a Queue, the principle of first in, first out is followed (FIFO). A queue is just like a waiting line queue: Whomever was added to the waiting line first, will be the first person to leave the line. The person who has been waiting the longest will be the first person helped. Queues take much longer to update when removing nodes.

The methods that queues use most are .enqueue() and .dequeue(), with .enqueue() (or .push()) being how we add elements to the queue and .dequeue() (or .shift()) being how we remove elements from the queue.

We can now implement this with Javascript classes again, adding a couple other methods that are useful on a queue. Again, I’m using Beitrix’s example to build this, because I love how she builds the class constructing a head and a tail for the queue → showing how queues are useful for building linked lists (and also for building a cache — which will be my article topic next week)

We can now set up a new object of a queue, perform the above operations on the queue and show return values of each method:

Big O’s

For stacks, the .push() and .pop() methods both have a runtime of O(1).

For queues, the .enqueue() method has a runtime of O(1), but the .dequeue() method has a runtime of O(n) because it must reassign the place in the memory for each element, looping through the rest of our data and re-index everything after the element that we have removed (remember: we removed the first element in the queue).

1. Exploring Stacks and Queues via JavaScript | Joshua Hall | “https://www.digitalocean.com/community/tutorials/js-stacks-queues”
2. Difference between Linear and Non-linear Data Structures | “https://www.tutorialspoint.com/difference-between-linear-and-non-linear-data-structures”
3. Time spent as a Novice Apprentice at 8th Light | “http://noviciateinitiate.blogspot.com/2014/01/an-array-is-example-of-whats-called.html”
4. Stacks & Queues — Data Structures in JavaScript | Beiatrix | “https://youtu.be/1AJ4ldcH2t4”