Implement Queue using Stack

How to implement queue functionality into stack?

As Queue has nature First In First Out (FIFO) i.e. any item insert into Queue arrange such way whenever we will fetch the item from queue we will get oldest inserted element fist.

Implement Queue using Stack

The Stack class represents a Last-In-First-Out (LIFO) stack of objects. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

Solution 1: Using a Temporary Stack

import java.util.Stack;

/**
 * 
 */

/**
 * @author Dinesh.Rajput
 *
 */
public class StackAsQueue {

 /**
  * @param args
  */
 public static void main(String[] args) {
  Stack<Integer> stack = new Stack<Integer>();
  for(int i = 1;i<=10;i++ ){
   //stack.push(i);
   push(i, stack);
  }
  while(!stack.isEmpty()){
   System.out.println(stack.pop());
  }
 }

 private static void push(int i, Stack<Integer> stack) {
  Stack<Integer> temp = new Stack<Integer>();
  if(stack.isEmpty()){
   stack.push(i);
  }else{
   while(!stack.isEmpty()){
    int iii=stack.pop();
    temp.push(iii);
   }
   stack.push(i);
   while(!temp.isEmpty()){
    int iii=temp.pop();
    stack.push(iii);
   }
  }
 }

}


Solution 2: Without Using a Temporary Stack

For performing enqueue we require only one stack as we can directly push data into stack, but to perform dequeue we will require two Stacks, because we need to follow queue’s FIFO property

Using recursive approach, the queue can be implemented with single Stack instance.

import java.util.Stack;


public class MyQueue<Integer> {

 Stack<Integer> stack = new Stack<Integer>();
 
 public boolean isEmpty(){
  return stack.isEmpty();
 }
 
 public void enqueue(Integer item){
  stack.push(item);
 }
 
 public Integer dequeue(){
  return pop(stack);
 }
 
 private Integer pop(Stack<Integer> stack){
  Integer top = stack.pop();
  Integer last;
  if(stack.isEmpty()){
   return top;
  }else{
   last = pop(stack);
  }
  stack.push(top);
  return last;
 }
}

 

Previous
Next