Implement a first-in, first-out (FIFO) queue using only stack operations (push / pop / peek / size / empty on a last-in, first-out structure). The queue supports four operations:
- "push" — add an element x to the back of the queue. Returns null.
- "pop" — remove and return the element at the front of the queue.
- "peek" — return the element at the front without removing it.
- "empty" — return true if the queue is empty, false otherwise.
You are given the operations as two parallel arrays: operations[i] is the name of the i-th operation, and values[i] is its argument list ([x] for "push", [] for the others). Apply them in order and return an array holding each operation's return value (use null for "push").
"pop" and "peek" are only called on a non-empty queue.
Example
Push 1 then 2; peek and pop both return 1 (FIFO front); the queue still holds 2, so empty is false.
Constraints
- 1 <= operations.length <= 1000
- operations[i] is one of "push", "pop", "peek", "empty".
- 1 <= x <= 9 for every "push".
- At most 1000 calls total; pop/peek are only made on a non-empty queue.
Intuition
A queue is FIFO — first in, first out — but a stack is LIFO, so they pull in opposite directions. The naïve fix with a single stack: to dequeue, pop everything into a temporary holder so the oldest element surfaces, take it, then pour everything back.
// Using a single stack, every front operation reverses the whole thing twice.
function dequeue(stack) {
const tmp = [];
// Pour everything out so the oldest element ends up on top of tmp.
while (stack.length) tmp.push(stack.pop());
const front = tmp.pop(); // the oldest element
while (tmp.length) stack.push(tmp.pop()); // pour it all back
return front;
}Every single dequeue does two full O(n) reversals — O(n) per operation. Can we do better?
The key observation: that costly reversal doesn't have to happen every time. Use two stacks — an inStack for pushes and an outStack for fronts. Reverse inStack into outStack only when `outStack` is empty; that single pour flips the order so the oldest element sits on top of outStack. After that, pop and peek read straight off outStack's top with no reversal, until it drains and you transfer again.
This is the two-stacks technique (see the Stacks intro). The magic is amortized cost: each element is moved between the stacks at most once over its lifetime, so although one transfer is O(n), the cost spread across all operations is O(1) amortized each.
Why it works, step by step — say we push 1, 2, 3. inStack holds [1, 2, 3] (top is 3). The first peek/pop finds outStack empty and transfers: popping 3, then 2, then 1 onto outStack yields [3, 2, 1] (top is 1 — the oldest!). Now pop returns 1, pop returns 2 straight off the top. Push a 4: it lands on inStack, not outStack, so the front order is preserved. When outStack finally empties, the next front op transfers [4] over and continues. empty is just both stacks empty.
Note on the diagram: this problem is about two vertical stacks pouring into each other, which our 1-D lane diagram can't honestly depict — so this page teaches it in prose rather than forcing a misleading single-row animation. The stored solution below traces the same inStack/outStack model.
- Transfer only when `outStack` is empty — transferring while it still holds elements would interleave new pushes ahead of older ones and break FIFO order.
emptymust check both stacks: an element can be sitting in either the in- or the out-stack.
Optimization
Two stacks, lazy transfer
One stack alone reverses order: popping it returns the most recent push, but a queue needs the oldest. Use two stacks. inStack receives every push. When a pop or peek needs the front and outStack is empty, pour inStack into outStack — that single reversal flips the order so the oldest element is now on top of outStack. While outStack is non-empty, front operations read straight off its top; only when it drains do you transfer again.
Each element is moved between stacks at most once, so although a single transfer is O(n), every element is pushed and popped a constant number of times overall — O(1) amortized per operation.
O(1) amortized time per call, O(n) space for the elements held.
function runQueueOps(operations, values) {
const inStack = []; // newest pushes land here
const outStack = []; // reversed once, so its top is the queue front
const result = [];
// Move everything to outStack only when a front op needs it and outStack is empty.
const transfer = () => {
if (outStack.length === 0) {
while (inStack.length > 0) outStack.push(inStack.pop());
}
};
for (let i = 0; i < operations.length; i++) {
const op = operations[i];
if (op === "push") {
inStack.push(values[i][0]);
result.push(null);
} else if (op === "pop") {
transfer();
result.push(outStack.pop());
} else if (op === "peek") {
transfer();
result.push(outStack[outStack.length - 1]);
} else { // "empty"
result.push(inStack.length === 0 && outStack.length === 0);
}
}
return result;
}Complexity analysis
Time complexity: O(1) amortized per operation. Here's why:
pushis a single O(1) stack push.pop/peekare O(1) whenoutStackis non-empty; a transfer is O(n), but it moves each element exactly once over that element's lifetime.
So although a single front operation can be O(n), the cost amortizes to O(1) per operation across a sequence of m calls — the whole sequence is O(m).
Space complexity: O(n). Here's why:
- Every queued element lives in exactly one of the two stacks at any moment.
So the two stacks together hold at most n elements — O(n), where n is the number of elements currently in the queue.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| operations = ["push","peek","empty"], values = [[4],[],[]] | [null,4,false] | Peek returns the front (4) without removing it; the queue stays non-empty. |
| operations = ["push","push","peek","pop","empty"], values = [[1],[2],[],[],[]] | [null,null,1,1,false] | FIFO: peek and pop both return the oldest (1); 2 remains. |
| operations = ["push","pop","empty"], values = [[5],[],[]] | [null,5,true] | Push then drain — back to empty. |
| operations = ["push","push","pop","push","peek","pop","pop","empty"], values = [[1],[2],[],[3],[],[],[],[]] | [null,null,1,null,2,2,3,true] | A push (3) after a transfer lands on inStack, preserving FIFO order. |
| operations = ["push","push","push","pop","pop","pop","empty"], values = [[1],[2],[3],[],[],[],[]] | [null,null,null,1,2,3,true] | One transfer serves three pops in order 1, 2, 3. |
| operations = ["push","push","pop","pop"], values = [[8],[9],[],[]] | [null,null,8,9] | Two pushes then two pops drain oldest-first: 8 before 9. |
Try it yourself
Write your solution against the real judge before checking the reference.