How to solve LeetCode 232 (Implement Queue using Stacks)?

This page provides optimized solutions for LeetCode problem 232 (Implement Queue using Stacks) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 232: Implement Queue using Stacks Solution

Problem Description

Explanation

To implement a queue using two stacks, we can use one stack for pushing elements and the other stack for popping elements. When we need to pop or peek at the front of the queue, we can transfer elements from the push stack to the pop stack to maintain the correct order.

Algorithm:

For the push operation, simply push the element onto the push stack.
For the pop or peek operation, if the pop stack is empty, transfer all elements from the push stack to the pop stack.
Perform the pop or peek operation on the pop stack.
For the empty operation, check if both push and pop stacks are empty.

Time Complexity:

Push: O(1)
Pop/Peek: Amortized O(1)
Empty: O(1)

Space Complexity:

O(n) where n is the number of elements in the queue.

Solutions

import java.util.Stack;

class MyQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public MyQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    public void push(int x) {
        pushStack.push(x);
    }

    public int pop() {
        if (popStack.isEmpty()) {
            transferElements();
        }
        return popStack.pop();
    }

    public int peek() {
        if (popStack.isEmpty()) {
            transferElements();
        }
        return popStack.peek();
    }

    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }

    private void transferElements() {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
    }
}