Technical Interview Question: Implement a Stack using Queues

Write a program to implement a stack using standard queue operations (enqueue and dequeue). Your implementation should support the following stack operations: push, pop, top, and empty.

Answer

We can implement a stack using two queues. The basic idea is to use one queue for storing the elements of the stack and perform the push and pop operations efficiently.

Here's the step-by-step detailed explanation:

class StackUsingQueues:
    def __init__(self):
        self.queue1 = []
        self.queue2 = []

    def push(self, val):
        self.queue1.append(val)

    def pop(self):
        if not self.queue1:
            return None
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.pop(0))
        element = self.queue1.pop(0)
        self.queue1, self.queue2 = self.queue2, self.queue1
        return element

    def top(self):
        if not self.queue1:
            return None
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.pop(0))
        element = self.queue1.pop(0)
        self.queue2.append(element)
        self.queue1, self.queue2 = self.queue2, self.queue1
        return element

    def empty(self):
        return len(self.queue1) == 0

In the above implementation:

• We use two queues (queue1 and queue2) to mimic a stack's behavior.
• The push(val) method simply appends the value to queue1.
• The pop() method moves all elements from queue1 to queue2 except the last one, which is removed and returned.
• The top() method is similar to pop() but it also puts the top element back after retrieval.
• The empty() method checks if the stack is empty.

This implementation allows us to use the queue's standard operations to perform stack operations efficiently. It has a time complexity of O(1) for push, pop, top, and empty operations.