Implement Queue using Stacks | Leetcode 232 | Using 2 stacks

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, peek, pop, and empty).

Here’s the [Problem Link] to begin with.

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 must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Intuition & Approach

Why Use Two Stacks?

A queue is FIFO (first-in, first-out); a stack is LIFO (last-in, first-out). By cleverly combining two stacks, you can reverse the LIFO order to achieve the desired FIFO behavior.

How Does This Work?

• in_stack receives new elements (acts like the back of the queue).
• out_stack gives elements in “queue order” (the front of the queue).

When you need to pop or peek:

• If out_stack is empty, dump all elements from in_stack into out_stack (reversing their order).
• If out_stack is not empty, use it directly.

This “delayed reversal” ensures each element is reversed only once, keeping operations efficient on average (amortized O(1) time).

Code Implementation

class MyQueue:
    def __init__(self):
        # Two stacks: in_stack (for push), out_stack (for pop/peek)
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        # Add to in_stack (end of queue)
        self.in_stack.append(x)

    def pop(self) -> int:
        # Pop from out_stack (front of queue)
        self.peek()  # Ensure out_stack has the current items
        return self.out_stack.pop()

    def peek(self) -> int:
        # Get the front element
        if not self.out_stack:
            # Transfer all from in_stack to out_stack if needed, reversing order
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

    def empty(self) -> bool:
        # Queue is empty only if both stacks are empty
        return not self.in_stack and not self.out_stack

Code Explanation

• push(x): Always adds new elements to in_stack, which is simple and O(1).
• pop(): If out_stack is empty, transfer all elements from in_stack (which reverses their order). This lets you pop the oldest element, just like a queue.
• peek(): Ensures the next element to pop is on top of out_stack; if not, does the same transferring as in pop(), then returns the top of out_stack.
• empty(): The queue is empty if BOTH stacks have no elements left.

Time and Space Complexity

• push: O(1)
• pop: Amortized O(1) (costly transfers only when out_stack is empty, and each element is moved at most once)
• peek: Amortized O(1)
• empty: O(1)
• Space: O(n), where n = number of queue elements

In simple words:
Normal operations are constant time; only occasional transfers take extra time, but spread across all operations they average out to “fast enough” (O(1) per operation).

Conclusion

Implementing a queue using two stacks is an interview classic for a reason. It elegantly demonstrates both the difference between LIFO and FIFO structures and how you can achieve one using the other. Practice this pattern, then try similar challenges like stack using queues to deeply strengthen your data structure skills!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.