Implement Queue using One Stack in Java (Recursive Implementation)

Implement Queue using One 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 one Stack instances.

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

Algorithm

---

We already saw how to Implement Queue using Two Stack: Implement Queue using Two Stack
 
There are many approach to Implement Queue using Stack, here we will implement Queue using Single Stack. (We will use Recursion, which internally uses Stack, so ultimately it is 2 Stack approach using Recursion.)

We only have explicit one 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 only 1 Stack instances("mainStack") to behave it like Queue. 

enQueue() Operation:

1. Push the element to the Stack.
   

deQueue() Operation:

1. Pop all the elements from Main Stack recursively until Stack item count is equal to 1.


2. If Stack item count = 1, Pop item from Stack, Print it & Return.


3. Push all popped element back to Stack as shown below.

Java Program to Implement Queue using Single Stack - Recursion.

---

package javabypatel;

import java.util.Stack;

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

  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 QueueUsingSingleStack{
 Stack<Integer> stack = new Stack<Integer>();

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

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

  if(stack.size()==1){
   System.out.println(stack.pop());
   return;
  }

  int data = stack.pop();
  deQueue();
  stack.push(data);
 }
}

You may also like to see

---

Implement Queue using Two Stack

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

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.