Data Structures: Improving Time Complexity on Stacks and Queues

How to use stacks and queues as your app scales

Photo by noor Younis on Unsplash

Background

In my previous blog, I provided an introduction to a niche data structure called stacks and queues. If you are unfamiliar with it, please take a quick look at my blog Stacks and Queues.

In a nutshell, stacks and queues follow the principle of first-in-last-out (stacks) and first-in-first-out (queues). However, for out-of-the-box JavaScript array methods, the time complexity for stacks is O(1) and the time complexity for queues is O(n).

Which led me to think, can we do better? Specifically, can we improve the time complexity for queues to be faster than O(n)?

Inspiration

Before we dive further, I would like to thank Rud, who introduced me to the concept of circular arrays to improve the time complexity for stacks and queues. My research on circular arrays was what inspired me to create my own stack and queue array class.

Although I am not diving deep into circular arrays for this blog, I am using the same principles I learned from studying circular arrays and leveraging them for my stack and queue array class.

Stack and Queue Class Overview

Before we dig too much into the weeds and code, let’s provide a general overview of how we’re going to create the StackQueueArray class.

For the stack portion, since the time complexity is O(1) with out-of-the-box Javascript array methods, I decided to keep using the same methods (i.e., .push() and .pop()). It doesn’t make sense to reinvent the wheel when it’s working perfectly fine, especially when its already optimized.

For the queue portion, that’s where I had to think outside the box. We will still be leveraging the .push() method but the .shift() method will need to change. After all, the .shift() method is the reason why the time complexity is O(n).

This is where leveraging principles from circular arrays come in. Based on my research, an implicit assumption made about circular arrays is that they have a fixed length.

Typically, a circular array has a pointer for the head and tail of the array. By keeping track of the pointers of where the head and tail are at all times, you can figure out if there is space in the array to add an additional element.

In other words, if the head and tail are not next to each other, then you can add the element.

However, in JavaScript, thanks to it being a dynamic language, we don’t have to worry about memory allocation. This dissuaded me from using circular arrays but inspired me to use a pointer to keep track of the head of the array.

We don’t need a pointer for the tail because the tail will always be the last element of the array.

So, how are we going to use a head pointer in conjunction with our custom .shift() method?

Let’s establish a new array with the StackQueueArray class and push some elements into them.

Don’t worry about the class methods for now as we will dive into detail about what those will be later. Recall that the .push() function will be the same as the out-of-box .push() function.

let array = new StackQueueArray()
array.push(10)
array.push(20)
array.push(30)
console.log(array) // [10, 20, 30]

In the StackQueueArray class, it will have an attribute called headIndex, which will be our head pointer. Currently, in array, the headIndex should be 0 because 10 was the first element push into the array as per the first-in principle.

console.log(array.headIndex) // 0

Now, with our custom .shift() method, we’re going to leverage another principle I learned from circular arrays.

In a circular array, whenever there was space between the head and tail pointers, the empty spaces were filled with null as placeholders. We’re going to do the same thing whenever we invoke our custom .shift() method.

When .shift() is invoked, it’ll swap the value at the headIndex with null, increase headIndex by 1 to assign the head pointer to the new head, and return the value.

So, in pseudo code, it will look like this:

console.log(array) // [10, 20, 30]
console.log(array.headIndex) // 0
array.shift()
console.log(array) // [null, 20, 30]
console.log(array.headIndex) // 1

Let’s really drive it home and invoke our custom .shift() method again to our current array to solidify what the method should be doing.

array.shift() 
console.log(array) // [null, null, 30]
console.log(array.headIndex) // 2

Now that we have a more holistic understanding what the methods are supposed to do and the general idea of the class, let’s break it down into code.

Note: For the purposes of brevity and explanation, the code for the StackQueueArray class below will only take into account normal cases. There were many edge cases to consider, which I will go over in another section, and I will provide the complete code of the class at the end of this blog.

Push and Pop Functions

Let’s start with what we’ll need for the StackQueueArray class. We’re going to initialize an empty array and the headIndex.

So far, so good. We initialized the headIndex to null because the array is empty, so there is no need for a head pointer yet.

Next, let’s go into the .push() and .pop() functions. Recall that we will be leveraging the out-of-the-box methods that are already provided by JavaScript.

First, let’s do the .push() function.

In the if statement, this only occurs when the array is empty. We would start the headIndex at 0 because when you push an element to an empty array, it will be at index 0.

Next, let’s do the .pop() function.

I am using the out-of-the-box .pop() function from JavaScript and using it as my own.

Shift, Head, and Tail Functions

Well, time for the hard part, making the custom .shift() function. For a normal case, let’s assume we already have [10, 20, 30] as our array. The headIndex is at 0 for this case.

The following are the three steps we need to do based on what I said in the “Stack and Queue Class Overview” section.

1. Swap the value at the headIndex with null.
2. Increment the headIndex by 1.
3. Return the value at the previous headIndex (the value prior to incrementing headIndex).

Since we need to return the value, we should save it in a separate variable.

For the sake of saving space, I am going to be working on the .shift() function separately and then inputting it into the class once it’s complete. The array and headIndex are still referenced from the previous code.

Seems pretty good so far!

We can also include some helper functions to find what the head and tail are to alleviate the pain of parsing through the entire array.

Since we know the tail is always at the end of the array, we can use the length of the array as our reference point. For the head, we already have a head pointer, which is our headIndex.

Great, now let’s add these methods to the StackQueueArray class!

And viola! We’ve created the skeleton of the StackQueueArray class.

If you were able to follow along thus far, you’re more than halfway there! The next steps would be taking into account edge cases… and there are a lot of them.

If you want to challenge yourself, try to think of all the edge cases that could possibly happen with this class. This is especially good practice for code challenges and coding interviews since it is the developer’s responsibility to take into account all possible edge cases.

Personally, I don’t even know if I thought of all the edge cases myself.

Edge Cases Galore

There are six unique edge cases to consider. Some of these edge cases repeat in different methods.

The gist below shows the full code for the StackQueueArray class that I made. There is an additional method that I made, called cleanUp(), which I will explain later.

Edge case 1

All of the elements are null. This typically occurs when .shift() is invoked all the way to the end of the array.

Edge case 2

There is only one non-null element in the array. This only occurs for the .pop() method because, after invoking it, the array will be empty, implying that headIndex should be null.

Edge case 3

The tail of the array is the last non-null element. This only occurs for the .pop() methods because after invoking it, we need to re-assign the headIndex by decrementing it by 1.

If we don’t decrement it, the headIndex will be outside the scope of the array itself.

Edge case 4

The array is either empty or all elements in the array are null.

Edge case 5

No parameter was used for the .push() method. This is geared towards user error where they may have forgotten to put in a value or decided to put in null as a value.

Without a parameter, .push() will push undefined into the array. Pushing undefined or null into the array will break the class and also violates the basis of a stack and queue data structure.

Before we jump into edge case 6, let me explain the purpose of the .cleanUp() method.

cleanUp() Method

I made .cleanUp() with the thought of what happens if you only invoke the .push() and .shift() methods multiple times. For example, the array could look like it has a bunch of null values and two non-null values at the end.

console.log(array) 
// [null, null, null, null, null, null, null, null, null, 10, 20]

As mentioned before, the null values just represent a place holder for where the previous heads used to be. We don’t really care about these null values anymore.

But what if you have a memory requirement or you’re running out of memory to store this array?

This is where the inspiration for the .cleanUp() method came from. We can invoke this method to shorten our array to take up less memory by removing all the null values.

So, in pseudo code, it’ll look like the following:

array.cleanUp()
console.log(array) // [10, 20]

However, this introduces two edges cases: edge case 1 and edge case 6. We already took into account edge case 1, where all the elements in the array are null. For this edge case in this method, we would revert back to the initial conditions of the class.

Edge case 6

The array is empty or the array only contains non-null elements.

For edge case 6, we wouldn’t change the array in any way and let the user know that there are no more null values in the array.

Time Complexity of the StackQueueArray Class

Give yourself a pat on the back if you’ve made it this far. This is a lot of information to process, especially if you read my previous blog on stacks and queues on top of this one.

Remember, the original goal was to improve the time complexity from O(n) to O(1). Let’s take a look at the time complexity of each class method to see if we achieved that.

.push(): For this method, we’re doing five actions: declaration, incrementation, boolean comparisons, accessing an element in an array, and using the out-of-the-box .push() method.

Each of these actions has a time complexity of O(1), which means this method’s time complexity is O(1).

.pop(): For this method, we’re doing five actions: declaration, decrementation, boolean comparisons, accessing an element in an array, and using the out-of-the-box .pop() method.

Each of these actions has a time complexity of O(1), which means this method’s time complexity is O(1).

.shift(): For this method, we’re doing four actions: declaration, incrementation, boolean comparisons, and accessing an element in an array.

Each of these actions has a time complexity of O(1), which means this method’s time complexity is O(1).

.head(): For this method, we’re doing three actions: declaration, boolean comparisons, and accessing an element in an array.

Each of these actions has a time complexity of O(1), which means this method’s time complexity is O(1).

.tail(): For this method, we’re doing three actions: declaration, boolean comparisons, and accessing an element in an array.

Each of these actions has a time complexity of O(1), which means this method’s time complexity is O(1).

.cleanUp(): For this method, we’re doing four actions: declaration, boolean comparisons, accessing an element in an array, and using the out-of-the-box .slice() method.

Each of these actions has a time complexity of O(1) except for the .slice() method.

The .slice() method makes a copy of subarray based on the input range provided in the parameters. In the worse-case scenario, it can copy the entire array, which is dependent on the array’s length.

Based on this, the time complexity of the .slice() method is O(n). This implies that, in the worst-case scenario, the .cleanUp() method has a time complexity O(n).

It looks like every method, except for .cleanUp() , has a time complexity of O(1). Would we count this as a success? Yes! And here’s why.

Recall that .cleanUp() was originally made to help with allocation, not with time complexity. You can think of this method more as a nice-to-have method rather than a necessary method.

This method does not directly affect the crux of the stack and queue data structure. If we didn’t have the .cleanUp() method in the StackQueueArray class, the class can still be used for any data structure that implements stacks and queues assuming that memory is not an issue.

If we ignore the .cleanUp() method now, then the overall time complexity for the StackQueueArray class is O(1)!

We successfully improved the time complexity of stacks and queues from O(n) to O(1)!

Conclusion

Notice in the StackQueueArray class, we didn’t use any special functions or something uncommon. Everything we coded in the class was out-of-the-box methods, properties of an array, and boolean comparisons.

All it took was some creativity to build out a new class and now we have a class that is faster than using out-of-the-box methods for stacks and queues.