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[0]);
  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[0]) {
      case '1':
        //enqueue
        inputStack.push(entry[1]);
        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.