[Hackerrank] – Queue using two stacks

A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way.

If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem.

Problem Statement:

The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a data structure for queue already exists. Sometimes you have a limited architecture and still need a solution that supports your use case.

If you look at the operations will still behave like a queue:

enqueue ( 4 )
enqueue ( 8 )
enqueue ( 15 )
enqueue ( 16 )

dequeue ( ) => 4
dequeue ( ) => 8
peek ( ) => 15
dequeue ( ) => 15Code language: PHP (php)

For all the operations the desired output is same as if you are operating on a queue.

Solution:

This problem does not have a brute force method. Just a common understanding of how both the data structures work should be helpful in approaching this. Just need to make sure that you are following the FIFO (First in First out). Let us see how that would look.

Let us start by creating 2 stacks as desired. One stack is In and the other is named as Out. Apart from those, also create a queue that is mimicking the actual operations.

Queue:
--------------------------------------------------------------------------
      |              |              |              |            |
--------------------------------------------------------------------------

Stacks:

|           |                       |           |
-------------                       -------------
|           |                       |           |
-------------                       -------------
|           |                       |           |
-------------                       -------------
|           |                       |           |
-------------                       -------------
     In                                 OutCode language: plaintext (plaintext)

Enqueue:

Now, let us try to perform 3 operations on the queue:

- enqueue ( 4 )
- enqueue ( 8 )
- enqueue ( 15 )Code language: Java (java)

For every enqueue( ) operation, you push( ) the element in the In stack. As per this our data structures would look like:

Queue:
--------------------------------------------------------------------------
      |              |              |       15      |      8     |   4
--------------------------------------------------------------------------

Stacks:

|           |                       |           |
-------------                       -------------
|    15     |                       |           |
-------------                       -------------
|    8      |                       |           |
-------------                       -------------
|    4      |                       |           |
-------------                       -------------
     In                                 OutCode language: plaintext (plaintext)

This takes care of one part of the problem. How do you remove elements now? If you perform a dequeue () operation on the queue, you would get the value 4. However, if you observe carefully you cannot extract the value 4 from the In stack. As soon as you do a pop(), you would get the element 15. This is not what we desired, it breaks the rules of a queue.

That is where the Out stack comes in handy. As soon as you receive a dequeue () request, check the Out stack. If it is not empty, do a pop() operation and return the element. If it is empty. Transfer all the elements from In stack to the Out stack. Let us see how that works.

Dequeue:

It is a 2-step process. First we pop() all the elements from In stack and push() it in the Out stack.

Queue:
--------------------------------------------------------------------------
      |              |              |       15      |      8     |   4
--------------------------------------------------------------------------

Stacks:

|           |                       |           |
-------------                       -------------
|           |                       |    4      |
-------------                       -------------
|           |                       |    8      |
-------------                       -------------
|           |                       |    15     |
-------------                       -------------
     In                                 Out

Now, if you look closely stack Out looks very similar to the queue. If you pop an element from it, you will get the same element that you will get from the queue.

If we now perform a dequeue operation, we just need to pop an element from the other stack. The data structures now look like:

Queue:
--------------------------------------------------------------------------
      |              |              |       15      |      8     |   
--------------------------------------------------------------------------

Stacks:

|           |                       |           |
-------------                       -------------
|           |                       |           |
-------------                       -------------
|           |                       |    8      |
-------------                       -------------
|           |                       |    15     |
-------------                       -------------
     In                                 Out

Algorithm:

We can now write the algorithm for all the 3 operations:

• Create two stacks In and Out
• enqueue( ) : Push elements in stack In
• dequeue( ) : If stack Out is not empty, pop an element from the stack. If the stack is empty, pop all elements of stack In in the Out stack and then again pop from Out.
• peek ( ) : Same as dequeue, but instead of pop just perform the peek operation.

Code:

private Stack input = new Stack();
private Stack output = new Stack();

public void enqueue(int x) {
  input.push(x);
}

public int dequeue() {
  peek();
  return output.pop();
}

public int peek() {
  if (output.empty())
    while (!input.empty())
      output.push(input.pop());
  return output.peek();
}

public boolean isEmpty() {
  return input.empty() && output.empty();
}
Code language: Java (java)

The problem statement can be found at HackerRank : Queue using two Stacks.
You can also find the complete solution and the test cases on GitHub as well.

Video Explanation: