Design Queue Using Stacks

Problem

Implement a FIFO queue using only two LIFO stacks. Provide push(int), pop() (returns the dequeued value), peek(), and empty().

Constraints

• 1 ≤ ops ≤ 1000

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class MyQueue:
    def __init__(self):
        self.inn = []
        self.out = []

    def push(self, x):
        self.inn.append(x)

    def _shift(self):
        if not self.out:
            while self.inn:
                self.out.append(self.inn.pop())

    def pop(self):
        self._shift()
        return self.out.pop()

    def peek(self):
        self._shift()
        return self.out[-1]

    def empty(self):
        return not self.inn and not self.out

Java

import java.util.*;

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>();
    private Deque<Integer> out = new ArrayDeque<>();
    public void push(int x) { in.push(x); }
    public int pop() { shift(); return out.pop(); }
    public int peek() { shift(); return out.peek(); }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
    private void shift() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
    }
}

class Solution {}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.