Deque (Double-Ended Queue)

A deque (double-ended queue) is a linear data structure that allows insertion and deletion of elements from both ends (front and rear). It combines the functionality of both stacks and queues, providing maximum flexibility for element access patterns.

Features

Dual-ended access - Insert and remove from both front and rear in O(1) time
Stack and queue hybrid - Can function as both LIFO and FIFO data structure
Efficient operations - O(1) for all basic operations at both ends
Dynamic size - automatically grows and shrinks as needed
Memory efficient - uses doubly linked list for optimal memory usage
Type safe - generic implementation with type checking
Iterator support - can iterate in both directions (forward and reverse)
Utility operations - search, count, rotate, reverse, and copy functionality

Time Complexities

Operation	Time Complexity	Description
Add Front	O(1)	Insert element at front
Add Rear	O(1)	Insert element at rear
Remove Front	O(1)	Remove element from front
Remove Rear	O(1)	Remove element from rear
Front	O(1)	View front element
Rear	O(1)	View rear element
Search	O(n)	Find element position
Count	O(n)	Count occurrences
Clear	O(1)	Remove all elements
Copy	O(n)	Create shallow copy
Reverse	O(n)	Reverse deque order
Rotate	O(k)	Rotate by k positions
Size/Length	O(1)	Get number of elements

Space Complexity: O(n) where n is the number of elements

Basic Usage

Creating and Initializing

from algo.data_structs.stacks_queues.deque import Deque

# Create empty deque
deque = Deque()

# Check if empty
print(deque.is_empty())    # True
print(len(deque))          # 0
print(deque.size())        # 0

# Create with initial elements
deque = Deque([1, 2, 3, 4, 5])
print(len(deque))          # 5
print(deque.to_list())     # [1, 2, 3, 4, 5]

# Deque is generic - can specify type
int_deque = Deque[int]()
str_deque = Deque[str]()

Adding Elements

# Add to rear (right side)
deque = Deque()
deque.add_rear(1)
deque.add_rear(2)
deque.add_rear(3)

print(deque.to_list())     # [1, 2, 3]
print(deque.front())       # 1
print(deque.rear())        # 3

# Add to front (left side)
deque.add_front(0)
deque.add_front(-1)

print(deque.to_list())     # [-1, 0, 1, 2, 3]
print(deque.front())       # -1
print(deque.rear())        # 3

# Using convenience aliases
deque.append(4)            # Same as add_rear
deque.appendleft(-2)       # Same as add_front

print(deque.to_list())     # [-2, -1, 0, 1, 2, 3, 4]

Viewing Elements

# Peek at both ends without removing
front_element = deque.front()
rear_element = deque.rear()

print(f"Front: {front_element}")  # -2
print(f"Rear: {rear_element}")    # 4
print(len(deque))                 # Still same size

# Check if deque contains element
print(1 in deque)          # True
print(99 in deque)         # False

# Convert to list (front to rear order)
elements = deque.to_list()
print(elements)            # [-2, -1, 0, 1, 2, 3, 4]

Removing Elements

# Remove from front
front_removed = deque.remove_front()
print(front_removed)       # -2
print(deque.front())       # -1

# Remove from rear
rear_removed = deque.remove_rear()
print(rear_removed)        # 4
print(deque.rear())        # 3

# Using convenience aliases
left_removed = deque.popleft()   # Same as remove_front
right_removed = deque.pop()      # Same as remove_rear

print(left_removed)        # -1
print(right_removed)       # 3
print(deque.to_list())     # [0, 1, 2]

Clearing the Deque

# Add some elements
deque.extend([5, 6, 7, 8, 9])
print(len(deque))          # 8

# Clear all elements
deque.clear()
print(len(deque))          # 0
print(deque.is_empty())    # True

Advanced Operations

Extending with Iterables

deque = Deque()

# Extend to rear (normal order)
deque.extend([1, 2, 3])
print(deque.to_list())     # [1, 2, 3]

# Extend to front (reversed order)
deque.extendleft([4, 5])
# Elements added one by one: first 4, then 5
print(deque.to_list())     # [5, 4, 1, 2, 3]

# Extend with different iterables
deque.extend((6, 7))       # Tuple
deque.extendleft("ab")     # String (characters)
print(deque.to_list())     # ['b', 'a', 5, 4, 1, 2, 3, 6, 7]

Rotation Operations

deque = Deque([1, 2, 3, 4, 5])
print(f"Original: {deque.to_list()}")

# Rotate right (positive steps)
deque.rotate(2)
print(f"Rotate right 2: {deque.to_list()}")  # [4, 5, 1, 2, 3]

# Rotate left (negative steps)
deque.rotate(-1)
print(f"Rotate left 1: {deque.to_list()}")   # [5, 1, 2, 3, 4]

# Full rotation (same as original)
deque.rotate(5)  # Rotate by length
print(f"Full rotation: {deque.to_list()}")   # [5, 1, 2, 3, 4] (unchanged)

Reversing the Deque

deque = Deque([1, 2, 3, 4, 5])
print(f"Original: {deque.to_list()}")

# Reverse in place
deque.reverse()
print(f"Reversed: {deque.to_list()}")        # [5, 4, 3, 2, 1]
print(f"Front: {deque.front()}")             # 5
print(f"Rear: {deque.rear()}")               # 1

Search and Count Operations

Finding Elements

deque = Deque([1, 2, 3, 2, 4, 2])

# Search returns position from front (0-based)
print(deque.search(1))     # 0 (front element)
print(deque.search(2))     # 1 (first occurrence of 2)
print(deque.search(3))     # 2 (third position from front)
print(deque.search(4))     # 4 (fifth position from front)
print(deque.search(99))    # -1 (not found)

# Check membership
print(2 in deque)          # True
print(99 in deque)         # False

Counting Elements

# Count occurrences of elements
print(deque.count(2))      # 3 (appears 3 times)
print(deque.count(1))      # 1 (appears once)
print(deque.count(99))     # 0 (not present)

# Count all elements
total_elements = len(deque)
print(total_elements)      # 6

Iteration and Traversal

deque = Deque(['apple', 'banana', 'cherry', 'date'])

# Iterate from front to rear
print("Deque contents (front to rear):")
for item in deque:
    print(item)  # apple, banana, cherry, date

# Convert to list for processing
items = list(deque)
print(items)               # ['apple', 'banana', 'cherry', 'date']

# Reverse iteration (rear to front)
print("Deque contents (rear to front):")
for item in deque.reversed_iter():
    print(item)  # date, cherry, banana, apple

# Enumerate with position
for i, item in enumerate(deque):
    print(f"Position {i}: {item}")

Working with Different Types

String Elements

words = Deque()
words.append("hello")
words.append("world")
words.appendleft("python")

print(words.front())       # "python"
print(words.rear())        # "world"
print("world" in words)    # True
print(words.count("hello")) # 1

Numeric Elements

numbers = Deque([1, 2, 3, 4, 5])
numbers.append(3.14)
numbers.appendleft(42)

print(numbers.front())     # 42
print(numbers.rear())      # 3.14
print(3.14 in numbers)     # True
print(len(numbers))        # 7

Mixed Types

mixed = Deque()
mixed.append("string")
mixed.append(42)
mixed.appendleft([1, 2, 3])   # Lists can be stored
mixed.appendleft(True)

print(mixed.front())       # True
print(mixed.rear())        # 42
print(42 in mixed)         # True
print(len(mixed))          # 4

Custom Objects

class Task:
    def __init__(self, name: str, priority: int):
        self.name = name
        self.priority = priority

    def __eq__(self, other):
        return isinstance(other, Task) and self.name == other.name

    def __str__(self):
        return f"Task({self.name}, priority={self.priority})"

tasks = Deque()
task1 = Task("Write code", 1)
task2 = Task("Test code", 2)
task3 = Task("Deploy", 3)

tasks.append(task1)
tasks.append(task2)
tasks.appendleft(task3)

print(tasks.front())       # Task(Deploy, priority=3)
print(tasks.rear())        # Task(Test code, priority=2)
print(task1 in tasks)      # True
print(len(tasks))          # 3

Deque Manipulation

Copying Deques

original = Deque([1, 2, 3, 4, 5])

# Create a copy
copy_deque = original.copy()

# Verify they have same contents
print(copy_deque.to_list() == original.to_list())  # True
print(len(copy_deque) == len(original))             # True

# Verify they're independent
original.append(6)
print(len(original))       # 6
print(len(copy_deque))     # 5 (unchanged)

copy_deque.appendleft(99)
print(99 in original)      # False
print(99 in copy_deque)    # True

String Representation

# Empty deque
empty_deque = Deque()
print(str(empty_deque))    # Deque([])

# Non-empty deque
deque = Deque([1, 2, 3])
print(str(deque))          # Deque([1 <-> 2 <-> 3])

# Detailed representation for debugging
print(repr(deque))         # Deque(size=3, front=1, rear=3)

Error Handling

deque = Deque()

# Safe operations on empty deque
print(deque.is_empty())    # True
print(len(deque))          # 0
print(deque.search(42))    # -1
print(deque.count(42))     # 0
print(42 in deque)         # False

# Operations that raise errors on empty deque
try:
    deque.remove_front()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot remove from empty deque

try:
    deque.remove_rear()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot peek rear of empty deque

try:
    deque.front()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot peek front of empty deque

try:
    deque.rear()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot peek rear of empty deque

# Alias methods also raise appropriate errors
try:
    deque.pop()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot remove from empty deque

try:
    deque.popleft()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot remove from empty deque

Common Patterns

Using as Stack (LIFO)

# Stack behavior using rear end
stack = Deque()

# Push elements (to rear)
stack.append(1)
stack.append(2)
stack.append(3)
print(f"Stack: {stack.to_list()}")  # [1, 2, 3]

# Pop elements (from rear) - LIFO order
while not stack.is_empty():
    item = stack.pop()
    print(f"Popped: {item}")  # 3, 2, 1

Using as Queue (FIFO)

# Queue behavior using both ends
queue = Deque()

# Enqueue elements (to rear)
queue.append(1)
queue.append(2)
queue.append(3)
print(f"Queue: {queue.to_list()}")  # [1, 2, 3]

# Dequeue elements (from front) - FIFO order
while not queue.is_empty():
    item = queue.popleft()
    print(f"Dequeued: {item}")  # 1, 2, 3

Sliding Window Operations

def sliding_window_example():
    """Example of sliding window using deque rotation."""
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    window_size = 3

    window = Deque()
    results = []

    # Process each element
    for i, value in enumerate(data):
        window.append(value)

        # Maintain window size
        if len(window) > window_size:
            window.popleft()

        # Process complete windows
        if len(window) == window_size:
            window_sum = sum(window.to_list())
            results.append(window_sum)
            print(f"Window {list(window.to_list())}: sum = {window_sum}")

    return results

sliding_window_example()
# Output shows sum of each sliding window of size 3

Buffer Management

class CircularBuffer:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.deque = Deque()

    def add(self, item):
        """Add item to buffer, removing oldest if at capacity."""
        if len(self.deque) >= self.capacity:
            removed = self.deque.popleft()
            print(f"Buffer full, removed: {removed}")

        self.deque.append(item)
        print(f"Added: {item}, buffer: {self.deque.to_list()}")

    def get_all(self):
        """Get all items in buffer order."""
        return self.deque.to_list()

# Usage
buffer = CircularBuffer(capacity=3)
for i in range(6):
    buffer.add(f"item_{i}")

print(f"Final buffer: {buffer.get_all()}")

Practical Applications

Palindrome Checker

from algo.data_structs.stacks_queues.deque import is_palindrome

# Test palindrome checking
test_strings = [
    "racecar",
    "hello", 
    "A man a plan a canal Panama",
    "race a car",
    "Madam",
    "12321",
    "12345"
]

for text in test_strings:
    result = is_palindrome(text)
    print(f"'{text}' is palindrome: {result}")

# Custom palindrome checker showing deque operations
def check_palindrome_manual(text: str) -> bool:
    """Manual palindrome check showing deque operations."""
    deque = Deque()

    # Add only alphanumeric characters (lowercase)
    for char in text.lower():
        if char.isalnum():
            deque.append(char)

    print(f"Cleaned text in deque: {deque.to_list()}")

    # Compare from both ends
    while len(deque) > 1:
        front_char = deque.popleft()
        rear_char = deque.pop()
        print(f"Comparing '{front_char}' and '{rear_char}'")

        if front_char != rear_char:
            return False

    return True

print("\nManual palindrome check:")
result = check_palindrome_manual("A man a plan a canal Panama")
print(f"Result: {result}")

Sliding Window Maximum

from algo.data_structs.stacks_queues.deque import sliding_window_maximum

# Find maximum in sliding windows
arrays = [
    ([1, 3, -1, -3, 5, 3, 6, 7], 3),
    ([1, 1, 1, 1, 1], 2),
    ([9, 8, 7, 6, 5, 4, 3, 2, 1], 3),
    ([1, 2, 3, 4, 5], 1),
]

for arr, k in arrays:
    result = sliding_window_maximum(arr, k)
    print(f"Array: {arr}")
    print(f"Window size: {k}")
    print(f"Sliding maximums: {result}")
    print()

# Manual implementation showing deque usage
def sliding_max_manual(arr, k):
    """Manual sliding window maximum showing deque operations."""
    if not arr or k <= 0:
        return []

    indices_deque = Deque()  # Store indices of useful elements
    result = []

    for i, num in enumerate(arr):
        print(f"\nProcessing element {num} at index {i}")

        # Remove indices outside current window
        while not indices_deque.is_empty() and indices_deque.front() <= i - k:
            removed_idx = indices_deque.popleft()
            print(f"  Removed index {removed_idx} (outside window)")

        # Remove indices with smaller values (they can't be maximum)
        while not indices_deque.is_empty() and arr[indices_deque.rear()] <= num:
            removed_idx = indices_deque.pop()
            print(f"  Removed index {removed_idx} (smaller value {arr[removed_idx]})")

        indices_deque.append(i)
        print(f"  Added index {i}")
        print(f"  Deque indices: {indices_deque.to_list()}")

        # Add result when we have a complete window
        if i >= k - 1:
            max_idx = indices_deque.front()
            max_val = arr[max_idx]
            result.append(max_val)
            print(f"  Window [{i-k+1}:{i+1}] maximum: {max_val}")

    return result

print("Manual sliding window maximum:")
test_arr = [1, 3, -1, -3, 5, 3, 6, 7]
manual_result = sliding_max_manual(test_arr, 3)
print(f"Final result: {manual_result}")

Undo/Redo System

class UndoRedoSystem:
    def __init__(self, max_history: int = 10):
        self.max_history = max_history
        self.history = Deque()
        self.current_state = None

    def execute_action(self, action: str, state):
        """Execute an action and save state for undo."""
        if self.current_state is not None:
            # Save current state to history
            self.history.append((action, self.current_state))

            # Limit history size
            if len(self.history) > self.max_history:
                self.history.popleft()

        self.current_state = state
        print(f"Executed: {action} -> {state}")

    def undo(self):
        """Undo the last action."""
        if not self.history.is_empty():
            action, previous_state = self.history.pop()
            print(f"Undoing: {action}")
            self.current_state = previous_state
            return previous_state
        else:
            print("Nothing to undo")
            return None

    def can_undo(self) -> bool:
        """Check if undo is possible."""
        return not self.history.is_empty()

    def get_history(self):
        """Get current history."""
        return [action for action, _ in self.history.to_list()]

# Usage
editor = UndoRedoSystem(max_history=5)

editor.execute_action("type 'Hello'", "Hello")
editor.execute_action("type ' World'", "Hello World")
editor.execute_action("delete 6 chars", "Hello")
editor.execute_action("type ' Python'", "Hello Python")

print(f"Current state: {editor.current_state}")
print(f"History: {editor.get_history()}")

# Undo operations
while editor.can_undo():
    state = editor.undo()
    print(f"State after undo: {state}")

Task Scheduler with Priority

class PriorityTaskScheduler:
    def __init__(self):
        self.high_priority = Deque()
        self.normal_priority = Deque()
        self.low_priority = Deque()

    def add_task(self, task: str, priority: str = "normal"):
        """Add task with specified priority."""
        if priority == "high":
            self.high_priority.append(task)
        elif priority == "low":
            self.low_priority.append(task)
        else:
            self.normal_priority.append(task)

        print(f"Added {priority} priority task: {task}")

    def add_urgent_task(self, task: str):
        """Add urgent task to front of high priority queue."""
        self.high_priority.appendleft(task)
        print(f"Added URGENT task to front: {task}")

    def process_next_task(self):
        """Process next task based on priority."""
        # Check high priority first
        if not self.high_priority.is_empty():
            task = self.high_priority.popleft()
            print(f"Processing HIGH priority: {task}")
            return task

        # Then normal priority
        if not self.normal_priority.is_empty():
            task = self.normal_priority.popleft()
            print(f"Processing NORMAL priority: {task}")
            return task

        # Finally low priority
        if not self.low_priority.is_empty():
            task = self.low_priority.popleft()
            print(f"Processing LOW priority: {task}")
            return task

        print("No tasks to process")
        return None

    def show_status(self):
        """Show current task queues."""
        print(f"High priority tasks: {self.high_priority.to_list()}")
        print(f"Normal priority tasks: {self.normal_priority.to_list()}")
        print(f"Low priority tasks: {self.low_priority.to_list()}")

# Usage
scheduler = PriorityTaskScheduler()

# Add various tasks
scheduler.add_task("Send email", "normal")
scheduler.add_task("Backup database", "low")
scheduler.add_task("Fix critical bug", "high")
scheduler.add_task("Update documentation", "normal")
scheduler.add_urgent_task("Server is down!")

scheduler.show_status()

# Process all tasks
print("\nProcessing tasks:")
while True:
    task = scheduler.process_next_task()
    if task is None:
        break

Web Browser History

class BrowserHistory:
    def __init__(self, max_history: int = 50):
        self.max_history = max_history
        self.history = Deque()
        self.current_page = None

    def visit(self, url: str):
        """Visit a new page."""
        if self.current_page:
            self.history.append(self.current_page)

            # Limit history size
            if len(self.history) > self.max_history:
                self.history.popleft()

        self.current_page = url
        print(f"Visited: {url}")

    def back(self):
        """Go back to previous page."""
        if not self.history.is_empty():
            previous = self.history.pop()
            self.current_page = previous
            print(f"Back to: {previous}")
            return previous
        else:
            print("No previous page")
            return None

    def forward_to_recent(self):
        """Go to most recent page in history."""
        if not self.history.is_empty():
            recent = self.history.pop()
            if self.current_page:
                self.history.append(self.current_page)
            self.current_page = recent
            print(f"Forward to: {recent}")
            return recent
        return None

    def get_recent_history(self, count: int = 5):
        """Get recent history."""
        history_list = self.history.to_list()
        return history_list[-count:] if len(history_list) >= count else history_list

# Usage
browser = BrowserHistory(max_history=10)

# Simulate browsing
pages = [
    "google.com",
    "github.com", 
    "stackoverflow.com",
    "python.org",
    "docs.python.org",
    "realpython.com"
]

for page in pages:
    browser.visit(page)

print(f"Current page: {browser.current_page}")
print(f"Recent history: {browser.get_recent_history(3)}")

# Navigate back
browser.back()
browser.back()
print(f"After going back: {browser.current_page}")

Use Cases

When to Use Deques

Good for:

Sliding window algorithms
Implementing both stacks and queues
Palindrome checking
Undo/redo functionality
Browser history management
Task scheduling with priorities
Circular buffers
Breadth-first search with backtracking
Dynamic programming with space optimization

Examples:

# Sliding window maximum
sliding_deque = Deque()
sliding_deque.append(window_element)

# Stack and queue combined
dual_ended = Deque()
dual_ended.append(item)      # Add to rear
dual_ended.appendleft(item)  # Add to front
dual_ended.pop()             # Remove from rear
dual_ended.popleft()         # Remove from front

# Palindrome checking
palindrome_deque = Deque()
palindrome_deque.extend(text)

# Undo/redo system
history_deque = Deque()
history_deque.append(action)

When NOT to Use Deques

Avoid for:

Random access to middle elements (use arrays/lists)
Frequent searches in large datasets (use hash tables)
Sorted data operations (use heaps or balanced trees)
Simple single-ended operations (use specialized stack/queue)

Better alternatives:

# For random access, use list
random_access = [1, 2, 3, 4, 5]
print(random_access[2])  # Direct access to index 2

# For sorted operations, use heapq
import heapq
priority_queue = []
heapq.heappush(priority_queue, (priority, item))

# For fast searches, use set or dict
fast_lookup = {1, 2, 3, 4, 5}
print(3 in fast_lookup)  # O(1) lookup

# For simple stack, use list
simple_stack = []
simple_stack.append(item)  # Push
simple_stack.pop()         # Pop

Performance Characteristics

Time Complexity Analysis

Front/Rear operations: O(1) - constant time for both ends
Search operations: O(n) - linear time traversal
Rotation: O(k) where k is rotation steps
Memory allocation: O(1) per element (doubly linked list)
Space overhead: Moderate (two pointers per node)

Memory Efficiency

# Deque uses doubly linked list internally
# Memory per element: data + two pointers (next, prev)
# No pre-allocation of fixed arrays
# Memory grows/shrinks dynamically

deque = Deque()
print(f"Empty deque memory efficient: {deque.is_empty()}")

# Memory usage scales linearly with elements
for i in range(1000):
    deque.append(i)
# Only allocates memory for actual elements

Comparison with Other Data Structures

Operation	Deque	List	Stack	Queue	Array
Add Front	O(1)	O(n)	N/A	N/A	O(n)
Add Rear	O(1)	O(1)	O(1)	O(1)	O(1)*
Remove Front	O(1)	O(n)	N/A	O(1)	O(n)
Remove Rear	O(1)	O(1)	O(1)	N/A	O(1)
Random Access	O(n)	O(1)	O(n)	O(n)	O(1)
Memory Overhead	Medium	Low	Low	Low	Low
Use Case	Both Ends	Random Access	LIFO	FIFO	Indexed

*Array add rear may require reallocation

Advanced Features

Rotation Patterns

# Demonstrate rotation for different use cases
def rotation_examples():
    # Circular shift for encryption
    message = Deque(list("HELLO"))
    print(f"Original: {''.join(message.to_list())}")

    message.rotate(3)  # Caesar cipher shift
    print(f"Shifted: {''.join(message.to_list())}")

    # Round-robin scheduling
    processes = Deque(["P1", "P2", "P3", "P4"])
    print("\nRound-robin scheduling:")

    for time_slice in range(8):
        current = processes.front()
        print(f"Time {time_slice}: Running {current}")
        processes.rotate(1)  # Next process

rotation_examples()

Custom Iteration

def custom_iteration_examples():
    deque = Deque([1, 2, 3, 4, 5])

    # Forward iteration
    print("Forward:", [x for x in deque])

    # Reverse iteration
    print("Reverse:", [x for x in deque.reversed_iter()])

    # Custom iteration patterns
    def zigzag_iter(dq):
        """Iterate alternating from front and rear."""
        temp_deque = dq.copy()
        from_front = True

        while not temp_deque.is_empty():
            if from_front:
                yield temp_deque.popleft()
            else:
                yield temp_deque.pop()
            from_front = not from_front

    print("Zigzag:", list(zigzag_iter(deque)))

custom_iteration_examples()

API Reference

Deque (Double-Ended Queue) Implementation

A deque is a double-ended queue that allows insertion and deletion at both ends. It's a generalization of both stacks and queues, providing efficient operations at both the front and rear.

Key Features:

Add/remove elements at both front and rear in O(1) time
Can be used as both stack and queue
Supports iteration in both directions
Dynamic size allocation

Common Use Cases:

Sliding window problems
Palindrome checking
Implementing undo/redo functionality
Browser history management
A* search algorithm (maintaining open/closed lists)

Time Complexities:

Add/remove front: O(1)
Add/remove rear: O(1)
Access front/rear: O(1)
Size: O(1)
Search: O(n)

Space Complexity: O(n)

`Deque(iterable=None)`

Bases: Generic[T]

A deque implementation using a doubly linked list as the underlying data structure.

This implementation provides efficient O(1) operations at both ends by maintaining references to both head and tail of the doubly linked list.

Initialize a deque.

Parameters:

Name	Type	Description	Default
`iterable`	`Optional[Iterable[T]]`	Optional iterable to initialize the deque with. Elements are added in order from front to rear.	`None`

`contains(value)`

Check if a value exists in the deque.

`iter()`

Return an iterator over the deque elements from front to rear.

`len()`

Return the number of elements in the deque.

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the deque.

`add_front(element)`

Add an element to the front of the deque.

Time Complexity: O(1)

Parameters:

Name	Type	Description	Default
`element`	`T`	Element to add to the front	required

`add_rear(element)`

Add an element to the rear of the deque.

Time Complexity: O(1)

Parameters:

Name	Type	Description	Default
`element`	`T`	Element to add to the rear	required

`append(element)`

Alias for add_rear - add element to the rear.

`appendleft(element)`

Alias for add_front - add element to the front.

`clear()`

Remove all elements from the deque.

Time Complexity: O(1)

`copy()`

Create a shallow copy of the deque.

Time Complexity: O(n)

Returns:

Type	Description
`Deque[T]`	A new Deque with the same elements

`count(target)`

Count the number of occurrences of an item in the deque.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`target`	`T`	Item to count	required

Returns:

Type	Description
`int`	Number of occurrences

`extend(iterable)`

Add all elements from an iterable to the rear of the deque.

Time Complexity: O(k) where k is the number of elements

Parameters:

Name	Type	Description	Default
`iterable`		Iterable containing elements to add	required

`extendleft(iterable)`

Add all elements from an iterable to the front of the deque.

Time Complexity: O(k) where k is the number of elements

Parameters:

Name	Type	Description	Default
`iterable`		Iterable containing elements to add	required

Note

Elements are added one by one to the front, so the final order will be reversed compared to the original iterable.

`front()`

Return the front element without removing it.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The front element of the deque

Raises:

Type	Description
`IndexError`	If the deque is empty

`is_empty()`

Check if the deque is empty.

Time Complexity: O(1)

Returns:

Type	Description
`bool`	True if the deque is empty, False otherwise

`pop()`

Alias for remove_rear - remove element from the rear.

`popleft()`

Alias for remove_front - remove element from the front.

`rear()`

Return the rear element without removing it.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The rear element of the deque

Raises:

Type	Description
`IndexError`	If the deque is empty

`remove_front()`

Remove and return the front element from the deque.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The front element of the deque

Raises:

Type	Description
`IndexError`	If the deque is empty

`remove_rear()`

Remove and return the rear element from the deque.

Time Complexity: O(1)

Returns:

Type	Description
`T`	The rear element of the deque

Raises:

Type	Description
`IndexError`	If the deque is empty

`reverse()`

Reverse the deque in place.

Time Complexity: O(n)

Note

After reversal, the front element becomes the rear element.

`reversed_iter()`

Return an iterator over the deque elements from rear to front.

Returns:

Type	Description
`Iterator[T]`	Iterator that goes from rear to front

`rotate(steps=1)`

Rotate the deque n steps to the right.

Time Complexity: O(min(steps, n)) where n is the size

Parameters:

Name	Type	Description	Default
`steps`	`int`	Number of steps to rotate right (negative for left rotation)	`1`

Note

Positive steps rotate right (rear elements move to front) Negative steps rotate left (front elements move to rear)

`search(target)`

Search for an item in the deque and return its position from the front.

Time Complexity: O(n)

Parameters:

Name	Type	Description	Default
`target`	`T`	Item to search for	required

Returns:

Type	Description
`int`	Position from front (0-based), or -1 if not found

`size()`

Get the number of elements in the deque.

Time Complexity: O(1)

Returns:

Type	Description
`int`	The number of elements in the deque

`to_list()`

Convert the deque to a Python list.

Time Complexity: O(n)

Returns:

Type	Description
`list[T]`	A Python list with elements from front to rear

`is_palindrome(text)`

Check if a string is a palindrome using deque.

Time Complexity: O(n) Space Complexity: O(n)

Parameters:

Name	Type	Description	Default
`text`	`str`	String to check	required

Returns:

Type	Description
`bool`	True if string is a palindrome, False otherwise

`sliding_window_maximum(array, window_size)`

Find maximum in each sliding window of size k using deque.

Time Complexity: O(n) Space Complexity: O(k)

Parameters:

Name	Type	Description	Default
`array`	`list[int]`	Input array	required
`window_size`	`int`	Window size	required

Returns:

Type	Description
`list[int]`	List of maximum values in each window

Deque (Double-Ended Queue)

Features

Time Complexities

Basic Usage

Creating and Initializing

Adding Elements

Viewing Elements

Removing Elements

Clearing the Deque

Advanced Operations

Extending with Iterables

Rotation Operations

Reversing the Deque

Search and Count Operations

Finding Elements

Counting Elements

Iteration and Traversal

Working with Different Types

String Elements

Numeric Elements

Mixed Types

Custom Objects

Deque Manipulation

Copying Deques

String Representation

Error Handling

Common Patterns

Using as Stack (LIFO)

Using as Queue (FIFO)

Sliding Window Operations

Buffer Management

Practical Applications

Palindrome Checker

Sliding Window Maximum

Undo/Redo System

Task Scheduler with Priority

Web Browser History

Use Cases

When to Use Deques

When NOT to Use Deques

Performance Characteristics

Time Complexity Analysis

Memory Efficiency

Comparison with Other Data Structures

Advanced Features

Rotation Patterns

Custom Iteration

API Reference

Deque(iterable=None)

__contains__(value)

__iter__()

__len__()

__repr__()

__str__()

add_front(element)

add_rear(element)

append(element)

appendleft(element)

clear()

copy()

count(target)

extend(iterable)

extendleft(iterable)

front()

is_empty()

pop()

popleft()

rear()

remove_front()

remove_rear()

reverse()

reversed_iter()

rotate(steps=1)

search(target)

size()

to_list()

is_palindrome(text)

sliding_window_maximum(array, window_size)

`Deque(iterable=None)`

`contains(value)`

`iter()`

`len()`

`repr()`

`str()`

`add_front(element)`

`add_rear(element)`

`append(element)`

`appendleft(element)`

`clear()`

`copy()`

`count(target)`

`extend(iterable)`

`extendleft(iterable)`

`front()`

`is_empty()`

`pop()`

`popleft()`

`rear()`

`remove_front()`

`remove_rear()`

`reverse()`

`reversed_iter()`

`rotate(steps=1)`

`search(target)`

`size()`

`to_list()`

`is_palindrome(text)`

`sliding_window_maximum(array, window_size)`