Implement Stack using One Queue

Implement Stack using Single 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 Single Queue.
Lets understand the problem statement graphically and it will be more clear, 

Algorithm


We already saw how to Implement Stack using Two Queue: Implement Stack using Two Queue

In this approach we will see how to Implement Stack using Single Queue,

It is very simple, In case of pushing the element in Queue, make sure element is stored in reversed fashion in Queue, that is the last inserted data should always be first element in Queue. 
If last inserted data is stored as first element in Queue then pop() operation simply requires removing data from top of Queue.

Push Operation:
  1. Push the element to the Queue.
  2. Check the size of Queue and store it in variable "sizeOfQueue".
  3. Iterate from 0 to "sizeOfQueue" and Pop the element from queue and push the same element to Queue. By doing this, last inserted data will come at first position in Queue.
If you observe, elements in Queue are stored in reversed order, So pop() operation simply needs to remove date from head of Queue.

Pop Operation:
  1. Pop the elements from Queue.  

Java Program to Implement Stack using One Queue.


package stack;

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

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

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

  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();

  stackUsingOneQueue.push(50);
  stackUsingOneQueue.push(60);

  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
  stackUsingOneQueue.pop();
 }
}
class StackUsingQueueWithOnlyOneQueue{
 Queue<Integer> queue = new LinkedList<Integer>();

 public void push(int data) {
  queue.add(data);
  int size = queue.size();
  while (size > 1) {
   queue.add(queue.remove());
   size--;
  }
 }
 
 public void pop() {
  if(queue.isEmpty()){
   System.out.println("No element present");
  }else{
   System.out.println(queue.poll());
  }
 }
}



You may also like to see


Implement Stack using Two Queue

Implement Queue using Stack


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