Queue Implementation with Two Stacks in JavaScript

This challenge asks you to implement a Queue data structure using only two Stacks. Queues follow the First-In, First-Out (FIFO) principle, while stacks follow Last-In, First-Out (LIFO). This exercise tests your understanding of data structures and your ability to creatively utilize them to achieve a desired outcome.

Problem Description

You are required to implement a QueueWithStacks class in JavaScript. This class should mimic the behavior of a standard Queue, supporting the following operations:

• enqueue(item): Adds an item to the rear of the queue.
• dequeue(): Removes and returns the item at the front of the queue. Returns null if the queue is empty.
• peek(): Returns the item at the front of the queue without removing it. Returns null if the queue is empty.
• isEmpty(): Returns true if the queue is empty, false otherwise.

You must implement this class using only two JavaScript arrays, which will act as your stacks. You are not allowed to use any built-in queue data structures or methods. The efficiency of your implementation will be considered.

Key Requirements:

• The enqueue operation should be relatively efficient (ideally O(1) on average).
• The dequeue operation might be less efficient, but it should still function correctly.
• All operations must adhere to the FIFO principle of a queue.
• The class should be well-documented with comments explaining the logic.

Expected Behavior:

The class should behave exactly like a standard queue. Items added to the queue should be removed in the order they were added. The peek operation should return the next item to be dequeued without modifying the queue.

Edge Cases to Consider:

• Empty queue: Handle cases where dequeue or peek are called on an empty queue.
• Multiple enqueues and dequeues: Ensure the FIFO order is maintained throughout a series of operations.
• Large number of operations: Consider the performance implications of your implementation.

Examples

Example 1:

Input:
enqueue(1);
enqueue(2);
enqueue(3);
dequeue();
enqueue(4);
dequeue();
peek();

Output:

1
2
3
4

Explanation: We enqueue 1, 2, and 3. Then we dequeue 1, leaving 2 and 3 in the queue. We enqueue 4, so the queue contains 2, 3, and 4. Finally, peek() returns 2.

Example 2:

Input:
enqueue("a");
enqueue("b");
dequeue();
dequeue();
dequeue();

Output:

"a"
"b"
null

Explanation: We enqueue "a" and "b". We dequeue "a" and then "b", leaving the queue empty. A subsequent dequeue() call returns null.

Example 3: (Edge Case - Empty Queue)

Input:
dequeue();
peek();

Output:

null
null

Explanation: The queue is initially empty. dequeue() and peek() both return null as expected.

Constraints

• The input item to enqueue can be any valid JavaScript data type.
• The number of enqueue and dequeue operations can vary significantly (up to 10,000).
• The space complexity of your solution should be proportional to the number of elements in the queue.
• While not strictly required, strive for an implementation where enqueue is O(1) and dequeue is O(n) in the worst case, but performs well on average.

Notes

Think about how you can use one stack to hold the incoming elements and the other stack to temporarily store elements when dequeuing. The key is to efficiently transfer elements between the stacks to maintain the FIFO order. Consider the order in which elements are pushed and popped from each stack.