How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Implement a FIFO Queue Using Two Stacks

Quick Overview

This question evaluates understanding of data structure design, specifically simulating queue (FIFO) behavior using only stack (LIFO) operations. It is commonly asked in coding interviews to assess amortized time complexity reasoning and the ability to translate between abstract data structure interfaces, testing practical algorithmic implementation skill.

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Implement a FIFO Queue Using Two Stacks Implement a first-in-first-out (FIFO) queue using only two last-in-first-out (LIFO) stacks. The implemented queue must support all the standard queue operations. Implement the `MyQueue` class: - `void push(int x)` — push element `x` to the back of the queue. - `int pop()` — remove the element at the front of the queue and return it. - `int peek()` — return the element at the front of the queue without removing it. - `boolean empty()` — return `true` if the queue is empty, `false` otherwise. ## Rules - You may use **only** the standard operations of a stack: push to top, peek/pop from top, get size, and check if empty. - You must use **two stacks** as the underlying storage. Depending on your language, you may simulate a stack using the list / deque / array operations that correspond to a stack (push and pop from the same end). - `pop` and `peek` are only ever called on a non-empty queue. ## Example ``` push(1); push(2); peek(); // returns 1 pop(); // returns 1 empty(); // returns false ``` ## Constraints - `1 <= x <= 9` - At most `100` calls in total are made to `push`, `pop`, `peek`, and `empty`. ## Follow-up Can you implement the queue so that each operation runs in **amortized** `O(1)` time, even though an individual `pop`/`peek` may occasionally take `O(n)`?

Quick Answer: This question evaluates understanding of data structure design, specifically simulating queue (FIFO) behavior using only stack (LIFO) operations. It is commonly asked in coding interviews to assess amortized time complexity reasoning and the ability to translate between abstract data structure interfaces, testing practical algorithmic implementation skill.

Implement a first-in-first-out (FIFO) queue using only two last-in-first-out (LIFO) stacks. The queue must support the standard operations: push, pop, peek, and empty. Implement the `MyQueue` class: - `void push(int x)` — push element `x` to the back of the queue. - `int pop()` — remove the element at the front of the queue and return it. - `int peek()` — return the element at the front of the queue without removing it. - `boolean empty()` — return `true` if the queue is empty, `false` otherwise. **Rules** - You may use only the standard operations of a stack: push to top, peek/pop from top, get size, and check if empty. - You must use two stacks as the underlying storage. - `pop` and `peek` are only ever called on a non-empty queue. **Driver format for this console.** Because a class cannot be graded directly here, your `solution(operations, values)` receives a list of operation names and a parallel list of argument lists, replays them against your `MyQueue`, and returns a list of results — one per operation: `None` for the constructor `"MyQueue"` and for `push`, the returned integer for `pop`/`peek`, and a boolean for `empty`. Example: ``` operations = ["MyQueue", "push", "push", "peek", "pop", "empty"] values = [[], [1], [2], [], [], []] -> [None, None, None, 1, 1, False] ``` **Follow-up.** Can you make every operation run in amortized O(1) time, even though an individual `pop`/`peek` may occasionally take O(n)? (The two-stack lazy-transfer approach achieves this.)

Constraints

1 <= x <= 9
At most 100 calls in total are made to push, pop, peek, and empty.
pop and peek are only ever called on a non-empty queue.
Only standard stack operations may be used, and the storage must be two stacks.

Examples

Input: (['MyQueue', 'push', 'push', 'peek', 'pop', 'empty'], [[], [1], [2], [], [], []])

Expected Output: [None, None, None, 1, 1, False]

Explanation: Push 1 then 2. peek() returns the front (1). pop() removes and returns 1. The queue still holds 2, so empty() is False.

Input: (['MyQueue', 'push', 'pop', 'empty'], [[], [5], [], []])

Expected Output: [None, None, 5, True]

Explanation: Push 5, pop returns 5, and the queue is now empty so empty() is True.

Input: (['MyQueue', 'empty'], [[], []])

Expected Output: [None, True]

Explanation: A freshly constructed queue with no elements: empty() returns True.

Input: (['MyQueue', 'push', 'push', 'push', 'pop', 'push', 'peek', 'pop', 'pop', 'empty'], [[], [3], [7], [9], [], [4], [], [], [], []])

Expected Output: [None, None, None, None, 3, None, 7, 7, 9, False]

Explanation: Push 3,7,9; pop returns 3 (FIFO front). Push 4 (queue is now 7,9,4). peek returns 7, pop returns 7, pop returns 9. The queue holds only 4, so empty() is False. This interleaves pushes after a transfer to confirm ordering stays correct.

Hints

Use two stacks: one for incoming pushes (in_stack) and one for outgoing pops/peeks (out_stack).
Always push new elements onto in_stack. Only move elements to out_stack when out_stack is empty and you need to pop or peek.
Transferring reverses the order once: the bottom of in_stack becomes the top of out_stack, which is exactly the front of the FIFO queue.
The queue is empty only when BOTH stacks are empty. Each element is transferred at most once, giving amortized O(1) operations.

Quick Overview