Implement Queue using Stacks - Complete Java Solution

This solution demonstrates how to implement a queue using two stacks to achieve FIFO behavior while maintaining efficient O(1) amortized operations for both enqueue and dequeue.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Should we support all standard queue operations (offer, poll, peek, isEmpty) with their expected time complexities?
2. Can we modify the input stack structure during operations, or must we maintain immutability?
3. What's the expected range of operations? Will we have a large number of enqueue/dequeue operations?
4. Do we need to handle concurrent access in a multi-threaded environment?
5. Should the solution optimize for amortized or worst-case time complexity?

Restatement of the problem: Implement a queue data structure using only two stacks. A queue follows FIFO (First In First Out) principle where elements are added to the rear and removed from the front. The challenge is to simulate this behavior using only LIFO (Last In First Out) stacks.

Input/Output specifications:

• Input: Queue operations (offer, poll, peek, isEmpty)
• Output: Values returned by poll and peek operations, boolean from isEmpty
• Constraints: Each operation should maintain queue semantics

Assumptions made:

1. We can use two stacks to simulate queue behavior
2. The implementation should support standard queue operations with reasonable time complexity
3. Stack operations (push, pop, peek) are O(1) and follow LIFO principle
4. We can modify the stacks during operations but must maintain queue semantics

Data shape and hidden structure: The problem involves simulating a FIFO queue using two LIFO stacks. The key insight is that one stack can be used for enqueuing (push operations) while the other handles dequeuing by transferring elements when needed. The hidden structure is that we're essentially using one stack to reverse the order of elements for proper queue behavior.

The challenge lies in maintaining the correct element ordering when elements are moved between stacks during dequeue operations, ensuring that the oldest element is always accessible at the top of the "output" stack.

2. Pattern Recognition

Identifying the pattern

The most likely pattern here is stack simulation using two stacks or LIFO-to-FIFO conversion.

Wording that signals the pattern

• "Implement Queue using Stacks" - This directly signals we need to simulate queue behavior (FIFO) using stack operations (LIFO)
• The requirement to maintain queue semantics (enqueue/dequeue) while only having stack operations available

Why this fits the pattern

This problem is a classic example of stack simulation or data structure transformation. The core challenge is that we're constrained to use only stack operations (push, pop, peek) but need to implement queue behavior (enqueue at rear, dequeue from front). This requires understanding how to simulate one data structure's semantics using another.

Core insight needed

The key insight is that we can simulate FIFO behavior using two stacks:

• One stack for incoming elements (push operations)
• One stack for outgoing elements (pop operations)
• When the output stack is empty, we transfer all elements from input stack to output stack to maintain order

This approach leverages the fact that reversing a stack twice gives us the original order, effectively creating a queue-like behavior.

The pattern is fundamentally about stack-to-queue simulation and lazy reversal - we only reverse elements when necessary to maintain the correct order for FIFO operations.

3. Approach Evolution

My first instinct is to use two stacks to simulate queue behavior, but I need to think carefully about how to maintain FIFO order. If I simply push elements to one stack and pop from another, that would give me LIFO order, which is wrong. Let me think about how to optimize this.

The key insight is that I need to ensure the oldest element is always at the top of one stack so it can be popped efficiently. If I maintain one stack for incoming elements and another for outgoing elements, I can achieve O(1) amortized operations.

Let me consider a brute force approach first: I could use one stack and for each dequeue operation, I'd need to move all elements to a temporary stack, pop the first element, then move everything back. That's O(n) for each dequeue operation, which is inefficient.

The improved approach is to use two stacks strategically. When I enqueue an element, I push it to the "input" stack. When I dequeue, if the "output" stack is empty, I transfer all elements from input to output stack (this reverses the order). Then I pop from the output stack. This ensures that each element is moved at most once between stacks, giving us O(1) amortized time complexity.

The key optimization is to only transfer elements when necessary - when the output stack becomes empty, and we need to get the oldest element. This way, we maintain the invariant that all elements in the output stack are in FIFO order.

Final approach: Use two stacks - one for enqueue operations (input), one for dequeue operations (output). When output stack is empty, transfer all elements from input to output. This maintains the FIFO property while achieving efficient operations.

Important invariants that must hold:

1. All elements in input stack are newer than those in output stack
2. Elements in output stack are in FIFO order (oldest at top)
3. When output stack is not empty, we can directly pop from it
4. When output stack is empty, all elements from input must be moved to output before any dequeue operation

4. Data Structure Choice

For implementing a queue using stacks, I need to carefully consider the data structures that will support the required operations efficiently.

The primary data structure is two stacks: stack1 and stack2. These are essential because:

• Stack1 serves as the main storage for incoming elements
• Stack2 acts as a temporary buffer during dequeue operations to reverse the order

Why two stacks are needed: The fundamental challenge is that stacks follow LIFO (Last In, First Out) order, while queues require FIFO (First In, First Out) order. By using two stacks, I can leverage one to maintain the correct order while the other supports efficient insertion.

Stack1 (primary storage):

• Used for pushing new elements to the queue
• Elements are added to the top of this stack in O(1) time
• Maintains elements in reverse order from desired queue sequence

Stack2 (temporary buffer):

• Used during dequeue operations to reverse the order
• Elements are moved from stack1 to stack2 when needed
• Provides O(1) access to the oldest element

Time and space impact:

• Time complexity for push operations: O(1) - direct stack push
• Time complexity for pop/peek operations: Amortized O(1) - elements are moved at most once from stack1 to stack2
• Space complexity: O(n) - where n is the number of elements in the queue

Helper structure considerations: I'm not using any additional helper structures beyond the two stacks. The implementation maintains clean separation between the storage and processing stacks, which simplifies the logic and reduces memory overhead.

This choice directly enables the core insight that queue operations can be efficiently implemented by maintaining proper ordering between two stacks, avoiding the need for expensive array reshuffling or complex state tracking.

5. Algorithm Walkthrough

Let me trace through the implementation with a concrete example to show how the algorithm works step by step.

Example: We'll simulate a queue with operations: push(1), push(2), push(3), pop(), push(4), pop(), peek().

Step 1: Push 1

• stack1 = [1] (after pushing to input stack)
• stack2 = [] (empty output stack)
• Invariant maintained: stack1 contains elements in FIFO order, stack2 is empty

Step 2: Push 2

• stack1 = [1, 2] (pushing to input stack)
• stack2 = []
• Invariant maintained: stack1 contains elements in FIFO order

Step 3: Push 3

• stack1 = [1, 2, 3]
• stack2 = []
• Invariant maintained: stack1 contains elements in FIFO order

Step 4: Pop operation

• Need to return first element (1) from queue
• stack2 is empty, so we must transfer elements from stack1
• Transfer: stack1 = [2, 3], stack2 = [1] (popping from stack1 and pushing to stack2)
• Pop from stack2: return 1
• Result: pop() returns 1

Step 5: Push 4

• stack1 = [2, 3, 4] (pushing to input stack)
• stack2 = [] (empty - elements still in proper order in stack1)
• Invariant maintained: stack1 contains elements in FIFO order

Step 6: Pop operation

• stack2 is empty, so transfer elements from stack1
• Transfer: stack1 = [3, 4], stack2 = [2]
• Pop from stack2: return 2
• Result: pop() returns 2

Step 7: Peek operation

• stack2 = [2] (non-empty) - elements are in proper order
• Peek from stack2: return 2 (top element)
• Result: peek() returns 2

The algorithm correctly maintains FIFO order by ensuring that elements are only transferred from stack1 to stack2 when stack2 is empty, which guarantees that the oldest element gets moved to the top of stack2 for efficient retrieval.

The key insight is that we only perform the expensive transfer operation when necessary, making it amortized O(1) for queue operations.

6. Java Solution

import java.util.Stack;

public class MyQueue {
    private Stack<Integer> stack1;  // for pushing elements
    private Stack<Integer> stack2;  // for popping/peeking elements
    
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    /**
     * Push element x to the back of queue.
     * Time: O(1)
     */
    public void push(int x) {
        stack1.push(x);
    }
    
    /**
     * Removes the element from in front of queue and returns that element.
     * Time: Amortized O(1)
     */
    public int pop() {
        if (stack2.isEmpty()) {
            // Transfer all elements from stack1 to stack2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        
        return stack2.pop();
    }
    
    /**
     * Get the front element.
     * Time: Amortized O(1)
     */
    public int peek() {
        if (stack2.isEmpty()) {
            // Transfer all elements from stack1 to stack2
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        
        return stack2.peek();
    }
    
    /**
     * Returns whether the queue is empty.
     * Time: O(1)
     */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

This implementation uses two stacks to simulate queue behavior. The key insight is that we maintain elements in stack2 in reverse order (so the oldest element is at the top), and only transfer elements from stack1 to stack2 when needed. This ensures that each element is moved at most once between stacks, making the amortized time complexity O(1) for all operations.

7. Complexity Analysis

Time Complexity: O(1) amortized for enqueue and dequeue operations

For the push operation in the first approach (where we move elements between stacks), each element is moved at most twice - once when it's pushed to the second stack, and once when it's popped from the first stack. Since each element is moved at most twice throughout its lifetime, the amortized cost per operation is O(1).

For the second approach (where we keep one stack for pushing and another for popping), the push operation is O(1) as it simply adds to the first stack. The pop operation is amortized O(1) because elements are moved from the first stack to the second stack only when the second stack is empty.

Space Complexity: O(n) where n is the number of elements in the queue. We use two stacks to store all elements, so the space complexity is linear with respect to the input size.

Why these bounds are correct:

• The amortized analysis works because we're distributing the cost of expensive operations (moving elements between stacks) across multiple cheaper operations.
• Each element is pushed and popped exactly once from each stack in the optimal approach, making the total cost linear.
• The space complexity is straightforward since we're storing all elements in two stacks.

Optimality: This solution achieves optimal amortized time complexity for queue operations using stacks. Since each element must be processed at least once for enqueue and dequeue, we cannot do better than O(1) amortized time complexity. The space complexity is also optimal as we must store all elements to maintain queue properties.

The solution is near-optimal because:

1. It matches the theoretical lower bound for queue operations using stacks
2. It provides O(1) amortized performance for both operations
3. It uses minimal additional space proportional to input size

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty queue operations: The solution must handle dequeue() and peek() on empty queues gracefully, typically throwing NoSuchElementException or returning null
• Single element: Operations on a queue with exactly one element must work correctly, especially the transition from one to zero elements
• Consecutive operations: Sequential enqueue() followed by dequeue() should work without issues

Duplicate Values and Repeated States

• Duplicate elements: Enqueuing identical values should not break the queue's FIFO behavior
• State consistency: After multiple operations, the internal stack states must remain consistent to maintain proper order

Boundary Conditions

• Stack overflow: If using fixed-size stacks, handle potential overflow conditions (though this is less likely in Java)
• Integer overflow: When tracking stack sizes, ensure integer arithmetic doesn't overflow (though not a concern in typical implementations)
• Null elements: Handle null element insertion appropriately based on requirements

Common Implementation Mistakes

• Incorrect stack management: Forgetting to move elements between stacks when needed, leading to wrong order
• Missing stack synchronization: Not properly maintaining the invariant that one stack is always empty during operations
• Inefficient stack transfers: Moving elements unnecessarily on every operation instead of amortizing the cost
• Not handling concurrent access: If used in multi-threaded context, race conditions between push/pop operations on the same stack
• Incorrect exception handling: Throwing wrong exceptions or not throwing them when required

The most critical pitfall is maintaining the FIFO property - any deviation in element ordering will make the queue behavior incorrect.

9. Alternative Approaches

There are two main alternative approaches to implementing a queue using stacks:

Approach 1: Amortized O(1) Push, O(n) Pop Instead of using two stacks to achieve O(1) queue operations, we can use just one stack and reverse the elements during pop operations. When pushing, we simply add to the top of the stack. When popping, we move all elements to a temporary stack, pop the top element, then move everything back. This approach has O(1) amortized push but O(n) worst-case pop.

Approach 2: Two Stack with Lazy Transfer This is the approach we implemented, but with a different transfer strategy. Instead of transferring elements from input to output stack only when output is empty, we can transfer elements whenever the output stack becomes empty. This maintains the same time complexity but changes when transfers occur.

Trade-offs:

The first alternative has better push performance but worse pop performance - it's O(1) amortized for push operations but O(n) worst-case for pop, which violates the expected queue behavior where both operations should be efficient.

The second alternative maintains the same O(1) amortized complexity for both operations but changes the transfer timing. This can be slightly more complex to reason about but offers no significant advantage in performance.

Our chosen solution is superior because:

1. It provides truly O(1) amortized time complexity for both operations
2. The transfer strategy is clean and intuitive - only happens when needed
3. It's easier to reason about correctness and maintainability

The key insight is that we only need to transfer elements when the output stack is empty, ensuring each element is moved at most once. This makes our approach optimal in both time and space complexity.

// Alternative 1: Lazy transfer with single stack (not recommended)
class QueueWithSingleStack {
    private Stack<Integer> stack;
    
    public QueueWithSingleStack() {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
    }
    
    public int pop() {
        Stack<Integer> temp = new Stack<>();
        while (stack.size() > 1) {
            temp.push(stack.pop());
        }
        int result = stack.pop();
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
        return result;
    }
    
    public int peek() {
        Stack<Integer> temp = new Stack<>();
        while (stack.size() > 1) {
            temp.push(stack.pop());
        }
        int result = stack.peek();
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
        return result;
    }
    
    public boolean empty() {
        return stack.isEmpty();
    }
}

10. Test Cases

import java.util.*;

public class QueueUsingStacksTest {
    public static void main(String[] args) {
        // Test Case 1: Basic enqueue/dequeue operations
        QueueUsingStacks queue = new QueueUsingStacks();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        assert queue.dequeue() == 1;
        assert queue.dequeue() == 2;
        assert queue.dequeue() == 3;
        
        // Test Case 2: Interleaved operations
        queue = new QueueUsingStacks();
        queue.enqueue(1);
        assert queue.dequeue() == 1;
        queue.enqueue(2);
        queue.enqueue(3);
        assert queue.dequeue() == 2;
        assert queue.dequeue() == 3;
        
        // Test Case 3: Empty queue operations
        queue = new QueueUsingStacks();
        assert queue.isEmpty() == true;
        try {
            queue.dequeue();
            assert false; // Should throw exception
        } catch (Exception e) {
            // Expected
        }
        
        // Test Case 4: Single element queue
        queue = new QueueUsingStacks();
        queue.enqueue(42);
        assert queue.dequeue() == 42;
        assert queue.isEmpty() == true;
        
        // Test Case 5: Multiple operations with peek
        queue = new QueueUsingStacks();
        queue.enqueue(10);
        queue.enqueue(20);
        assert queue.peek() == 10;
        assert queue.dequeue() == 10;
        assert queue.peek() == 20;
        assert queue.dequeue() == 20;
        
        System.out.println("All test cases passed!");
    }
}

Sample Test Cases:

1. Basic functionality: Enqueue 1,2,3 and dequeue in FIFO order (1,2,3)
2. Interleaved operations: Enqueue 1, dequeue 1, enqueue 2,3, then dequeue 2,3
3. Empty queue handling: Verify proper exception handling for dequeue on empty queue
4. Single element: Enqueue one element and immediately dequeue it
5. Peek operations: Verify peek works correctly with mixed queue operations

Tricky Case:

• Mixed enqueue/dequeue: Test that queue maintains proper order when operations are interleaved

Boundary Case:

• Empty queue: Verify that isEmpty() and dequeue() on empty queue behave correctly

These test cases cover the essential behaviors of a queue implementation including proper FIFO ordering, edge case handling, and correctness of all queue operations.

11. Final Summary

The core idea is to simulate FIFO queue behavior using two LIFO stacks by maintaining the invariant that one stack always contains elements in reverse order of their insertion. This solution efficiently handles queue operations with amortized O(1) time complexity, making it optimal for the given constraints. The key insight is that we only need to transfer elements between stacks when necessary, ensuring that each element is moved at most once across the stacks during its entire lifecycle in the queue.