Implement Queue using Stack

Implement Queue using Stack in Java

---

You are given a Stack data structure that supports standard push and pop operations. You need to implement Queue data structure using Stack instances.

Lets understand the problem statement graphically and it will be more clear,  

Algorithm

---

There are many approach to Implement Queue using Stack,

We only have Stack with us which works in LIFO that is Last In First Out order and need to behave it as way Queue works that is in FIFO (First In First Out) fashion.

In this approach, We will take help of 2 Stack instances("mainStack" and "tempStack") to behave it like Queue. 

While enQueue() operation, we simply push elements into the Stack "mainStack".

While deQueue() operation, we can't simply pop element from mainStack because it needs to behave like a Queue, and the element to be poped is present at bottom of the Stack, we need to use temporary Stack "tempStack", and pop all elements from "mainStack" to temporary Stack "tempStack", 
At last, Pop element form "tempStack".

enQueue() Operation:

1. Push the element to the Stack "mainStack".
   

deQueue() Operation:

1. Pop all the elements from Main Stack to Temporary Stack "tempStack".


2. Now all data is present in Temporary Stack in reverse order that is data which is inserted first is present at top of "tempStack", So simply pop element from Temporary Stack.


3. All elements are now present in Temporary Stack and Main Stack is empty, we will keep those 2 stack as it is and if the immediate next request continued to be of deQueue() operation, then we will pop data from Temporary Stack.


4. Now, if next request is of enQueue() operation, then what to do?
   Simple, we will push data in "mainStack" and let "tempStack" be as it is.
   Now tempStack and mainStack both contain few elements.


5. Say next request if deQueue() operation, now from which Queue we will pop data.
   Obviously "tempStack" as it contains oldest element.
   If "tempStack" is empty then again situtaion is same from where we started. Repeat from Step1.

Java Program to Implement Queue using Stack.

package javabypatel;

import java.util.Stack;

public class QueueUsingStackApp { 
 public static void main(String[] args) {
  QueueUsingStack queueUsingStack = new QueueUsingStack();

  queueUsingStack.enQueue(10);
  queueUsingStack.enQueue(20);
  queueUsingStack.enQueue(30);
  queueUsingStack.enQueue(40);

  queueUsingStack.deQueue();
  queueUsingStack.deQueue();

  queueUsingStack.enQueue(50);
  queueUsingStack.enQueue(60);

  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
  queueUsingStack.deQueue();
 }
}

class QueueUsingStack{
 Stack<Integer> stack = new Stack<Integer>();
 Stack<Integer> tempStack = new Stack<Integer>();

 public void enQueue(int data){
   stack.add(data);
 }

 public void deQueue(){
  if(!tempStack.isEmpty()){
   System.out.println(tempStack.pop());
   return;
  }

  if(stack.size() < 1){
   System.out.println("Nothing to DeQueue");
   return;
  }

  while (stack.size()>0) {
   tempStack.add(stack.pop());
  }
  System.out.println(tempStack.pop());
 }
}

You may also like to see

Implement Stack using One Queue

Implement Stack using Queue

Find Largest and Smallest number in Array

Count zeros in a row wise and column wise sorted matrix

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java