Implement a FIFO Queue Using Two Stacks

Question

The question asks the candidate to implement a FIFO (First In, First Out) queue using two stacks, demonstrating their understanding of data structures and algorithms.

Codemia · Accepted Answer

To implement a FIFO queue using two stacks, we will use one stack for enqueue operations and the other for dequeue operations. The key idea is to reverse the order of elements when transferring from one stack to the other, which allows us to maintain the FIFO order.

1. **Enqueue Operation**: Push the new element onto the first stack. 
2. **Dequeue Operation**: If the second stack is empty, pop all elements from the first stack and push them onto the second stack. Then pop the top element from the second stack. 
3. **Peek Operation**: Similar to dequeue, but return the top element of the second stack without removing it.

The time complexity for both enqueue and dequeue operations is O(1) on average, but the worst-case time complexity for dequeue is O(n) when transferring elements between stacks. The space complexity is O(n) as we are storing all elements in the two stacks.

```python
class MyQueue:
    def __init__(self):
        self.stack1 = []  # Stack for enqueue
        self.stack2 = []  # Stack for dequeue

def enqueue(self, x: int) -> None:
        self.stack1.append(x)

def dequeue(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop() if self.stack2 else None

def peek(self) -> int:
        if self.stack2:
            return self.stack2[-1]
        return self.stack1[0] if self.stack1 else None

def empty(self) -> bool:
        return not self.stack1 and not self.stack2
```

It is important to handle cases where dequeue or peek operations are called on an empty queue. The implementation should return None or raise an exception appropriately, ensuring robustness.

Implement a FIFO Queue Using Two Stacks

Apple

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Apple Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string