Queue – A Tale of Two Stacks

I looked at the HackerRank challenge Queues: A Tale of Two Stacks. If interested take a look at the requirements at the following URL:  https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks

Initially I followed the recommendation of using two stacks. The brute force approach worked for the test case but it was too slow in 3 or 4 test cases.

This morning I was implementing a doubly linked list class from scratch. I included methods to enqueue and dequeue from the tail or the head. That allows for a simple implementation of stacks. I decided to go through the process of moving data from one stack to the other, pop the element being dequeued, and then moving the data back to get the initial stack ready for the next enqueue operation.  Of course a flag could have eliminated moving the data back because the next operation could have been the same dequeue. Just keep on looking at what is happening with the values as they are being inserted and removed from the “queue”.

Decided to skip such approach and use the standard method to delete an element at a specified index. That approach passed all 16 test cases.

After doodling on my tablet it became clear that a flag or just a test would work. The following figure illustrates the observation:

 

Following is a screen capture from the console of the Eclipse IDE using the sample data:

10

1 42

2

1 14

3

1 28

3

1 60

1 78

2

2

14

14

Following is the Java code for my solution including the test code provided by the challenge:

import java.util.Scanner;

import java.util.Stack;

/*

* Implements a queue with 2 stacks.

*/

class MyQueue <T> {

// **** use 2 stacks ****

Stack<T> firstStack;

Stack<T> secondStack;

/**

* Constructor

*/

public MyQueue() {

firstStack    = new Stack<T>();

secondStack   = new Stack<T>();

}

/**

* Enqueue.

*/

public void enqueue(T x) {

firstStack.push(x);

}

/**

* Dequeue.

*/

public void dequeue() {

// **** populate second stack (if needed) ****

if (secondStack.isEmpty()) {

while (!firstStack.isEmpty()) {

secondStack.push(firstStack.pop());

}

}

// **** dequeue top value ****

secondStack.pop();

}

/**

* Peek.

*/

public T peek() {

// **** build second stack (if needed) ****

if (secondStack.isEmpty()) {

while (!firstStack.isEmpty()) {

secondStack.push(firstStack.pop());

}

}

// **** return value ****

return secondStack.peek();

}

}

public class Solution {

/*

* Test code.

*/

public static void main(String[] args) {

MyQueue<Integer> queue = new MyQueue<Integer>();

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

for (int i = 0; i < n; i++) {

int operation = scan.nextInt();

if (operation == 1) {        // enqueue

queue.enqueue(scan.nextInt());

} else if (operation == 2) {        // dequeue

queue.dequeue();

} else if (operation == 3) {        // print/peek

System.out.println(queue.peek());

}

}

scan.close();

}

}

My suggestion is to always take time understanding what is going on. A couple of cases should suffice. Make sure you test the end conditions. In this case at which time one needs to refresh the second stack. There is no need to clear the first stack after moving data to the second stack.

This challenge was simple but had fun working on it. Of course a second stack is not needed to implement a queue. I did submit a solution using a single stack and it was accepted.

If you have comments or questions regarding this or any other post in this blob please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *