Implement Queue using Stacks

Easy

Amazon

4 views

Topics:

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).

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.

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.

For example:

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

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.

Implement Queue using Stacks

Easy

Amazon

4 views

Topics:

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).

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.

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.

For example:

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

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.

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 elements in the queue be? Are we limited to integers or could they be other types?
Are there any constraints on the number of operations (push, pop, peek, empty) that will be performed on the queue?
Should I handle the case where `pop` or `peek` are called on an empty queue? If so, should I return a specific value (e.g., null, -1) or throw an exception?
Can I use built-in stack data structures from the language I'm using, or should I implement my own stack?
Does 'standard stack operations' preclude the use of a third stack as temporary storage during `pop` or `peek` operations?

Brute Force Solution

Approach

We want to simulate a waiting line (queue) using only two stacks. The straightforward but less efficient way is to move all elements from one stack to the other whenever we want to add or remove something from our queue.

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

When we want to add something to the queue, we need to ensure the newest element ends up at the bottom of the stack that represents the queue (like the back of the line).
To do this, move everything from the first stack to the second stack.
Then, place the new item onto the now-empty first stack.
Finally, move all the items from the second stack back to the first stack. Now, the new item is at the bottom, and everything else is in the correct order.
When we want to remove something from the queue, we simply remove the top item from the first stack, as it's the next item in line.
If we are peeking at the front item of the queue, return the first item from the stack.

Code Implementation

class MyQueue:

    def __init__(self):
        self.stack_one = []
        self.stack_two = []

    def push(self, element):
        # Moving elements to stack two to make space for new element
        while self.stack_one:
            self.stack_two.append(self.stack_one.pop())

        self.stack_one.append(element)

        # Moving back elements to stack one
        while self.stack_two:
            self.stack_one.append(self.stack_two.pop())

    def pop(self):
        # Stack one represents our queue, so pop the top
        if self.stack_one:
            return self.stack_one.pop()
        return None

    def peek(self):
        # Return top of stack one to simulate queue
        if self.stack_one:
            return self.stack_one[-1]
        return None

    def empty(self):
        # Queue empty when stack one is empty
        return not self.stack_one

Big(O) Analysis

Time Complexity

O(n) – The enqueue operation moves all n elements from stack1 to stack2, pushes the new element onto stack1, and then moves all n elements from stack2 back to stack1. This means 2n pushes and pops in total. The dequeue and peek operations simply pop or peek from stack1, taking constant time. Therefore, the enqueue operation takes O(n) time, while dequeue and peek take O(1) time. Since enqueue is the dominant operation when considering a sequence of operations, the overall time complexity for a series of enqueue and dequeue operations is O(n) for n enqueue operations.

Space Complexity

O(N) – The algorithm utilizes two stacks. In the worst-case scenario, where we enqueue N elements, we might need to temporarily move all N elements from one stack to the other. This results in the second stack holding up to N elements as auxiliary space during the enqueue operation. Therefore, the space complexity is proportional to the number of elements in the queue.

Optimal Solution

Approach

We'll use two stacks to simulate a queue. The main idea is that one stack handles adding new elements, and the other handles removing them, transferring elements only when necessary to maintain queue order.

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

For adding a new element, simply push it onto the first stack.
For removing an element, first check if the second stack is empty.
If the second stack is empty, move all the elements from the first stack to the second stack. This reverses the order, preparing elements for queue-like removal.
Then, remove the top element from the second stack (this is the element that has been in the queue the longest).
If we need to see the next element without removing it, we follow the same process as removing, moving from the first to second stack if the second one is empty, and then looking at the top of the second stack. The element is not actually removed.

Code Implementation

class MyQueue:

    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, element):
        self.input_stack.append(element)

    def pop(self):
        # Transfer elements if output stack is empty.
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

        if self.output_stack:
            return self.output_stack.pop()
        else:
            return None

    def peek(self):
        # Transfer elements only when output stack is empty.
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

        if self.output_stack:
            return self.output_stack[-1]
        else:
            return None

    def empty(self):
        # Queue is empty when both stacks are empty.
        return not self.input_stack and not self.output_stack

Big(O) Analysis

Time Complexity

O(1) amortized – The push operation onto the first stack (enqueue) takes O(1) time. The peek and pop operations (dequeue) may require moving all elements from the first stack to the second. While a single pop/peek can take O(n) in the worst case when the second stack is empty and the first stack has n elements, this O(n) operation occurs only once for every n push operations. Therefore, across a sequence of n enqueue and dequeue operations, the amortized time complexity for each operation is O(1).

Space Complexity

O(N) – The solution uses two stacks. In the worst-case scenario, all N elements will be pushed onto the first stack. Then, when dequeue is called and the second stack is empty, all N elements from the first stack are moved to the second stack. Therefore, the algorithm requires auxiliary space to store up to N elements, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Multiple pop operations when queue is empty.	Raise an exception or return null/error code to indicate an invalid operation on an empty queue.
Large number of push operations to test memory usage.	The stack operations should scale with available memory, but monitoring is important for resource leaks.
Simultaneous push and pop operations from multiple threads (concurrency).	Implement thread-safe stacks using locks or atomic operations to ensure correct behavior.
Pushing null values into the queue.	Decide if null values are allowed. If not, reject them and throw an exception, otherwise handle them as a valid value.
Check the correct order when pushing and immediately popping one element.	Verify that the single pushed element is returned by the immediate pop operation.
Interleaving push and pop operations to test FIFO behavior	Ensure that pop always returns the earliest pushed element even with frequent pushes and pops.
Negative or zero sized inputs	The size operation should always return a non-negative integer, and the queue operations should work correctly even when the queue is logically empty (size is zero).
Integer overflow with a huge number of elements pushed to the queue.	Consider the maximum possible stack size and handle integer overflow exceptions if the number of elements exceeds the limit.