Implementing Queue using Stack

This is one of the common question asked in interview. How do you implement a queue using stack.

Queue has operations enqueue and dequeue. While stack has operations like push and pop.

Solution1: 

We need 2 stack for this solution.

Enqueue operation in queue

if (stack1 is empty)

True:

push the element into the stack1

False:

pop the elements from stack1 and push them to stack2

push the incoming element to stack1

pop the elements from stack2 and push them again to stack1

For dequeue operation

Pop the element from the stack1

But this solution is not efficient. This can be altered to make it more efficient.

Solution 2:

The two stack now named as inbox and outbox.

Enqueue operation in queue

Push the incoming item to the inbox.

For dequeue operation

if(outbox is empty)

pop the elements from inbox and push them to outbox

pop the element from outbox.

By this, each element is popped and pushed only twice.

Here is the implementation of the same in java for reference.

package blog.java;

import java.util.Stack;

class Queue {

private Stack inbox = new Stack();

private Stack outbox = new Stack();

public void queue(Integer integer) {

inbox.push(integer);

}

public void dequeue() {

if (outbox.isEmpty()) {

while (!inbox.isEmpty())

outbox.push(inbox.pop());

}

System.out.println(outbox.pop());

}

}

public class QueueWithTwoStack {

/**

* @param args

*/

public static void main(String[] args) {

Queue queueTest = new Queue();

queueTest.queue(1);

queueTest.queue(2);

queueTest.queue(3);

queueTest.queue(4);

queueTest.dequeue();

queueTest.dequeue();

queueTest.queue(5);

queueTest.queue(6);

queueTest.queue(7);

queueTest.queue(8);

queueTest.dequeue();

queueTest.dequeue();

queueTest.dequeue();

queueTest.dequeue();

queueTest.dequeue();

queueTest.dequeue();

}

}