How JavaScript works: Stacks and Queues + tips for efficient implementation

Published in

SessionStack Blog

11 min readOct 14, 2021

This is post # 48 of the series, dedicated to exploring JavaScript and its building components. In the process of identifying and describing the core elements, we also share some rules of thumb we use when building SessionStack, a JavaScript tool for developers to identify, visualize, and reproduce web app bugs through pixel-perfect session replay.

In this article, we will look at Stacks and Queues which are common data structures that have a lot of real-world use cases. They are both linear data structures that have elements next to each other. You can think of a Stack as a pile of plates placed on a table, each plate being on top of the other. Also, think of a Queue as a line of people at the airport waiting for their turn to get a boarding pass, each individual linearly following another one.

Do not forget that Data structures are divided into two categories: linear and nonlinear. Stacks and Queues do form a sequence because they are linear.

We will look at the use cases, implementations and compare both data structures.

Have it in mind that our programming language in focus is JavaScript for the implementation but the idea is generic and does not depend on the particular implementation.

Stacks

Stacks are linear data structures that allow operations only on one end, meaning that all basic operations like insertion can only be done at the ends of the structure. This reason is because of the concept of Last in First Out(LIFO) where the last data placed will be the first data to be removed.

As stated earlier, we can take Stacks like a pile of plates, each plate placed on top of each other. The first plate that is placed becomes the last to be removed.

In the image above, the push adds an element to the Stack while pop removes the available on top. Push and Pop are the basic operations carried out on Stacks but there are more which we will discuss later in the article.

It is important to note how important Stacks are in real-world examples. Elements are stored in an ordered manner which makes them more applicable to a lot of scenarios.

Use cases for Stacks

A common real-life example is a stack of plates where you can add or remove from it, which explains Stacks to a 5-year-old.

Browsers use the Stack data structure as well to keep records of your browsing history where the last visit is the first on the record. So, if you use the back button you then go to the last visited site.

Same as call logs where your recent calls are placed on top of each other. Undo/Redo mechanisms in text editors use the Stack data structure to keep track of recent activities.

Reversing a word is applicable using Stack where we can pop the letters out and what we get becomes the reverse.

Another application of Stack is in the Tower of Hanoi and it is the most optimal way of solving this puzzle. The goal of the puzzle is to move all the disks from one rod to the next rod.

Other use cases for Stacks include the following;

Recursion handling
Backtracking
Function calls in a Compiler
Most JVMs are Stack oriented.

Basic operations

Stack supports two basic operations which are;

push — inserts into the stack.
pop — deletes from the stack.

Other operations are also available but their functionality is to check the status of the Stack, unlike the insertion and deletion operations. And they are;

isFull — checks if the stack is full.
isEmpty — checks if the stack is empty.
peek — gets the element at the top of the Stack.

In practice, you tend to see isFull, isEmpty and peek operations but they are not always required. The most used and important are push and pop because you need to add and remove items in the Stack.

Let us look at the algorithms we will use for each of these operations:

Push

Pop

isFull

isEmpty

Peek

Implementation

We should have a basic understanding of how a Stack works by now, the basic operations, and a few use cases but how do we implement it? Stacks have generally been easy to grasp and also one of the most used data structures. Implementing a Stack data structure can come in a few ways, the common ones being an array and a linked list. Because of this common way of implementing a Stack it is now being regarded as an Abstract Data Type (ADT). It is now up to you to decide how you want to implement a Stack, as long as the main operations push and pop do not change.

In JavaScript, the array already has the features we need to use on a Stack which is why we will use the array to implement on our implementation.

We created a Stack with two attributes count and the location of the elements will be storing. If you noticed, this.data is an object instead of an array because we would not learn much if we used an array. We could have just used the already existing array methods.

Our first operation which is the push the method takes in an element that is being stored at the position of the count and the count is incremented immediately after the element is added.

Our next method will help check if the count is at 0 which means our Stack is empty. This method is useful in pop in case we have to check if the Stack is empty before we remove an element.

The pop method checks if the Stack is empty before it performs the deletion. The count is decremented and the data in that location is then deleted.

The Peek method returns the element at the top of the Stack without removing it.

Queue

This data structure is exactly what it means in a real-world application. It follows the pattern that whatever goes in first will go out first. We had seen from Stacks how it follows the Last In First Out pattern. Queues follow the First In First Out pattern. Operations tend to happen on both ends in Queues. The data is inserted through the rear/tail of the structure while removing data only happens at the front/head of the structure.

A better definition of a Queue in my perspective is a data structure that is only restricted to inserting data through the front and deleting data through the rear. This is a linear data collection and the data here can be of any data type:

The Queue works on a first come first serve scenario meaning it is nothing more than a general queue in an airport terminal or a movie ticket queue.

Use cases for Queues

The most common use case is a queue at either a bus station, movie ticket or anywhere you have to wait for your turn to get served or attended to. This pretty much explains that whoever comes first gets served first. But our main focus is how Queue works on a computer.

Another use case is when a resource needs to be shared or served but this resource can only handle or serve one request at a time. Meaning that each request has to wait for its turn to get the resource. It makes more sense to queue up these requests so each is handled in turns.

Looking at it from another perspective, imagine an office with just one printer connected to many computers. If 3 computer users need to print a document, the printer doesn’t reject them if they come at the same time. It puts the requests in a queue. Ready Queue which is a type of Process Scheduling Queue manages all the computer users so the oldest request gets to print their desired document first.

Also, in the Tree data structure, level order binary tree traversal uses a queue to keep track of the nodes it visits when searching.

Basic operations

There are two basic operations used by Queues. These operations involve only adding data to the queue — the first data will also initialize the Queue before it gets added to it, while the second operation removes data from the Queue. We will discuss the basic operations that work with Queues:

Enqueue — adds an item to the queue.
Dequeue — removes an item from the queue.

Just like Stack, we also have a few more operations, they do not manipulate or move the data but check the status of the Queue.

Peek — gets the data at the front of the Queue.
isEmpty — checks if the memory(Queue) is empty.
isFull — checks if the memory is full.

Enqueue

Most people like to name it as a push. Let’s look at a simple algorithm for adding data to a Queue.

Dequeue

Peek

isEmpty

isFull

Implementation

Let us implement the fundamental operations of a Queue which are just Enqueue and Dequeue.

Before we begin creating a Queue and its methods, let us create a Node class. This Node class will contain the value of the data added to the Queue and a pointer to the next Node:

Next, we create the Queue which holds two properties: the front and back of the Queue. The reason why we first create the isEmpty() is not to write redundant code in the enqueue and dequeue methods.

The enqueue method first adds the new node, checks if the Queue is empty so it adds this new node to the Queue which means the front and back are being occupied by the new node.

Also, if the Queue wasn’t empty, we just add the node to the rear/back of the Queue.

The next method which is dequeue goes to the front of the Queue, also checks if the Queue is empty. If it’s not empty we make the front node point to the next node in the Queue.

Stacks vs Queues

Stacks and Queues are always the most discussed data structures. This is because they both have opposite operations. Stack follows the pattern LIFO — Last In First Out whereas Queues uses FIFO — First In First Out. A common example of a Stack is a pile of plates while that of Queue is a queue at a bus station.

Also, Stacks have a top property that points to the topmost element on the Stack. That’s used to keep track and perform all the operations. But Queues have two properties that are the front and the back to insert and delete the items in the Queue.

Stacks are mostly used in compilers to process statements. For example, there are two components in the V8 engine which are the Heap and the Call stack. The Call stack uses the LIFO to store the function calls where each function call is pushed to the top of the Stack.

Queues are mostly used for messaging systems like RabbitMQ. This happens when a process sends a message to another process to use. The message is first queue and sent out using the FIFO pattern.

You have to be very careful about the data structures you pick for certain tasks, especially for ones that could potentially degrade the performance of your product. Having an O(n) lookup complexity for functionality that has to be real-time and depends on lots of data could make your product unusable.

Even if you feel like the proper decisions have been made, it’s always necessary to verify that this is indeed true and your users have a great experience with your product.

A solution like SessionStack will allow you to replay customer journeys as videos, showing you how your customers actually experience your product. You can quickly determine whether your product is performing according to their expectations or not. In case you see that something is wrong, you can explore all of the technical details from the user’s browser such as the network, debug information, and everything about their environment so that you can easily understand the problem and resolve it.

There is a free trial if you’d like to give SessionStack a try.

If you missed the previous chapters of the series, you can find them here:

How JavaScript works: Stacks and Queues + tips for efficient implementation

Stacks

Use cases for Stacks

Basic operations

Push

Pop

isFull

isEmpty

Peek

Implementation

Queue

Use cases for Queues

Basic operations

Enqueue

Dequeue

Peek

isEmpty

isFull

Implementation

Stacks vs Queues

Published in SessionStack Blog

Written by Victor Jonah

No responses yet