Lecture 167:-Queue Using Stacks

Using two stacks, you can implement a queue. The basic idea is to use one stack for enqueueing elements and the other stack for dequeueing elements. Here's a Python implementation of a queue using two stacks:

pythonCopy code

class QueueUsingStacks: def __init__(self): self.stack_enqueue = [] # Stack for enqueueing self.stack_dequeue = [] # Stack for dequeueing def enqueue(self, item): self.stack_enqueue.append(item) def _transfer(self): while self.stack_enqueue: self.stack_dequeue.append(self.stack_enqueue.pop()) def dequeue(self): if not self.stack_dequeue: self._transfer() if self.stack_dequeue: return self.stack_dequeue.pop() def front(self): if not self.stack_dequeue: self._transfer() if self.stack_dequeue: return self.stack_dequeue[-1] def is_empty(self): return not (self.stack_enqueue or self.stack_dequeue) def size(self): return len(self.stack_enqueue) + len(self.stack_dequeue)

In this implementation, the enqueue operation simply adds elements to the stack_enqueue. For the dequeue operation, if stack_dequeue is empty, we transfer elements from stack_enqueue to stack_dequeue in reverse order. This way, the front element becomes the top of stack_dequeue, and we can perform a pop operation to dequeue the element.

Note that this implementation has a time complexity of O(1) for the enqueue operation and an amortized time complexity of O(1) for the dequeue operation. The _transfer method has a time complexity of O(n) in the worst case, but it's spread out over multiple enqueue operations, resulting in an amortized O(1) time complexity for each dequeue operation.

Keep in mind that while this implementation demonstrates the concept of implementing a queue using two stacks, it might not be the most efficient way to implement a queue in practice, especially if you're dealing with a large number of enqueue and dequeue operations. In real-world scenarios, using a linked list-based implementation or other optimized data structures might be more efficient.