Workspace

Problem workspace

3 day streakD

Queue Using Two Stacks

EasyStacksStack foundations

The challenge

Implement a FIFO queue using two LIFO stacks. Return each peek or pop result.

Operations are push:value, pop, peek. Empty queries return null.

Example

push:1, push:2, peek, pop, push:3, pop, pop → [1, 1, 2, 3].

Use the walkthrough below to inspect the input and each state change.

See Queue Using Two Stacks, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.push…0push…1peek2pop3push…4pop5pop6Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 12

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["push:1","push:2","peek","pop","push:3","pop","pop"]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Transfer incoming to outgoing only when outgoing is empty.

Indices are zero-based. C++ uses C++17 or later.

class MyQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []

    def _transfer(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

    def push(self, value):
        self.incoming.append(value)

    def peek(self):
        self._transfer()
        return self.outgoing[-1] if self.outgoing else None

    def pop(self):
        self._transfer()
        return self.outgoing.pop() if self.outgoing else None


def solve(operations):
    queue, output = MyQueue(), []
    for token in operations:
        op, _, raw = token.partition(':')
        if op == 'push': queue.push(int(raw))
        else: output.append(queue.pop() if op == 'pop' else queue.peek())
    return output

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap