Domain 1EasyCORE

Implement Queue using Stacks

The problem requires implementing a queue using only two stacks. A queue operates on a first-in-first-out (FIFO) principle, meaning the first element added is the first one to be removed. The stack data structure operates in a last-in-first-out (LIFO) manner by default, so we need to cleverly use two stacks to simulate queue behavior.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack#Design

232. Implement Queue using Stacks

Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 52.7%


Problem Breakdown

The problem requires implementing a queue using only two stacks. A queue operates on a first-in-first-out (FIFO) principle, meaning the first element added is the first one to be removed. The stack data structure operates in a last-in-first-out (LIFO) manner by default, so we need to cleverly use two stacks to simulate queue behavior.

Inputs:

  • push(int x): Adds an element to the back of the queue.
  • pop(): Removes and returns the element from the front of the queue.
  • peek(): Returns the element at the front of the queue without removing it.
  • empty(): Checks if the queue is empty.

Outputs:

  • For push, no output (void).
  • For pop and peek, an integer representing the element at the front of the queue.
  • For empty, a boolean indicating whether the queue is empty.

Implicit Constraints/Edge Cases:

  • The stack operations allowed are only push to top, peek/pop from top, size, and is empty.
  • The number of calls to each operation is limited (at most 100).
  • All calls to pop and peek are guaranteed to be valid, meaning the queue will not be empty when these operations are called.

Intuition

A brute-force approach would involve using one stack for all operations, which would not efficiently simulate a queue’s FIFO behavior. The key insight is to use two stacks: one for enqueue operations (stack1) and another for dequeue operations (stack2). When dequeuing or peeking, if stack2 is empty, we transfer all elements from stack1 to stack2, reversing their order to maintain the correct FIFO sequence.

Approach

  1. Data Structures:

    • Use two stacks, stack1 for enqueue operations and stack2 for dequeue operations.
  2. Push Operation:

    • Simply push the element onto stack1.
  3. Pop Operation:

    • If stack2 is empty, transfer all elements from stack1 to stack2 (this reverses their order).
    • Pop and return the top element of stack2.
  4. Peek Operation:

    • Similar to pop, if stack2 is empty, transfer all elements from stack1 to stack2.
    • Return the top element of stack2 without popping it.
  5. Empty Operation:

    • The queue is empty if both stack1 and stack2 are empty.

Complexity Analysis

  • Time Complexity:

    • Each operation (push, pop, peek) has an amortized time complexity of (O(1)). This is because each element is moved between the stacks at most once per operation.
  • Space Complexity:

    • The space complexity is (O(n)), where (n) is the number of elements in the queue. This is due to the storage required for both stacks.

Solution

class MyQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        # Push element x to the back of stack1
        self.stack1.append(x)

    def pop(self) -> int:
        # Ensure stack2 has the elements in FIFO order
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        # Pop and return the top element from stack2
        return self.stack2.pop()

    def peek(self) -> int:
        # Ensure stack2 has the elements in FIFO order
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        # Return the top element from stack2 without popping it
        return self.stack2[-1]

    def empty(self) -> bool:
        # The queue is empty if both stacks are empty
        return not self.stack1 and not self.stack2

Edge Cases Handled

  • Empty Queue: The empty method correctly returns true when both stacks are empty.
  • Single Element: Operations work correctly even when there’s only one element in the queue.
  • Multiple Elements: The FIFO order is maintained for multiple elements pushed and popped.