Introduction to Queues
A queue is a linear facts structure that follows the First In First Out (FIFO) precept. This approach that the primary detail added to the queue will be the primary one to be removed. Queues are used in numerous packages including task scheduling, dealing with requests in web servers, and breadth-first search in graphs.
Key Operations of a Queue
- Enqueue: Add an object to the rear of the queue.
- Dequeue: Remove and go back the item from the front of the queue.
- Is Empty: Check if the queue is empty.
Implementing a Queue with Two Stacks
To enforce a queue the usage of two stacks, we can make use of the following approach:
- Stack1: This stack is used for enqueue operations.
- Stack2: This stack is used for dequeue operations.
How It Works
- Enqueue: When we enqueue an item, we really push it onto Stack1.
- Dequeue: When we dequeue an item, we need to make certain that Stack2 has the elements in the right order. If Stack2 is empty, we pop all items from Stack1 and push them onto Stack2. This reverses the order of the objects, allowing us to pop from Stack2 for a correct FIFO behavior.
Detailed Code Implementation
Below is the complete code for a Queue class implemented using stacks together with reasons for each element.
class Stack:
"""A simple stack class for internal use in the Queue class."""
def __init__(self):
"""Initialize an empty stack."""
self.items = []
def push(self, item):
"""Add an item to the top of the stack."""
self.items.append(item)
def pop(self):
"""Remove and return the item from the top of the stack.
Returns:
The item removed from the top of the stack.
Raises:
IndexError: If the stack is empty.
"""
if self.is_empty():
raise IndexError("Pop from empty stack.")
return self.items.pop()
def is_empty(self):
"""Check if the stack is empty.
Returns:
True if the stack is empty, False otherwise.
"""
return len(self.items) == 0
def top(self):
"""Return the top item of the stack without removing it.
Returns:
The top item of the stack.
Raises:
IndexError: If the stack is empty.
"""
if self.is_empty():
raise IndexError("Peek from empty stack.")
return self.items[-1]
def size(self):
"""Return the number of items in the stack."""
return len(self.items)
class QueueUsingStacks:
"""A queue implementation using two stacks."""
def __init__(self):
"""Initialize two empty stacks."""
self.stack1 = Stack()
self.stack2 = Stack()
def enqueue(self, item):
"""Add an item to the rear of the queue.
Args:
item: The item to be added to the queue.
"""
self.stack1.push(item)
print(f"Enqueued {item} to queue.")
def dequeue(self):
"""Remove and return the item from the front of the queue.
Returns:
The item removed from the front of the queue.
Raises:
IndexError: If the queue is empty.
"""
if self.is_empty():
raise IndexError("Dequeue from empty queue.")
# If stack2 is empty, we need to move elements from stack1 to stack2
if self.stack2.is_empty():
while not self.stack1.is_empty():
item = self.stack1.pop()
self.stack2.push(item)
return self.stack2.pop()
def is_empty(self):
"""Check if the queue is empty.
Returns:
True if the queue is empty, False otherwise.
"""
return self.stack1.is_empty() and self.stack2.is_empty()
def size(self):
"""Return the number of items in the queue.
Returns:
The total size of the queue.
"""
return self.stack1.size() + self.stack2.size()
def display(self):
"""Display the current items in the queue."""
if not self.is_empty():
# Show items in queue order
temp_stack = Stack()
while not self.stack2.is_empty():
item = self.stack2.pop()
temp_stack.push(item)
print(item, end=" ")
while not temp_stack.is_empty():
item = temp_stack.pop()
self.stack2.push(item) # Restore items back to stack2
while not self.stack1.is_empty():
print(self.stack1.items[-1], end=" ")
print()
else:
print("Queue is empty.")Explanation of the Code
Stack Class:
A easy stack elegance is defined for internal use in the queue implementation.
The stack magnificence has strategies to push, pop, check if it’s far empty, get the top object, and return the scale.
QueueUsingStacks Class:
The QueueUsingStacks magnificence initializes stacks: stack1 for enqueue operations and stack2 for dequeue operations.
Enqueue Method:
The enqueue(item) method adds an object to the stop of the queue by pushing it onto stack1.
Dequeue Method:
The dequeue() method tests if the queue is empty. If stack2 is empty, it movements all objects from stack1 to stack2, reversing their order. It then pops an item from stack2, which represents the the front of the queue.
Is Empty Method:
The is_empty() method tests if each stacks are empty, indicating the queue is empty.
Size Method:
The length() method returns the full variety of gadgets within the queue by summing the sizes of both stacks.
Display Method:
The show() approach indicates the contemporary contents of the queue. It briefly reverses stack2 to keep the right order even as showing and then restores the stack.
Usage Example
Below is an example of how to use the QueueUsingStacks class:
if __name__ == "__main__":
queue = QueueUsingStacks()
# Enqueue items
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
# Display current queue
print("Current Queue:")
queue.display()
# Dequeue items
print("Dequeued:", queue.dequeue())
print("Dequeued:", queue.dequeue())
# Display current queue
print("Current Queue after two dequeues:")
queue.display()
# Checking if the queue is empty
if queue.is_empty():
print("Queue is empty.")
else:
print("Queue is not empty.")
# Enqueue another item
queue.enqueue(4)
# Display current queue
print("Current Queue after enqueueing another item:")
queue.display()
# Dequeue all items
while not queue.is_empty():
print("Dequeued:", queue.dequeue())
# Final check if queue is empty
if queue.is_empty():
print("Queue is empty now.")Explanation of the Example
- Queue Creation: An instance of the
QueueUsingStacksclass is created. - Enqueue Items: Several integers are enqueued into the queue.
- Display Current Queue: The contemporary country of the queue is displayed.
- Dequeue Items: Items are dequeued from the queue, and the country of the queue is displayed afterward.
- Check if Empty: The program assessments if the queue is empty and prints the end result.
- Further Operations: Another object is enqueued, and the queue is displayed again.
Finally, all objects are dequeued, and a very last check confirms that the queue is empty.
Implementing a queue the use of stacks is a extremely good exercising to apprehend the interplay between exclusive data systems. This implementation efficiently handles the queue operations while preserving the proper order of factors.
Further Enhancements
You can enhance this queue implementation by using:
- Adding exception coping with for invalid operations.
- Implementing a way to clear the queue.
- Creating a most size limit for the queue to keep away from immoderate memory use.
