Implement Stack using Queue

Implement Stack using Queue in Java

You are given a Queue data structure that supports standard enQueue and deQueue operations.  You need to implement Stack data structure using Queue instances.
Lets understand the problem statement graphically and it will be more clear, 

Algorithm


There are many approach to Implement Stack using Queue,

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

Idea is to push elements into the Queue "mainQueue" and while poping element, pop all elements except the last element one by one from "mainQueue" to temporary Queue "tempQueue", return the last element and initialise "mainQueue" with "tempQueue".

Push Operation:
  1. Push the element to the Queue.

Pop Operation:
  1. Pop all the elements from Main Queue to Temporary Queue except the last element as that is the element we need to return.
  2. Return the last element.
  3. All elements are now present in Temporary Queue and Main queue is empty, So instead of pushing all elements again from Temporary Queue to Main queue, lets initialise Main Queue to Temporary Queue and make Temporary Queue blank.

Optimized way to Implement Stack using One Queue : Implement Stack using One Queue.

Java Program to Implement Stack using Queue.


package stack;

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueueApp { 
 public static void main(String[] args) {
  StackUsingQueue stackUsingQueue = new StackUsingQueue();

  stackUsingQueue.push(10);
  stackUsingQueue.push(20);
  stackUsingQueue.push(30);
  stackUsingQueue.push(40);

  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();

  stackUsingQueue.push(50);
  stackUsingQueue.push(60);

  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();
  stackUsingQueue.pop();
 }
}

class StackUsingQueue{
 Queue<Integer> queue = new LinkedList<Integer>();
 Queue<Integer> tempQueue = new LinkedList<Integer>();

 public void push(int data){
  queue.add(data);
 }

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

  while (queue.size()>1) {
   tempQueue.add(queue.poll());
  }
  System.out.println(queue.poll());
  queue = tempQueue;
  tempQueue = new LinkedList<Integer>();
 }
}



You may also like to see


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

Post a Comment