Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Implement Queue using Stacks

How to compose two stacks to simulate a queue and understand why lazy transfer keeps the amortized cost low.

Stack Intermediate 15 min TypeScript

#interviews#stack#queue#design

Implement a queue using only stacks.

The structure must support:

  • push(x)
  • pop()
  • peek()
  • empty()

In the original problem, this is usually a class. In the SeniorPath playground, use:

  • operations: the list of operations
  • values: the value associated with each operation, or null

And return an array with the results. Operations with no return value should return null.

Example:

Input:
  operations = ["MyQueue","push","push","peek","pop","empty"]
  values     = [null,1,2,null,null,null]

Output:
  [null,null,null,1,1,false]

What to notice before coding

  • A queue is FIFO. A stack is LIFO.
  • The problem is about structure composition.
  • The strong part is avoiding unnecessary transfers.

Common mistakes

  • moving all elements back and forth on every operation
  • forgetting that `peek` and `pop` must read from the same logical end of the queue

Step 1 - Model the correct behavior first

Before thinking about stacks, it helps to lock in the behavior:

  • enter at the end
  • leave from the front

That is a queue.

Step 2 - Write the simplest baseline

The most direct baseline is using an array as a queue:

  • push adds at the end
  • pop removes from the front
  • peek looks at the front

It works for modeling the semantics.

But it does not respect the stack-only constraint.

Step 3 - Ask how two stacks can simulate FIFO

The key idea is separating:

  • what just came in
  • what is ready to come out

If you pour one full stack into another, the order flips.

And that inversion is exactly what turns LIFO into FIFO.

Step 4 - Transfer only when needed

If you transfer every time, it works, but it wastes work.

The stronger version does this:

  • incoming receives pushes
  • outgoing serves pops and peeks
  • only transfer from incoming to outgoing when outgoing is empty

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function runMyQueue(operations, values) {
  // operations example: ["MyQueue", "push", "peek"]
  // values example: [null, 1, null]
  // your solution here
  return []
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(1) amortized

Space: O(n)

Solution 1 - Simulate with an array queue

Good baseline to lock in the right semantics.

export function runMyQueue(operations, values) {
  const queue = []
  const output = []

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MyQueue") {
      output.push(null)
    } else if (operation === "push") {
      queue.push(value)
      output.push(null)
    } else if (operation === "pop") {
      output.push(queue.shift() ?? null)
    } else if (operation === "peek") {
      output.push(queue[0] ?? null)
    } else if (operation === "empty") {
      output.push(queue.length === 0)
    }
  }

  return output
}

Correct for behavior, but not for the stack-only restriction.

Solution 2 - Two stacks with lazy transfer and amortized O(1)

Now the structure respects the problem and avoids repeated work.

export function runMyQueue(operations, values) {
  const incoming = []
  const outgoing = []
  const output = []

  function rebalance() {
    if (outgoing.length === 0) {
      while (incoming.length > 0) {
        outgoing.push(incoming.pop())
      }
    }
  }

  for (let index = 0; index < operations.length; index += 1) {
    const operation = operations[index]
    const value = values[index]

    if (operation === "MyQueue") {
      output.push(null)
    } else if (operation === "push") {
      incoming.push(value)
      output.push(null)
    } else if (operation === "pop") {
      rebalance()
      output.push(outgoing.pop() ?? null)
    } else if (operation === "peek") {
      rebalance()
      output.push(outgoing[outgoing.length - 1] ?? null)
    } else if (operation === "empty") {
      output.push(incoming.length === 0 && outgoing.length === 0)
    }
  }

  return output
}

The most important part here is not the syntax. It is understanding why transfer only needs to happen sometimes.

What to say in the interview

A strong short explanation would be:

I separate new elements into an input stack and elements ready to leave into an output stack. When I need to pop or peek and the output stack is empty, I transfer everything from input to output. That inversion preserves FIFO behavior, and the cost becomes O(1) amortized.

That shows that you:

  • understood how the two structures compose
  • can justify lazy transfer
  • can talk about amortized cost concretely

When this pattern shows up again

The same pattern comes back when you need to:

  • compose simple structures into new behavior
  • use on-demand transfer
  • discuss amortized cost
  • separate write phase from read phase

The point is not memorizing MyQueue.

The point is learning to build larger behavior from smaller pieces.
Next challenge House Robber Previous challenge Min Stack

Related challenges

Min Stack

Valid Parentheses

Longest Substring Without Repeating Characters

Related articles

Thinking Before You Code in Interviews

How to Explain Your Solution Without Getting Lost

Recognizing Problem Patterns