Java Coding Challenge - Implement Queue Using Stack

Introduction

In this coding challenge, the goal is to implement a queue using two stacks. A queue follows the First In, First Out (FIFO) principle, whereas a stack follows the Last In, First Out (LIFO) principle. By using two stacks, we can simulate the behavior of a queue.

This is a common interview problem that tests your understanding of both stacks and queues, and your ability to manipulate data structures to achieve the desired behavior.

Problem Statement

Implement the following operations of a queue using two stacks:

1. enqueue(x): Add an element to the back of the queue.
2. dequeue(): Remove and return the element from the front of the queue.
3. peek(): Get the front element of the queue.
4. isEmpty(): Check whether the queue is empty.

Example:

• Input:

  • enqueue(1)
  • enqueue(2)
  • dequeue() → returns 1
  • peek() → returns 2
  • isEmpty() → returns false

• Output:

  • The first element enqueued is removed first (1), so the queue behaves correctly using two stacks.

Approach

Using Two Stacks

To implement a queue using stacks, we will maintain two stacks:

1. Stack 1 (stack1): This is used to store elements in the order they are enqueued.
2. Stack 2 (stack2): This is used to reverse the order of elements to simulate dequeuing.

How It Works:

• Enqueue Operation: Simply push the element onto stack1.
• Dequeue Operation: If stack2 is empty, pop all elements from stack1 and push them onto stack2 (this reverses the order). Then, pop from stack2 to dequeue the front element.
• Peek Operation: Similar to dequeue, but return the top of stack2 instead of popping it.
• isEmpty: Check if both stacks are empty.

Why Two Stacks?

• Stack 1 holds the elements in the order they were added (like a queue).
• When you need to dequeue, you reverse the elements into Stack 2, so the oldest element (front of the queue) comes to the top of Stack 2.

This approach ensures that we can implement a queue using only two stacks while maintaining the correct FIFO order.

Java Code Implementation

QueueUsingStacks Class

import java.util.Stack;

public class QueueUsingStacks {
    private Stack<Integer> stack1; // Stack 1 for enqueue operation
    private Stack<Integer> stack2; // Stack 2 for dequeue and peek operations

    // Constructor to initialize the stacks
    public QueueUsingStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // Enqueue operation: Push element to stack1
    public void enqueue(int value) {
        stack1.push(value);
    }

    // Dequeue operation: Pop element from stack2 if not empty, otherwise transfer elements from stack1 to stack2
    public int dequeue() {
        if (stack2.isEmpty()) {
            // Transfer all elements from stack1 to stack2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        // If stack2 is still empty, the queue is empty
        if (stack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }

        return stack2.pop(); // Pop the element from stack2 (which is the front of the queue)
    }

    // Peek operation: Return the front element of the queue without removing it
    public int peek() {
        if (stack2.isEmpty()) {
            // Transfer all elements from stack1 to stack2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        // If stack2 is still empty, the queue is empty
        if (stack2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }

        return stack2.peek(); // Peek the element from stack2 (front of the queue)
    }

    // isEmpty operation: Check if both stacks are empty
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Explanation

1. enqueue(x):
   • Push the new element onto stack1 which simulates adding elements to the back of the queue.

public void enqueue(int value) {
    stack1.push(value);
}

2. dequeue():
   • If stack2 is empty, transfer all elements from stack1 to stack2 to reverse the order.
   • Then, pop from stack2, which simulates removing the element from the front of the queue.

public int dequeue() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    
    if (stack2.isEmpty()) {
        throw new IllegalStateException("Queue is empty");
    }

    return stack2.pop();
}

3. peek():
   • Similar to dequeue(), but instead of popping the element, we return the top of stack2 to check the front of the queue without removing it.

public int peek() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    
    if (stack2.isEmpty()) {
        throw new IllegalStateException("Queue is empty");
    }

    return stack2.peek();
}

4. isEmpty():
   • Simply check if both stack1 and stack2 are empty.

public boolean isEmpty() {
    return stack1.isEmpty() && stack2.isEmpty();
}

Main Class to Test the Queue Implementation

public class Main {
    public static void main(String[] args) {
        QueueUsingStacks queue = new QueueUsingStacks();

        // Enqueue some elements
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        // Dequeue and peek
        System.out.println("Dequeued: " + queue.dequeue());  // Output: 1
        System.out.println("Front element: " + queue.peek()); // Output: 2

        // Enqueue more elements
        queue.enqueue(4);
        System.out.println("Dequeued: " + queue.dequeue());  // Output: 2

        // Check if the queue is empty
        System.out.println("Is queue empty? " + queue.isEmpty());  // Output: false
    }
}

Example Output:

Dequeued: 1
Front element: 2
Dequeued: 2
Is queue empty? false

Time Complexity

• Enqueue Operation: O(1), as we simply push elements onto stack1.
• Dequeue Operation: Amortized O(1). In the worst case, all elements from stack1 are moved to stack2, but this happens only once for each element.
• Peek Operation: O(1), as elements are only moved when stack2 is empty.
• isEmpty Operation: O(1), as it just checks if both stacks are empty.

Space Complexity

• Space Complexity: O(n), where n is the number of elements in the queue. Both stack1 and stack2 together store all the elements.

Conclusion

In this challenge, we implemented a queue using two stacks in Java. The approach ensures that all queue operations, including enqueue, dequeue, peek, and isEmpty, work efficiently. By using two stacks, we can simulate the FIFO behavior of a queue while maintaining the LIFO nature of stacks. This is a common interview question that tests your understanding of data structures and algorithm optimization.