Implement Stack using Queues

Easy

DE Shaw

0 views

Topics:

StacksQueues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

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

Follow-up: Can you implement the stack using only one queue?

Try coding it in LeetCode

Implement Stack using Queues

Easy

DE Shaw

0 views

Topics:

StacksQueues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

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

Follow-up: Can you implement the stack using only one queue?

Try coding it in LeetCode

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:

Can I assume the elements to be pushed into the stack will be of a specific data type, such as integers?
What is the expected behavior if `pop` or `top` are called on an empty stack? Should I return null/None, throw an exception, or is it guaranteed these operations will never be called on an empty stack?
Are there any constraints on the number of queue(s) I can use?
Is there a limit to the number of operations (push, pop, top, empty) that will be performed?
Do I need to worry about thread safety or concurrent access to the stack?

Brute Force Solution

Approach

We want to mimic how a stack works, but we only have queues to use. The brute force approach involves cleverly using the queues to ensure that the last element added is always the first one removed, just like a stack.

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

When we want to add a new item to our 'stack', we actually put it into a temporary queue.
Then, we move all the elements from our main queue into the temporary queue, so the new item is at the front.
Finally, we swap the temporary queue with the main queue. Now, the new item is effectively at the top of our 'stack'.
When we want to remove the top item, we simply remove the first item from our main queue. This is because we arranged things so the newest item is always at the front.
If we want to see the top item without removing it, we just look at the first item in our main queue.
If we want to know if the 'stack' is empty, we check if the main queue is empty.

Code Implementation

from collections import deque

class StackUsingQueues:
    def __init__(self):
        self.main_queue = deque()
        self.temporary_queue = deque()

    def push(self, item):
        # Enqueue to temporary queue.
        self.temporary_queue.append(item)

        # Move all elements from main to temporary.
        while self.main_queue:
            self.temporary_queue.append(self.main_queue.popleft())

        # Swap main and temporary queues.
        self.main_queue, self.temporary_queue = self.temporary_queue, self.main_queue

    def pop(self):
        if not self.main_queue:
            return None
        # Removal from main queue gives stack behavior.
        return self.main_queue.popleft()

    def top(self):
        if not self.main_queue:
            return None
        # Returns the front element of the queue.
        return self.main_queue[0]

    def empty(self):
        # Stack is empty if main queue is empty.
        return len(self.main_queue) == 0

Big(O) Analysis

Time Complexity

O(n) – The push operation involves moving all elements from the main queue to a temporary queue, and then swapping the queues. In the worst case, the main queue contains n elements, requiring n enqueue and dequeue operations. The pop, peek, and empty operations on the queue each take constant time, O(1). Therefore, the push operation dominates the time complexity, resulting in O(n) for push and O(1) for all other operations. The overall time complexity is determined by the push operation in the worst-case scenario.

Space Complexity

O(N) – The algorithm uses a temporary queue to hold elements while rearranging them. In the worst-case scenario, when a new element is pushed onto the 'stack', all N elements from the main queue are moved to the temporary queue. Therefore, the temporary queue can grow up to the size of the number of elements currently in the 'stack', leading to an auxiliary space usage proportional to N. Swapping queues does not contribute to extra space, however the temporary queue contributes an auxiliary space of O(N).

Optimal Solution

Approach

We can simulate a stack using two queues. The trick is to ensure that when we add a new element, it becomes the first element in the queue, behaving like the top of the stack.

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

To 'push' an element onto our 'stack', first move all the elements from our primary queue to the secondary queue.
Then, add the new element to the now empty primary queue.
Finally, move all the elements back from the secondary queue to the primary queue. This ensures that the newly added element is at the front of the primary queue.
To 'pop' an element, simply remove and return the first element from the primary queue, which is the element that was most recently added.
The 'top' operation is similar to 'pop', but instead of removing the first element, we just look at it and return it.
The 'empty' operation just checks if the primary queue has any elements in it.

Code Implementation

class MyStack:

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

    def push(self, element_x: int) -> None:
        # Move all elements from queue_one to queue_two
        while self.queue_one:
            self.queue_two.append(self.queue_one.pop(0))

        # Add the new element to queue_one
        self.queue_one.append(element_x)

        # Move elements back from queue_two to queue_one
        while self.queue_two:
            self.queue_one.append(self.queue_two.pop(0))

    def pop(self) -> int:
        # queue_one maintains stack order, so remove head
        return self.queue_one.pop(0)

    def top(self) -> int:
        # Return the first element of queue_one
        return self.queue_one[0]

    def empty(self) -> bool:
        # Check if queue_one is empty
        return not self.queue_one

# Your MyStack object will be instantiated and called as such:
# my_stack = MyStack()
# my_stack.push(element_x)
# param_2 = my_stack.pop()
# param_3 = my_stack.top()
# param_4 = my_stack.empty()

Big(O) Analysis

Time Complexity

O(n) – The push operation involves moving all n elements from the primary queue to the secondary queue, adding the new element, and then moving the n elements back from the secondary queue to the primary queue. This means each push operation takes approximately 2n operations. The pop, top, and empty operations take constant time, O(1). Therefore, since push is the dominant operation, the overall complexity considering a single push operation is O(n).

Space Complexity

O(N) – The algorithm uses two queues. The primary queue stores up to N elements, where N is the number of elements ever pushed onto the stack. The secondary queue is used as temporary storage to rearrange elements. In the worst-case scenario, the secondary queue can also hold close to N elements while transferring items during the push operation. Therefore, the auxiliary space required is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Pushing null or undefined value onto the stack	Handle null or undefined push values by either disallowing them (throwing an error) or treating them as a valid data element like 0, depending on requirements.
Popping from an empty stack	Return null, undefined, throw an exception or return a status flag indicating an error based on the problem context.
Peeking (top) on an empty stack	Return null, undefined, throw an exception or return a status flag indicating an error based on the problem context.
Maximum number of push operations exceeding queue's capacity (if limited)	Ensure that if the underlying queue implementation has a size limit, the push operation can appropriately handle exceeding this limit, perhaps by resizing or throwing an exception.
Stack operations performed concurrently from multiple threads	The implementation should be thread-safe, using locks or other synchronization mechanisms to prevent race conditions when multiple threads access the queues simultaneously.
Extremely large values being pushed onto the stack (potential memory issues)	Consider the memory footprint of each element, and ensure that pushing very large values doesn't lead to memory exhaustion or integer overflow during operations like calculating queue sizes.
Queue implementation errors	If the underlying queue implementation has bugs (e.g., enqueue or dequeue fails intermittently), the stack implementation needs to be robust enough to handle such exceptions or inconsistencies from the queue.
Empty queue after multiple push and pop operations	Correctly reset any internal state or temporary queues to ensure consistent behaviour of push and pop after the stack empties.