Implementation of Queues using two Stack in Java

Implementation of Queues using Two Stack

Implementation of Queues using Two Stacks in Java is a popular Data Structures problem that tests your understanding of how different data structures can be combined to simulate each other.

A queue follows FIFO (First In, First Out), while a stack follows LIFO (Last In, First Out). Since their behaviors are opposite, implementing a queue using stacks requires a smart rearrangement of elements.

implementing queue using two stack

What is a Queue Using Two Stacks?

Queue using Two Stacks means implementing queue operations (enqueue, dequeue) with the help of two stack data structures.

We use two stacks to reverse element order so that FIFO behavior is maintained.

  • Queue → FIFO
  • Stack → LIFO

By transferring elements between two stacks, we simulate queue behavior.

implementing queue using two stack

Approach to Implement Queue Using Two Stacks in Java

We use two stacks:

  • stack1 → For insertion (enqueue)
  • stack2 → For deletion (dequeue)

Working Principle:

  1. Enqueue always happens in stack1
  2. Dequeue happens from stack2
  3. If stack2 is empty, elements are moved from stack1 to stack2

This reversal maintains FIFO order.

Algorithm to Implement Queue Using Stack in Java

Algorithm:

1. Enqueue Operation

  • Push element into stack1

2. Dequeue Operation

  1. If stack1 is empty AND stack2 is empty
    • If stack1 is empty AND stack2 is empty
  2. Underflow (Queue is empty)
    • If stack2 is empty
      • Pop from stack1
      • Push into stack2
  3. Pop and return top of stack2

Learn DSA

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Java Code to Implement Queues Using Two Stacks

Run
import java.util.Stack;

class QueueUsingTwoStacks {

    private Stack stack1;
    private Stack stack2;

    // Constructor
    public QueueUsingTwoStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // Enqueue operation
    public void enqueue(int value) {
        stack1.push(value);
        System.out.println(value + " inserted");
    }

    // Dequeue operation
    public int dequeue() {

        // Underflow check
        if (stack1.isEmpty() && stack2.isEmpty()) {
            System.out.println("Queue is empty (Underflow)");
            return -1;
        }

        // Transfer elements if needed
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        return stack2.pop();
    }

    // Peek operation
    public int peek() {

        if (stack1.isEmpty() && stack2.isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }

        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        return stack2.peek();
    }

    // Check if queue is empty
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    // Display queue elements
    public void display() {

        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }

        System.out.print("Queue: ");

        // Print stack2 (top to bottom)
        for (int i = stack2.size() - 1; i >= 0; i--) {
            System.out.print(stack2.get(i) + " ");
        }

        // Print stack1 (bottom to top)
        for (int i = 0; i < stack1.size(); i++) {
            System.out.print(stack1.get(i) + " ");
        }

        System.out.println();
    }

    // Main method
    public static void main(String[] args) {

        QueueUsingTwoStacks queue = new QueueUsingTwoStacks();

        // Enqueue
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        // Display
        queue.display();

        // Peek
        System.out.println("Front element: " + queue.peek());

        // Dequeue
        System.out.println("Removed: " + queue.dequeue());
        System.out.println("Removed: " + queue.dequeue());

        // Display
        queue.display();

        // Enqueue again
        queue.enqueue(40);
        queue.enqueue(50);

        queue.display();

        // Dequeue remaining
        System.out.println("Removed: " + queue.dequeue());
        System.out.println("Removed: " + queue.dequeue());
        System.out.println("Removed: " + queue.dequeue());

        // Underflow test
        System.out.println("Removed: " + queue.dequeue());
    }
}

Input:

enqueue(10)
enqueue(20)
enqueue(30)
dequeue()
dequeue()
enqueue(40)
enqueue(50)
dequeue()
dequeue()
dequeue()

Output:

10 inserted
20 inserted
30 inserted
Queue: 10 20 30
Front element: 10
Removed: 10
Removed: 20
Queue: 30
40 inserted
50 inserted
Queue: 30 40 50
Removed: 30
Removed: 40
Removed: 50
Queue is empty (Underflow)
Removed: -1

Comparison with Other Queue Implementations

Method using queueTime ComplexitySpace Complexity
Array QueueO(1)O(n)
Circular QueueO(1)O(n)
Linked List QueueO(1)O(n)
Two Stacks QueueO(1)*O(n)

Frequently Asked Questions

Answer:

It is a method of building a queue using two stacks to maintain FIFO order.

Answer:

Two stacks help reverse element order, converting LIFO behavior into FIFO.

Answer:

Enqueue is O(1), and dequeue is O(1) amortized.

Answer:

Yes, using recursion, but it is less efficient.

Answer:

Mostly for interviews and learning. Real systems use built in queue structures.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java