Abstract / Summary

Implement a queue using two stacks to manage enqueue and dequeue operations.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (2+ million submissions).

Typical patterns to solve this problem:

• Design
• Queue
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a MyQueue class that mimics a first-in-first-out (FIFO) queue using a single Python list as an underlying stack. The class supplies the typical queue operations-push, pop, peek, and empty-and relies on a helper method reverse to reorder elements when necessary. By repeatedly reversing the internal list, the code transforms stack semantics into queue semantics without introducing additional data structures.

Core Components

The reverse Helper

def reverse(self, s):
    result = []
    while (len(s) > 0):
        result.append(s.pop())
    return result

The reverse method consumes the input list s by repeatedly popping its last element and appending that element to a new list result. Because list.pop() without an index removes the final element in constant time, the reversal proceeds efficiently. The method returns a brand-new list that contains the elements of s in opposite order, leaving s empty after execution.

Constructor

def __init__(self):
    self.stack = []

The constructor initializes an instance attribute stack as an empty list. This attribute holds the elements that have been enqueued. The class also declares a class-level variable stack = [], but the instance attribute shadows it, ensuring each queue instance maintains its own storage.

push Operation

def push(self, x: int) -> None:
    self.stack.append(x)

Adding an element to the queue is a direct append to the internal list. Since appending to the end of a Python list is an amortized constant-time operation, the push method introduces minimal overhead.

pop Operation

def pop(self) -> int:
    other = self.reverse(self.stack)
    result = other.pop()
    self.stack = self.reverse(other)
    return result

To remove the front element, the method first reverses self.stack, turning the oldest element into the last position of the new list other. It then pops that element, which corresponds to the queue’s head. Finally, it restores the original order by reversing other back into self.stack. The two reversals guarantee that the internal representation always reflects the order of enqueued items after a pop.

peek Operation

def peek(self) -> int:
    other = self.reverse(self.stack)
    result = other.pop()
    self.stack.append(result)
    while (len(other) > 0):
        self.stack.append(other.pop())
    return result

The peek method follows a similar pattern to pop but preserves the front element. After reversing self.stack into other, it extracts the front value with other.pop(). The extracted value is immediately re-appended to self.stack, and the remaining elements of other are transferred back in reverse order, effectively reconstructing the original stack without discarding the peeked element.

empty Check

def empty(self) -> bool:
    return len(self.stack) == 0

The emptiness test simply evaluates the length of the internal list. An empty list yields True, indicating that no elements are present in the queue.

Edge Cases Handled

When the queue is empty, both pop and peek invoke reverse on an empty list. The while loop inside reverse terminates immediately, returning an empty list. Subsequent calls to pop() on this empty list would raise an IndexError, which aligns with the typical behavior of a queue when attempting to remove from an empty container. The empty method correctly reports the state before such operations.

For a single-element queue, the reversal process yields a list containing that sole element. The pop method removes it, and the subsequent reversal restores an empty internal list. The peek method extracts the element, re-adds it, and then restores the original order, leaving the queue unchanged after the peek.

Multiple elements are handled by the two-step reversal in pop and the three-step transfer in peek. The order of elements after each operation matches the FIFO contract, regardless of how many items have been enqueued.

Performance Optimizations Observed

The implementation leverages Python’s list pop() from the end, which operates in constant time, to achieve an efficient reversal without explicit indexing. By constructing a new list during reversal rather than inserting at the front, the code avoids the linear-time cost associated with list.insert(0, ...).

Both pop and peek reuse the same reverse routine, eliminating duplicated logic and ensuring that any internal optimization to the reversal process benefits all queue operations.

The push method’s direct append avoids any intermediate copying, keeping the amortized cost low even under heavy insertion workloads.

Overall, the design balances simplicity with the intrinsic performance characteristics of Python lists, delivering queue semantics while staying within the constraints of the underlying stack-based storage.

Imagine a train made of toy blocks. The computer has a special box called a stack where it keeps these blocks. When you put a block in the box, it sits right on top of all the others. Because the last block you added is always the easiest one to reach, the computer has to do some rearranging to treat the stack like a line where it can get the first block you gave it.

The part called reverse is like taking all the blocks out of the box and flipping their order so the one at the very bottom is now sitting on top.

When you push a new block, it just gets added to the top of the stack.

When you want to pop a block out, the computer flips everything upside down so the oldest block is reachable. It takes that block out and then flips everything back to the way it was before.

When you want to peek at the block at the front, the computer does the same flip dance. It takes that first block out to look at it, then puts it back into the stack along with all the others in the right order.

The empty part just checks if there are any blocks left in the stack. If the box has nothing inside, it says that the line is empty.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		Rust			TS			Go
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim							C
	everthis						JS
	fartem									Ruby
	gaosq0604		Python
	halfrost											Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	luangong								TS
	lzl124631x	C++
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	TypeScript
lzl124631x	C++
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality