algoadvance

Implement a stack using queues. You should implement the following operations of a stack using standard queue operations:

1. push(x) – Push element x onto stack.
2. pop() – Removes the element on top of the stack.
3. top() – Get the top element.
4. empty() – Return whether the stack is empty.

Notes:

• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
• You can only use standard operations of a queue which means only enqueue, dequeue, size, and isEmpty operations are allowed.

Clarifying Questions

Before proceeding, let’s clarify a few things:

1. Can we use built-in Python queue (like collections.deque or queue.Queue) to implement the solution?
2. Do we have any constraints on the number or size of operations we can perform?
3. Should the operations be optimized for time complexity or are we aiming for a simpler implementation?

Let’s assume standard constraints and built-in Python queue usage is allowed unless specified otherwise.

Strategy

We can maintain two queues (q1 and q2) to manage the stack operations effectively:

1. Push Operation (push(x)):
   • Enqueue the element x to q2.
   • Dequeue all elements of q1 and enqueue them to q2.
   • Swap the names of q1 and q2.
2. Pop Operation (pop()):
   • Simply dequeue from q1 (as it holds the current stack elements in the correct order).
3. Top Operation (top()):
   • Return the front element of q1 (peek without dequeuing).
4. Empty Operation (empty()):
   • Check if q1 is empty (using its isEmpty method).

This will ensure that all stack operations are simulated using queue operations.

Code

from collections import deque

class MyStack:
    
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return not self.q1

Time Complexity

• Push Operation: O(n) - Since we move all elements from q1 to q2 and then swap.
• Pop Operation: O(1) - Direct dequeuing from q1.
• Top Operation: O(1) - Direct access to the front element of q1.
• Empty Operation: O(1) - Checking if q1 is empty.

This approach ensures that our stack operations are correctly managed using two queues, while keeping most operations efficient.

Try our interview co-pilot at AlgoAdvance.com

• 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?