Implement Queue Using Stacks

Objective: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out).

Here our objective is to implement queue using stacks.

Approach:

  • Take 2 Stacks, stack1 and stack2.
  • stack1 will be used a back of the Queue and stack2 will be used as front of the Queue.
  • Push() operation will be done on stack1, and peek() and pop() operations will be done on stack2.
  • When peek() and pop() are called, check is stack2 is empty, if yes then move all the elements from stack1 and push them into stack2.

Example:

Implement Queue Using Stacks

Complete Code:

import java.util.Stack;
public class QueueUsingStacks {
Stack<Integer> stack1 = new Stack<>(); //act as back of the Queue
Stack<Integer> stack2 = new Stack<>(); // act as the front of the Queue
public void push(int x) { // push into stack 1
stack1.push(x);
}
public int peek() {
if (stack2.isEmpty()) {
moveItems(stack1, stack2);
}
return stack2.peek(); // return the top element in stack2
}
public int pop() {
if (stack2.isEmpty()) {
moveItems(stack1, stack2);
}
return stack2.pop(); // return the top element in stack2
}
public void moveItems(Stack<Integer> s1, Stack<Integer> s2) {
while (!stack1.isEmpty()) {
s2.push(s1.pop()); // move all the elements from stack 1 to stack 2
}
}
public static void main(String[] args) {
QueueUsingStacks q = new QueueUsingStacks();
q.push(10);
q.push(20);
q.push(30);
System.out.println("POP from Queue " + q.pop());
}
}


Output:

POP from Queue 10