How to construct queue using Stacks in Java

Hello Coding Enthusiasts, today we will see how to implement a queue using Stacks in Java.

A queue is a First-In-First-Out (FIFO) data structure and a stack is a Last-In-First-Out (LIFO) data structure.

Before doing so, let’s see what all basic functions a queue has:

• Enqueue()  – adding an element at the back of the Queue.
• Dequeue()  – removing an element from the front of the Queue.
• Front()         – Retrieve the front element from the queue.
• Rear()           – Retrieve the last element from the queue.

Refer,  implementing Queue in Java for better understanding.

Also, let’s see what all basic functions a stack has:

• push()   –  inserts an element on top of the Stack.
• pop()     –  removes an element from  top of the Stack.
• peek()   –  returns the value of the element at the top.

Refer,  implementing Stack in Java for better understanding.

Implementing Queue using Stacks

Here, our main idea is to implement the functionalities of a queue without implementing a queue. To do so, we will be using stacks.
We need two stacks for this implementation. One is for pushing the elements into the stack(for enqueue operation) and the second stack is always in the inverted form of the first stack(just like queue). To, get better clarity look into the code below:

class Solution {
  public static ArrayList<Integer> implementQueue(ArrayList<ArrayList<Integer>> Query) {

      ArrayList<Integer> result= new ArrayList<Integer>();
      if(Query==null || Query.size()==0) 
          return result;

      Stack<Integer> stack1=new Stack<Integer>();
      Stack<Integer> stack2=new Stack<Integer>(); //holds the queue form
      
      int q=Query.size();
      
      for(int i=0;i<q;i++){
          ArrayList<Integer> list=new ArrayList<Integer>();
          list=Query.get(i);
          if(list.get(0)==1){
              while(!stack2.isEmpty()){
                  stack1.push(stack2.pop());//before enqueuing, all the elements in stack 2 are pushed onto stack 1 
              }
              
              stack1.push(list.get(1));//element is enqueued,i.e., pushed onto stack1
              
              while(!stack1.isEmpty()){
                  stack2.push(stack1.pop());// all the stack1 elements are pushed onto stack2(now, stack2 is in Queue form)
              }
              continue;
          }
          else if(list.get(0)==2){
              stack2.pop();//Since, stack2 is in Queue form when dequeue function is implemented then element is popped out of stack2
          }
          else if(list.get(0)==3){
              result.add(stack2.peek());
          }
      }
      return result;
  }
}

Let the input be as shown below, where the first column contains 1,2 and 3 (1-enqueue, 2-dequeue, 3-print front element of queue) and the second column ant number x with 1 in its first column means that number x should be enqueued and for the rest(2 and 3 in first column) any number (here we used zero) can be used as it’s work is just to dequeue and print.

1 42 
2 0 
1 14 
3 0 
1 28 
3 0 
1 60 
1 78 
2 0 
2 0 

Output:

14 14

The explanation for the output:

At first, 42 is enqueued and then dequeued, then 14 is enqueued and as it is the front it’s printed. Now 28 is enqueued and print is called, as 14 is still at the front 14 is printed. Later, 60 and 78 are enqueued and 14 and 28 are dequeued.