Queues: A Tale of Two Stacks

HackerRack Stacks and Queues JavaScript Solution

I recently completed this HackerRank Problem, that I found very clever and wanted to share! I had compartmentalized the use of stacks and queues separately in my mind, so this expanded my thinking to outside the box. Let’s checkout the problem.

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

Enqueue: add a new element to the end of the queue.

Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process q queries, where each query is one of the following 3 types:

1 x: Enqueue element x into the end of the queue.

2: Dequeue the element at the front of the queue.

3: Print the element at the front of the queue.

For example, a series of queries might be as follows:

Function Description

Complete the put, pop, and peek methods in the editor below. They must perform the actions as described above.

Input Format

The first line contains a single integer, q, the number of queries.

Each of the next q lines contains a single query in the form described in the problem statement above. All queries start with an integer denoting the query type, but only query 1 is followed by an additional space-separated value, x, denoting the value to be enqueued.

Constraints:

1 ≤ q ≤ 10⁵

1≤ type ≤ 3

1≤ |x| ≤ 10⁹

It is guaranteed that a valid answer always exists for each query of types 2 and 3.

Output Format

For each query of type 3, return the value of the element at the front of the fifo queue on a new line.

So what is this saying? Let’s take it step by step.

What kind of input are we working with? Let’s take a look. We need to make sure the input is usable for us.

Not super helpful, an array would be a lot more useful to work with. So let’s do some work.

If we split the input into an array where each index is one line of the input, that changes what were working with to this:

Much better.

So conceptually, we need to make a queue using two stacks before we can process any queries. The stacks need to exist and then relate to each other in such a way that we can turn two LIFO data structures into a FIFO data structure. Here is what I came up with:

So we create two stacks to account for a queue’s behavior of enqueue and dequeue. The important part here is that as we keep track of items added to the queue (with the inQueue stack), and the last item that is popped off, is then added to the end of the outQueue stack. In this way, we can manipulate the behavior of two stacks to emulate a queue. We can use this function as we loop through the input array, to perform the action associated with the query.

So what now? Now we need to look at each query and decide what to do based on the case. The problem gives us three cases to handle. Sounds like a good use case for a switch case statement. We also need to remember we are working with strings at each index, and in case 1, there are two inputs, the command of “1”, and the number to be added to the end of the queue. Here is where I went with it:

When we run line 18, and console.log(swCase), the data we are working with now looks like this:

So what do we need to do in each case? If the case (i.e. swCase[0]) is “1” we add a number to the end of the queue. If it is “2” we remove the element from the front of the queue, and if it is “3”, console.log the first element in the queue.

If we find the command of “1” we look to the next index of 1 for the number, or swCase[1] and then we can push it into the stack that is keeping track of the elements going in.

If the command is “2”, we need to run the function we created before to push anything that have added to the inQueue to stage it for the order it will be removed. We then pop the last value on the outQueue stack (the first value on the “queue”).

If the command is “3”, we again run the function we created before for the same reason as the previous command, and then console.log the last item in the outQueue stack, because the stacks are LIFO, which is the first item in our FIFO “queue”.

So altogether, our algorithm looks like this:

And if we run our code…

We did it! Who woulda thought to use stacks to make a queue?! 🤔 Thanks, HackerRank, for making me think outside the box!