Implement a queue data structure using two stacks in Python

Implementing a queue using two stacks is a common interview question that demonstrates understanding of stack operations and how they can be used to simulate a queue. Here's how you can implement a queue using two stacks in Python:

class QueueUsingStacks:

    def __init__(self):

        self.stack1 = []

        self.stack2 = []

    def enqueue(self, item):

        # Push item into stack1

        self.stack1.append(item)

    def dequeue(self):

        if not self.stack2:

            # Transfer all elements from stack1 to stack2

            while self.stack1:

                self.stack2.append(self.stack1.pop())

        

        # Pop from stack2 if it's not empty

        if self.stack2:

            return self.stack2.pop()

        else:

            raise IndexError("dequeue from empty queue")

    def peek(self):

        if not self.stack2:

            # Transfer all elements from stack1 to stack2

            while self.stack1:

                self.stack2.append(self.stack1.pop())

        

        # Peek from stack2 if it's not empty

        if self.stack2:

            return self.stack2[-1]

        else:

            return None

    def is_empty(self):

        return not self.stack1 and not self.stack2

    def size(self):

        return len(self.stack1) + len(self.stack2)

Explanation:

1. Initialization (__init__ method):

   • Initializes two empty lists self.stack1 and self.stack2. self.stack1 will be used for enqueue operations, and self.stack2 will be used for dequeue operations.

2. Enqueue operation (enqueue method):

   • Adds an item to the end of self.stack1 using the append method.

3. Dequeue operation (dequeue method):

   • Checks if self.stack2 is empty.
   • If self.stack2 is empty, transfers all elements from self.stack1 to self.stack2 by popping from self.stack1 and pushing onto self.stack2.
   • Finally, pops and returns the top element from self.stack2.

4. Peek operation (peek method):

   • Similar to dequeue, checks if self.stack2 is empty and transfers elements from self.stack1 to self.stack2 if needed.
   • Returns the top element of self.stack2 without removing it.

5. is_empty method:

   • Checks if both self.stack1 and self.stack2 are empty and returns True if they are, False otherwise.

6. size method:

   • Returns the total number of elements in the queue, which is the sum of the lengths of self.stack1 and self.stack2.

Example Usage:

# Create a new queue using stacks

queue = QueueUsingStacks()

# Enqueue some elements

queue.enqueue(1)

queue.enqueue(2)

queue.enqueue(3)

# Dequeue an element

print("Dequeued element:", queue.dequeue())  # Output: 1

# Peek at the front of the queue

print("Front of the queue:", queue.peek())  # Output: 2

# Check if the queue is empty

print("Is the queue empty?", queue.is_empty())  # Output: False

# Get the size of the queue

print("Size of the queue:", queue.size())  # Output: 2

In this implementation, the enqueue operation simply appends elements to self.stack1. The dequeue and peek operations first check if self.stack2 is empty; if it is, they transfer elements from self.stack1 to self.stack2 to ensure FIFO (first-in-first-out) order is maintained. This approach ensures that enqueueing and dequeueing operations are efficient, each operating in $O(1)$ amortized time complexity.