Implementing a Deque Data Structure

This challenge asks you to implement a Deque (Double-Ended Queue) data structure in Python. Deques are versatile linear data structures that allow efficient insertion and deletion of elements from both the front and the rear. This is a fundamental data structure with applications in areas like breadth-first search algorithms, undo/redo functionality, and efficient queue/stack implementations.

Problem Description

Your task is to create a Python class that simulates the behavior of a Deque. The Deque should support the following core operations:

• __init__(self): Initializes an empty Deque.
• is_empty(self): Returns True if the Deque is empty, False otherwise.
• size(self): Returns the number of elements currently in the Deque.
• add_front(self, item): Adds an item to the front of the Deque.
• add_rear(self, item): Adds an item to the rear of the Deque.
• remove_front(self): Removes and returns the item from the front of the Deque. Raises an IndexError if the Deque is empty.
• remove_rear(self): Removes and returns the item from the rear of the Deque. Raises an IndexError if the Deque is empty.
• peek_front(self): Returns the item at the front of the Deque without removing it. Raises an IndexError if the Deque is empty.
• peek_rear(self): Returns the item at the rear of the Deque without removing it. Raises an IndexError if the Deque is empty.

You should aim for efficient implementations of these operations, ideally with O(1) time complexity for all of them, assuming the underlying storage mechanism supports it.

Examples

Example 1:

# Initialize a deque
my_deque = Deque()

# Add elements
my_deque.add_rear(10)
my_deque.add_rear(20)
my_deque.add_front(5)

# Current state: [5, 10, 20]
print(my_deque.size())       # Output: 3
print(my_deque.peek_front()) # Output: 5
print(my_deque.peek_rear())  # Output: 20

# Remove elements
print(my_deque.remove_front()) # Output: 5
print(my_deque.remove_rear())  # Output: 20

# Current state: [10]
print(my_deque.size())       # Output: 1
print(my_deque.is_empty())   # Output: False

Explanation: This example demonstrates basic insertion and removal from both ends, along with checking size and emptiness.

Example 2:

# Initialize a deque
my_deque = Deque()

# Attempt to remove from an empty deque
try:
    my_deque.remove_front()
except IndexError as e:
    print(e) # Output: Cannot remove from an empty deque

try:
    my_deque.peek_rear()
except IndexError as e:
    print(e) # Output: Cannot peek at an empty deque

# Add and then remove all elements
my_deque.add_front('A')
my_deque.add_front('B')
my_deque.remove_rear() # Removes 'A'
my_deque.remove_front() # Removes 'B'

print(my_deque.is_empty()) # Output: True

Explanation: This example shows the expected behavior when trying to perform operations on an empty deque, and also tests sequences of additions and removals that empty the deque.

Example 3:

# Initialize a deque
my_deque = Deque()

# Add multiple items of different types
my_deque.add_rear(1)
my_deque.add_front("hello")
my_deque.add_rear(True)
my_deque.add_front([1, 2])

# Current state: [[1, 2], 'hello', 1, True]
print(my_deque.size())       # Output: 4
print(my_deque.remove_front()) # Output: [1, 2]
print(my_deque.remove_rear())  # Output: True
print(my_deque.remove_front()) # Output: 'hello'
print(my_deque.remove_front()) # Output: 1

# Current state: []
print(my_deque.is_empty())   # Output: True

Explanation: This example demonstrates that the deque can hold elements of various data types and tests a more complex sequence of operations.

Constraints

• The Deque should be able to store any Python object.
• The remove_front, remove_rear, peek_front, and peek_rear methods must raise an IndexError with an appropriate message (e.g., "Cannot remove from an empty deque") when called on an empty Deque.
• Your implementation should aim for an average time complexity of O(1) for all provided operations.

Notes

• Consider using Python's built-in collections.deque as inspiration for the functionality, but you should implement your own version from scratch.
• Think about the underlying data structure you will use to implement the Deque. A standard Python list can work, but be mindful of its performance characteristics for front insertions/deletions. Alternatively, you might consider a linked list approach.
• For the error messages in IndexError, make them informative for debugging.