Katkat
Back

Implement a FIFO Queue Using Two Stacks

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to adapt data structure behaviors by implementing a First-In-First-Out (FIFO) queue using only Last-In-First-Out (LIFO) stacks.

Problem Statement

Design a queue that supports the standard queue operations using only two stacks. The queue should support the following operations:

  • push(x): Pushes element x to the back of the queue.
  • pop(): Removes the element from the front of the queue and returns it.
  • peek(): Returns the element at the front of the queue.
  • empty(): Returns whether the queue is empty.

Implementation Requirements

You must only use standard stack operations: push(x), pop(), peek(), and empty(). Do not use any built-in queue or list collections that expose non-stack behavior.

Constraints

  • All operations must be valid (e.g., calling pop on an empty queue will not occur).
  • Try to optimize for amortized time complexity.

Example

# Initialize
q = MyQueue()
q.push(1)
q.push(2)
print(q.peek()) # Output: 1
print(q.pop())  # Output: 1
print(q.empty()) # Output: False

Edge Cases

  • Interleaving push and pop operations.
  • Performing peek or pop when the output stack is empty but the input stack has elements.

Hints

Hint 1

Use one stack to handle incoming elements and a second stack to reverse the order for outgoing elements.

Hint 2

Only move elements from the input stack to the output stack when the output stack is completely empty.

Hint 3

Consider the amortized cost; while a single operation might take O(n), the sequence of operations is more efficient.

Follow-up questions

  • What is the amortized time complexity of the `pop` and `peek` operations?
  • Can you implement this using only one stack and recursion?
  • How would you modify your implementation to be thread-safe in a concurrent environment?