Full lesson preview

Design a queue using two stacks

Implement a FIFO queue using two LIFO stacks. Support enqueue, dequeue, peek, and empty operations.

Python practice22 minStacks & QueuesAdvancedLast updated March 27, 2026

Problem statement

You are asked to implement a queue data structure using exactly two stacks. The queue should support the following operations: - enqueue(x): Add element x to the end of the queue. - dequeue(): Remove and return the element from the front of the queue. If the queue is empty, return None. - peek(): Return the element at the front of the queue without removing it. If the queue is empty, return None. - empty(): Return True if the queue is empty, False otherwise. Additionally, provide a helper function run_ops(ops) that takes a list of operations described as [operation_name, optional_value] and executes them in order on a queue instance, returning a list of results for operations that produce values (dequeue, peek, empty). This helper will be used by the test harness to validate behavior using a single expression.

Task

Build a queue using two stacks and a helper runner to validate sequences of operations.

Examples

Basic enqueue and dequeue

Input

run_ops([['enqueue', 1], ['enqueue', 2], ['dequeue'], ['dequeue'], ['empty']])

Output

[1, 2, True]

Enqueue 1 and 2, then dequeue twice returns 1 and 2. After both removals the queue is empty.

Input format

A list of operations. Each operation is a list where the first element is the operation name: 'enqueue', 'dequeue', 'peek', or 'empty'. 'enqueue' operations include a second element with the value to add.

Output format

A Python list of results (in order) for operations that return values: dequeue, peek, and empty. Returned as a standard Python list (e.g. [1, 2, True]).

Constraints

- You must only use two stacks (Python lists) for the queue internal storage. - enqueue, dequeue, and peek should have amortized O(1) time. - Do not use collections.deque or other high-level queue/stack libraries. - The helper run_ops must be a single callable used by tests.

Samples

Sample 1

Input

run_ops([['enqueue', 10], ['enqueue', 20], ['peek'], ['dequeue'], ['peek']])

Output

[10, 10, 20]

peek returns 10, dequeue returns 10, then peek returns 20.