Lecture 168:-Stacks Using Queue

You can implement a stack using two queues. The basic idea is to use one queue for push (or enqueue) operations and another queue for pop (or dequeue) operations. Here's a Python implementation of a stack using two queues:

pythonCopy code

from collections import deque class StackUsingQueues: def __init__(self): self.queue1 = deque() # Queue for push operations self.queue2 = deque() # Queue for pop operations def push(self, item): # Enqueue the item into queue1 self.queue1.append(item) def pop(self): if not self.queue1: return None # Stack is empty # Move all but the last element from queue1 to queue2 while len(self.queue1) > 1: self.queue2.append(self.queue1.popleft()) # Pop the last element from queue1 (equivalent to popping from stack) item = self.queue1.popleft() # Swap the names of queue1 and queue2 self.queue1, self.queue2 = self.queue2, self.queue1 return item def top(self): if not self.queue1: return None # Stack is empty # Move all but the last element from queue1 to queue2 while len(self.queue1) > 1: self.queue2.append(self.queue1.popleft()) # Get the last element from queue1 (equivalent to top of stack) item = self.queue1[0] # Move the element back to queue1 self.queue2.append(self.queue1.popleft()) # Swap the names of queue1 and queue2 self.queue1, self.queue2 = self.queue2, self.queue1 return item def is_empty(self): return not self.queue1 def size(self): return len(self.queue1)

In this implementation, the push operation enqueues an item into queue1. For the pop operation, we move all elements except the last one from queue1 to queue2. This makes the last element in queue1 (which corresponds to the top of the stack) available for popping. After popping, we swap the names of queue1 and queue2 to maintain the order.

The top operation is similar to the pop operation, but it leaves the last element in queue1 so that we can retrieve the top element without actually removing it.

Just like with the previous example, keep in mind that while this implementation demonstrates the concept of implementing a stack using two queues, it might not be the most efficient way to implement a stack in practice, especially if you're dealing with a large number of push and pop operations.