algoadvance

Leetcode 232. Implement Queue using Stacks

Problem Statement

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, pop, peek, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You can only use standard stack operations (push to top, peek/pop from top, size, and is empty).
• You may assume that all operations are valid (for example, no calls to pop or peek will be made on an empty queue).

Clarifying Questions

1. Q: Are there any constraints on the values that can be pushed into the queue?
   • A: No, any integer values can be pushed into the queue.
2. Q: Can we use other data structures apart from two stacks for internal usage?
   • A: No, you are limited to using only two stacks.
3. Q: Is it necessary to handle exceptions for operations on an empty queue?
   • A: For this problem, you may assume that all operations are valid, so you do not need to handle exceptions.

Strategy

To implement a queue using two stacks, we can use two main stacks:

1. Input Stack (stack_in): Used to handle incoming elements via the push operation.
2. Output Stack (stack_out): Used to handle outgoing elements for pop and peek operations.

The main idea is to transfer elements from the input stack to the output stack when needed, ensuring that the order of elements in the output stack is such that the topmost element is the front of the queue.

Operations:

• Push: Always push the new element onto stack_in.
• Pop: If stack_out is empty, transfer all elements from stack_in to stack_out (reversing their order). Then, pop the top element from stack_out.
• Peek: Similar to pop, but instead of popping the top element from stack_out, simply return it.
• Empty: Return true if both stack_in and stack_out are empty.

Code

import java.util.Stack;

class MyQueue {
    private Stack<Integer> stack_in;
    private Stack<Integer> stack_out;

    public MyQueue() {
        stack_in = new Stack<>();
        stack_out = new Stack<>();
    }

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

    public int pop() {
        if (stack_out.isEmpty()) {
            while (!stack_in.isEmpty()) {
                stack_out.push(stack_in.pop());
            }
        }
        return stack_out.pop();
    }

    public int peek() {
        if (stack_out.isEmpty()) {
            while (!stack_in.isEmpty()) {
                stack_out.push(stack_in.pop());
            }
        }
        return stack_out.peek();
    }

    public boolean empty() {
        return stack_in.isEmpty() && stack_out.isEmpty();
    }
}

Time Complexity

• Push: (O(1)) as it just involves a simple push operation to the stack.
• Pop: (O(n)) in the worst case when stack_out is empty and elements need to be transferred from stack_in. However, amortized over a sequence of (m) operations, the complexity is (O(1)) per operation because each element is moved at most once.
• Peek: (O(n)) in the worst case due to the potential transfer from stack_in to stack_out, but similar to pop, the amortized complexity is (O(1)).
• Empty: (O(1)) as it only checks if both stacks are empty.

This implementation provides an efficient and correct solution to the problem of simulating a queue using two stacks.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?