Skip to main content

232. Implement Queue using Stacks

easy

Build a FIFO queue using only two LIFO stacks. The textbook 'two-stack technique' that shows up in interviews to test whether you understand amortized complexity.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: void push(int x) Pushes element x to the back of the queue. int pop() Removes the element from the front of the queue and returns it. int peek() Returns the element at the front of the queue. boolean empty() Returns true if the queue is empty, false otherwise. You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

Constraints

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, peek, and empty.
  • All the calls to pop and peek are valid.

Examples

Example 1

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation: MyQueue myQueue = new MyQueue(); myQueue.push(1); myQueue.push(2); myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

One stack reverses order. Two stacks reverse it twice — which is the original order.

Hint 2

Keep an 'input' stack for pushes and an 'output' stack for pops. When output is empty, drain input into output.

Hint 3

Don't move elements back to input. Once they're in output, they're in correct FIFO order — pop and peek directly from output.

Hint 4

Each element gets pushed and popped at most twice across both stacks: amortized O(1) per operation.

Solution approach

Reveal approach

Two-stack technique. Keep stackIn for incoming pushes and stackOut for outgoing pops/peeks. push(x) always pushes onto stackIn. pop() and peek() first ensure stackOut is non-empty: if it is, pop everything off stackIn and push onto stackOut (this reverses the order so the oldest element is on top). Then return the top of stackOut. empty() returns true iff both stacks are empty. Each element moves between stacks at most once, so push is O(1) worst case and pop/peek are amortized O(1). Don't shuffle elements back into stackIn after draining — that breaks the invariant and slows everything down.

Complexity

Time
Amortized O(1) per op
Space
O(n)

Related patterns

  • stack
  • queue
  • design
  • two-stack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Implement Queue using Stacks and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →