In this Python program, we will implement a queue data structure using two stacks. The idea is to simulate the behavior of a queue by using two stacks, one for enqueueing elements and another for dequeueing elements. This approach showcases how stacks can be utilized to achieve the functionality of a queue.
Problem Statement
Implement a queue data structure using two stacks to support enqueue and dequeue operations efficiently using Python.
Python Program to Implement Queues using Stack
class QueueUsingStack:
def __init__(self):
self.stack_enqueue = [] # For enqueueing elements
self.stack_dequeue = [] # For dequeueing elements
def enqueue(self, item):
self.stack_enqueue.append(item)
def dequeue(self):
if not self.stack_dequeue:
while self.stack_enqueue:
self.stack_dequeue.append(self.stack_enqueue.pop())
if self.stack_dequeue:
return self.stack_dequeue.pop()
else:
return None # Queue is empty
def is_empty(self):
return len(self.stack_enqueue) == 0 and len(self.stack_dequeue) == 0
def size(self):
return len(self.stack_enqueue) + len(self.stack_dequeue)
# Example usage
queue = QueueUsingStack()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Dequeued:", queue.dequeue()) # Output: Dequeued: 10
print("Dequeued:", queue.dequeue()) # Output: Dequeued: 20
queue.enqueue(40)
print("Dequeued:", queue.dequeue()) # Output: Dequeued: 30
print("Is empty:", queue.is_empty()) # Output: Is empty: False
print("Queue size:", queue.size()) # Output: Queue size: 1
How it Works
- Two stacks are used:
stack_enqueuefor enqueueing elements andstack_dequeuefor dequeueing elements. - Enqueue operation simply appends the element to the
stack_enqueue. - Dequeue operation involves transferring elements from
stack_enqueuetostack_dequeueonly ifstack_dequeueis empty. Then, the element on top ofstack_dequeueis popped and returned. - The
is_emptymethod checks if both stacks are empty. - The
sizemethod returns the combined size of both stacks.
Input/Output
