# HackerRank Queue using Two Stacks solution with JavaScript

Learn how to solve the Queue using Two Stacks problem from the HackerRank challenges with JavaScript.
May 07, 2023JavaScript

This HackerRank problem introduces us to queues. A queue is a data structure that maintains the order in which elements were added to it. Oldest elements are removed from the front and new elements are added to the back.

Think of a queue as a waiting line of customers at a store. A queue is a First-In-First-Out (FIFO) data structure because the first element added to the queue is always the first one to be removed. Waiting lines are always first come, first served.

Queues have two main operations, enqueue and dequeue. The enqueue operation adds a new element to the end of the queue. The dequeue operation removes an element from the front of the queue and returns it.

## The problem

For this HackerRank challenge, we are asked to implement a queue using two stacks. This is where the challenge is. A stack is a Last-In-First-Out (LIFO) data structure, while a queue is a First-In-First-Out (FIFO) data structure. Using two stacks, we can mimic the behavior of a queue.

We are asked to define a `processData` function that receives a string. The first line of the input string contains a single integer, denoting the number of queries. Each of the subsequent lines of the input string contains a query.

Each query can be one of the following 3 types:

1. `x`: Enqueue element `x` to the end of the queue.
2. Dequeue the element from the front of the queue.
3. Print the element at the front of the queue.

All three queries start with an integer identifying the query type. Only the first query is followed by an additional space-separated value, `x`, specifying the value to be enqueued.

## Working out the solution

For the enqueue operation, we will push an element onto the input stack.

For the dequeue operation:

• If the output stack is empty, pop every element from the input stack and push them onto the output stack.
• If the output stack is not empty, pop an element from the output stack.

If we have a queue of `1, 2, 3, 4, 5` and we must perform a dequeue operation (remove from the front of the queue), we must remove and return `1`.

To do this with two stacks, we must:

1. Push all elements into an input stack.
2. Pop all elements in the input stack and insert them into the output stack, so that the first element is last.
3. Pop the last element in the output stack.
``````// push all elements into an input stack.
inputStack = [1, 2, 3, 4, 5];
outputStack = [];

// pop from the input stack and insert into the output stack
inputStack = [];
outputStack = [5, 4, 3, 2, 1];

// pop from the output stack
outputStack.pop(); // 1
``````

## Pseudo code solution

Now, let's define the full pseudo code for this challenge.

1. Define two stacks, an input stack and an output stack.
2. Define a `stackToQueue` function that converts a LIFO-ordered stack into a stack that resembles a FIFO-like queue. It will check if the output stack is empty. If so, it will pop every element from the input stack and push them onto the output stack.
3. Convert multi-line input string to an array.
4. Loop over the array line-by-line.
• Read the first character to identify the query to perform.
• If it's query type `1`, perform an enqueue operation by pushing the second character onto the stack.
• If it's query type `2`, perform a dequeue operation.
• Call the `stackToQueue` function.
• Pop from the output stack.
• If it's query type `3`, print the element at the front of the queue.
• Call the `stackToQueue` function.
• Log the last element from the output stack to the console.

## Code solution

``````function processData(input) {
const inputArray = input.split('\n');
const numberOfQueries = parseInt(inputArray);
const inputStack = [];
const outputStack = [];

function stackToQueue() {
if (!outputStack.length) {
while (inputStack.length) {
outputStack.push(inputStack.pop());
}
}
}

for (let i = 1; i <= numberOfQueries; i++) {
let entry = inputArray[i].trim().split(' ');

switch (entry) {
case '1':
//enqueue
inputStack.push(entry);
break;
case '2':
//dequeue
stackToQueue();
outputStack.pop();
break;
case '3':
//print from front of queue
stackToQueue();
console.log(outputStack[outputStack.length - 1]);
break;
default:
break;
}
}
}
``````

## Test cases

Let's test the `processData` function above with the following test case.

``````console.log(
processData(
`10
1 42
2
1 14
3
1 28
3
1 60
1 78
2
2`
)
); // 14, 14
``````

The `10` specifies that there will be 10 queries. The loop that iterates over the queries starts after this initial value. The input string has the query of type `3` twice, which means we will get two values printed to the console. Both times, the result is the value `14`.

Here is the execution flow:

• `1 42`: enqueue `42`.
• `2`: dequeue.
• `1 14`: enqueue `14`.
• `3`: print from the front of the queue (`14`).
• `1 28`: enqueue `28`.
• `3`: print from the front of the queue (`14`).
• `1 60`: enqueue `60`.
• `1 78`: enqueue `78`.
• `2`: dequeue.
• `2`: dequeue.

The result is:

``````14;
14;
``````

At the end of the execution, the queue will contain `[14, 28]`.

## Time and space complexity

The Big O time complexity of the solution is linear, or `O(n)`, where `n` is the number of queries defined in the input string. The solution used one loop that iterated over all the lines with queries in the input string.

The Big O space complexity of the solution is linear, or `O(2n)`, where `n` is the number of characters that will be added to the queue. Since we are using two stacks to mimic a queue, the space complexity is multiplied by 2 times the number of characters.