DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Implement Queue using Stacks

EasyStacks and Queues
AmazonMicrosoft Community-reported practice tags — not verified company questions.

1Problem statement

Implement a FIFO queue using only two stacks. Support push(x), pop(), peek() and empty(). Each operation should be amortized O(1).

2Examples

Input: push(1), push(2), peek(), pop(), empty()
Output: 1, 1, false
Explanation: peek returns the front (1), pop removes it (1), and the queue still contains 2.

3Constraints

  • 1 ≤ x ≤ 9
  • At most 100 calls
  • pop and peek are only called on a non-empty queue.

4Approaches

Approach 1

Brute Force

On every push, move everything to the second stack, push, and move it all back.

Time O(n) pushSpace O(n)

Approach 2

Better

Transfer on every pop/peek (always move all back afterwards).

Time O(n) popSpace O(n)

Approach 3

Optimal: Lazy transfer

Push onto `in`. For pop/peek, only when `out` is empty move all of `in` into `out` (reversing order). Each element moves at most once.

Time O(1) amortizedSpace O(n)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  push(x) {
    this.inStack.push(x);
  }
  shift() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) this.outStack.push(this.inStack.pop());
    }
  }
  pop() {
    this.shift();
    return this.outStack.pop();
  }
  peek() {
    this.shift();
    return this.outStack[this.outStack.length - 1];
  }
  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

const q = new MyQueue();
q.push(1);
q.push(2);
console.log(q.peek());
console.log(q.pop());
console.log(q.empty());

6Complexity

Time

O(1) amortized

Space

O(n)

7Visual walkthrough

  1. 1.push 1, push 2 → in = [1, 2], out = []
  2. 2.peek: out empty → move → out = [2, 1] (top is 1) → returns 1
  3. 3.pop → returns 1, out = [2]
  4. 4.empty → in and out not both empty → false

Related visualization (Queue Enqueue and Dequeue) — shows the core data-structure operations this solution relies on:

Queue Enqueue and Dequeueinteractive Open full visualizer
enqueue 10enqueue 20enqueue 30dequeue()enqueue 40enqueue 50enqueue 60dequeue()dequeue()
circular array · data[]
null
0
▲front
null
1
null
2
null
3
rear = −1 (nothing enqueued yet)
in
10
front →(empty)← rear

Size 0 / 4 · FIFO — values leave in the same order they arrived

Just enqueuedLeaving (front)Slot being updated

A queue is First-In-First-Out (FIFO): enqueue adds at the rear, dequeue removes from the front. This circular-array queue wraps the rear pointer around to reuse freed slots.

1 / 49

8Related questions

Valid Parentheses

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions