Implement Stack using Queues

Easy

Implement Stack using Queues

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type will the stack hold? Can it be assumed to be integers, or should I handle generic types?
Are there any limitations on the number of elements that can be pushed onto the stack?
Is it acceptable to use more than two queues in my implementation?
Should my `pop` method return an error or throw an exception if the stack is empty, or is it acceptable to return a default value like `null` or `undefined`?
Is thread safety a concern for this stack implementation?

Brute Force Solution

Approach

We need to create a stack (like a pile of plates) using only queues (like lines where the first person in line is served first). The brute force approach essentially uses one queue to store the stack and, for every new element, shuffles all existing elements to make room for the new one at the 'top'.

Here's how the algorithm would work step-by-step:

When adding a new element to our 'stack', first put the new element into the queue.
Then, move all the existing elements from the queue one by one to the back of the same queue.
This makes the newest element appear at the front of the queue, which acts as the 'top' of our stack.
When we want to remove the 'top' element from the stack, we just remove the element at the front of the queue.
When we want to see what's at the 'top' of the stack, we just look at the element at the front of the queue.
If we need to check if the stack is empty, we just check if the queue is empty.

Code Implementation

from collections import deque

class StackUsingQueues:
    def __init__(self):
        self.queue = deque()

    def push(self, element):
        self.queue.append(element)
        # Rotate the queue to place the new element at the front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        if not self.is_empty():
            return self.queue.popleft()

    def top(self):
        # Return the front element
        if not self.is_empty():
            return self.queue[0]

    def is_empty(self):
        # Easy check to see if the stack is empty.
        return len(self.queue) == 0

Big(O) Analysis

Time Complexity

O(n) – The push operation involves adding the element to the queue (O(1)) and then rotating the existing n elements to the back of the queue, which takes O(n) time. The pop, peek, and empty operations only involve constant time operations on the queue (O(1)). Therefore, the push operation dominates, and since we are only analyzing the provided implementation where we perform the shuffling operations in every push operation, the overall time complexity of push is O(n). Other operations like pop, peek and empty are O(1). Since it is a Stack data structure, it doesn't make much sense to consider the runtime over a series of operations. Therefore, the complexity of the provided stack implementation is O(n), driven by the shuffle operations in the push method.

Space Complexity

O(1) – The provided solution uses a single queue. While the queue itself grows to store all N elements pushed onto the stack, it's considered the primary data structure rather than auxiliary space. The shuffling operation occurs in-place within the queue, meaning it doesn't create additional copies of the queue or significant temporary data structures. Therefore, the auxiliary space used is constant, consisting of a few variables for managing the queue's state, independent of the number of elements N. The space complexity is O(1).

Optimal Solution

Approach

The key idea is to use two queues to simulate the stack's behavior. We'll make one of the queue do most of the work so pushing items will be as simple as adding to a queue, while popping will require shifting elements between the queues to maintain the stack's last-in, first-out order.

Here's how the algorithm would work step-by-step:

When adding a new item, simply place it into the first queue.
When removing the top item, shift all elements, except the last one, from the first queue to the second queue.
Remove and return the last element from the first queue; this is the last-in element, or top of the stack.
Swap the names of the two queues so the second queue, which now contains the remaining elements, becomes the first queue for subsequent operations.
If we're checking the top item, we do almost the same thing as removal: shift all elements except the last one, get the last element, put all the shifted element back, and return the last element we got.

Code Implementation

class MyStack:

    def __init__(self):
        self.queue_one = []
        self.queue_two = []

    def push(self, item_to_push: int) -> None:
        self.queue_one.append(item_to_push)

    def pop(self) -> int:
        # Move all but the last element
        while len(self.queue_one) > 1:
            self.queue_two.append(self.queue_one.pop(0))

        # This is the top of the stack
        top_of_stack = self.queue_one.pop(0)

        self.queue_one, self.queue_two = self.queue_two, self.queue_one
        return top_of_stack

    def top(self) -> int:
        # Move all but the last element
        while len(self.queue_one) > 1:
            self.queue_two.append(self.queue_one.pop(0))
        
        # Get the top element
        top_of_stack = self.queue_one[0]

        self.queue_two.append(self.queue_one.pop(0))
        self.queue_one, self.queue_two = self.queue_two, self.queue_one

        # Return the top element
        return top_of_stack

    def empty(self) -> bool:
        # Stack is empty when queue is empty
        return len(self.queue_one) == 0

Big(O) Analysis

Time Complexity

O(n) – The push operation to the stack using queues takes O(1) time as it simply enqueues the element into the first queue. However, the pop and top operations require moving elements between the two queues. Specifically, for n elements, popping or peeking involves dequeuing n-1 elements from the first queue and enqueueing them into the second queue. This happens once for each pop or top. This means the pop and top operations each take O(n) time, since shifting elements dictates cost, hence the total cost scales linearly with n for these operations.

Space Complexity

O(N) – The algorithm uses two queues. In the worst-case scenario, where we push N elements onto the stack, both queues could potentially hold up to N elements between the push, pop, and top operations. Therefore, the auxiliary space required to store the queue elements grows linearly with the number of elements in the stack. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Calling pop or top on an empty stack	Raise an exception (e.g., EmptyStackException) or return a specific error value (like null) indicating an invalid operation.
Large number of push operations causing queue overflow (potential memory issue)	Ensure that the queue implementation can dynamically resize or has a maximum size with appropriate error handling to prevent memory exhaustion.
Negative or zero values being pushed onto the stack	The implementation should handle these values correctly as they are valid integers; if the problem dictates only positives, then validation must be added.
Very large integer values being pushed (potential overflow issues depending on language)	Use appropriate data types (e.g., long) to handle large integers or check for potential overflows before pushing.
Concurrent access from multiple threads	Implement thread safety using locks or synchronized queues to prevent race conditions.
Testing the stack after a mix of push, pop, and top operations	Create comprehensive test cases covering various sequences of operations to ensure correct behavior under different usage patterns.
Extreme edge cases where the queues are constantly re-arranged with push and pop actions	Test with scenarios that alternate between pushing and popping multiple times to ensure the algorithm maintains stack order
If queues use linked lists internally, confirm they are not susceptible to memory leaks after many push/pop cycles	In languages with manual memory management, ensure all allocated memory is properly deallocated during pop operations to prevent memory leaks.