Deque

Overview

A Deque (double-ended queue) is a data structure that allows insertion and deletion at both ends. The UCX DSA package provides two deque implementations:

Deque: Fixed-capacity static deque
DynamicDeque: Automatically resizing deque

Both implementations use circular indexing internally for efficient space utilization.

Deque (Static)

A static deque with a fixed capacity that supports operations at both the front and back.

Creating a Deque

from dsa.deque import Deque

# Create deque with default capacity of 10
deque = Deque()
print(deque.capacity())  # 10
print(len(deque))        # 0

Key Methods

Operations at the Front

append_left / push_front
pop_left / pop_front
peek_left / front

Add an element to the front of the deque:

deque = Deque()
deque.append_left(1)
deque.append_left(2)
deque.append_left(3)
print(deque.to_list())  # [3, 2, 1]

# push_front is a synonym for append_left
deque.push_front(4)
print(deque.to_list())  # [4, 3, 2, 1]

# Raises Exception if deque is full
full_deque = Deque(capacity=2)
full_deque.append_left(1)
full_deque.append_left(2)
try:
    full_deque.append_left(3)
except Exception as e:
    print(e)  # Deque Full

Time Complexity: O(1)

Remove and return the front element:

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

front = deque.pop_left()
print(front)  # 1
print(deque.to_list())  # [2, 3, 4, 5]

# pop_front is a synonym for pop_left
front = deque.pop_front()
print(front)  # 2

# Raises Exception if deque is empty
empty_deque = Deque()
try:
    empty_deque.pop_left()
except Exception as e:
    print(e)  # Empty Deque

Time Complexity: O(1)

View the front element without removing it:

deque = Deque.from_list([10, 20, 30])

print(deque.peek_left())  # 10
print(len(deque))         # 3 (unchanged)

# front is a synonym for peek_left
print(deque.front())  # 10

# Raises Exception if deque is empty
empty_deque = Deque()
try:
    empty_deque.peek_left()
except Exception as e:
    print(e)  # Empty deque

Time Complexity: O(1)

Operations at the Back

append_right / push_back
pop_right / pop_back
peek_right / back

Add an element to the back of the deque:

deque = Deque()
deque.append_right(1)
deque.append_right(2)
deque.append_right(3)
print(deque.to_list())  # [1, 2, 3]

# push_back is a synonym for append_right
deque.push_back(4)
print(deque.to_list())  # [1, 2, 3, 4]

# Raises Exception if deque is full
full_deque = Deque(capacity=2)
full_deque.append_right(1)
full_deque.append_right(2)
try:
    full_deque.append_right(3)
except Exception as e:
    print(e)  # Deque Full

Time Complexity: O(1)

Remove and return the back element:

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

back = deque.pop_right()
print(back)  # 5
print(deque.to_list())  # [1, 2, 3, 4]

# pop_back is a synonym for pop_right
back = deque.pop_back()
print(back)  # 4

# Raises Exception if deque is empty
empty_deque = Deque()
try:
    empty_deque.pop_right()
except Exception as e:
    print(e)  # Empty Deque

Time Complexity: O(1)

View the back element without removing it:

deque = Deque.from_list([10, 20, 30])

print(deque.peek_right())  # 30
print(len(deque))          # 3 (unchanged)

# back is a synonym for peek_right
print(deque.back())  # 30

# Raises Exception if deque is empty
empty_deque = Deque()
try:
    empty_deque.peek_right()
except Exception as e:
    print(e)  # Empty deque

Time Complexity: O(1)

Utility Methods

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

# Check if empty
print(deque.is_empty())  # False

# Get number of elements
print(len(deque))  # 5

# Get capacity
print(deque.capacity())  # 10

# Convert to Python list
print(deque.to_list())  # [1, 2, 3, 4, 5]

# String representation
print(deque)  # [1, 2, 3, 4, 5] Count: 5 Capacity: 10

Circular Indexing

The Deque uses circular indexing internally for efficient space utilization:

deque = Deque(capacity=5)

# Add from both ends
deque.append_right(3)
deque.append_left(2)
deque.append_left(1)
deque.append_right(4)
deque.append_right(5)

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

# Remove from both ends
deque.pop_left()   # 1
deque.pop_right()  # 5

# Add more elements (reuses space)
deque.append_left(0)
deque.append_right(6)

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

DynamicDeque

A dynamic deque that automatically adjusts its capacity. It doubles when full and halves when utilization drops below 25%.

Creating a DynamicDeque

from dsa.deque import DynamicDeque

# Create with default capacity
deque = DynamicDeque()

# Create from list
deque = DynamicDeque.from_list([1, 2, 3])

Automatic Resizing

The DynamicDeque grows and shrinks automatically:

deque = DynamicDeque(capacity=2)
print(f"Initial capacity: {deque.capacity()}")  # 2

# Add elements - capacity doubles when full
deque.append_right(1)
deque.append_right(2)
print(f"After 2 elements: {deque.capacity()}")  # 2

deque.append_right(3)  # Triggers growth
print(f"After 3 elements: {deque.capacity()}")  # 4

deque.append_left(0)  # Add to front
deque.append_right(4)  # Triggers growth again
print(f"After 5 elements: {deque.capacity()}")  # 8

# Shrinks when count <= 1/4 of capacity
for i in range(4):
    deque.pop_left()
print(f"After removals: {deque.capacity()}")  # 4 (shrunk from 8)

Growth Strategy:

Grows: capacity × 2 when count >= capacity
Shrinks: capacity ÷ 2 when count <= capacity ÷ 4
Minimum capacity: 10
Elements are reorganized during resize to maintain order

Key Methods

DynamicDeque supports all the same methods as Deque:

deque = DynamicDeque()

# Append to both ends without capacity concerns
for i in range(50):
    deque.append_right(i)
for i in range(50):
    deque.append_left(-i)

print(len(deque))  # 100

# Pop from both ends
while not deque.is_empty():
    if len(deque) % 2 == 0:
        deque.pop_left()
    else:
        deque.pop_right()

Time Complexity:

append_left(), append_right(): O(1) amortized
pop_left(), pop_right(): O(1) amortized
peek_left(), peek_right(): O(1)

Use Cases

Palindrome Checker
Sliding Window Maximum
Undo/Redo System
Work Stealing Queue

Check if a sequence is a palindrome:

from dsa.deque import Deque

def is_palindrome(text):
    """Check if text is a palindrome using deque."""
    # Remove spaces and convert to lowercase
    text = text.replace(" ", "").lower()
    deque = Deque.from_list(list(text))
    
    while len(deque) > 1:
        if deque.pop_left() != deque.pop_right():
            return False
    
    return True

print(is_palindrome("racecar"))      # True
print(is_palindrome("hello"))        # False
print(is_palindrome("A man a plan a canal Panama"))  # True

Find maximum in all sliding windows:

from dsa.deque import DynamicDeque

def sliding_window_max(arr, k):
    """Find maximum in each window of size k."""
    deque = DynamicDeque()
    result = []
    
    for i in range(len(arr)):
        # Remove elements outside window
        while not deque.is_empty() and deque.front() <= i - k:
            deque.pop_left()
        
        # Remove smaller elements (they won't be max)
        while not deque.is_empty() and arr[deque.back()] <= arr[i]:
            deque.pop_right()
        
        deque.append_right(i)
        
        # Add to result once we have full window
        if i >= k - 1:
            result.append(arr[deque.front()])
    
    return result

arr = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(arr, 3))  # [3, 3, 5, 5, 6, 7]

Implement undo/redo with efficient access to both ends:

from dsa.deque import DynamicDeque

class UndoRedoManager:
    def __init__(self, max_history=50):
        self.actions = DynamicDeque()
        self.current_index = -1
        self.max_history = max_history
    
    def do_action(self, action):
        # Remove any actions after current position
        while len(self.actions) > self.current_index + 1:
            self.actions.pop_right()
        
        # Add new action
        self.actions.append_right(action)
        self.current_index += 1
        
        # Maintain max history
        if len(self.actions) > self.max_history:
            self.actions.pop_left()
            self.current_index -= 1
    
    def undo(self):
        if self.current_index >= 0:
            self.current_index -= 1
            return True
        return False
    
    def redo(self):
        if self.current_index < len(self.actions) - 1:
            self.current_index += 1
            return True
        return False

manager = UndoRedoManager()
manager.do_action("Type 'Hello'")
manager.do_action("Type ' World'")
manager.undo()  # Back to 'Hello'
manager.redo()  # Forward to 'Hello World'

Implement a work-stealing deque for parallel processing:

from dsa.deque import DynamicDeque

class WorkStealingQueue:
    def __init__(self):
        self.tasks = DynamicDeque()
    
    def add_task(self, task):
        """Add task to own end (right)."""
        self.tasks.append_right(task)
    
    def get_own_task(self):
        """Get task from own end (right) - LIFO for cache locality."""
        if not self.tasks.is_empty():
            return self.tasks.pop_right()
        return None
    
    def steal_task(self):
        """Steal task from other end (left) - FIFO."""
        if not self.tasks.is_empty():
            return self.tasks.pop_left()
        return None
    
    def has_tasks(self):
        return not self.tasks.is_empty()

# Worker thread
worker = WorkStealingQueue()
worker.add_task("Task 1")
worker.add_task("Task 2")
worker.add_task("Task 3")

# Process own tasks (LIFO)
print(worker.get_own_task())  # Task 3

# Another worker steals (FIFO)
print(worker.steal_task())    # Task 1

Method Aliases

Deque provides convenient aliases for operations:

Operation	Primary Method	Alias
Add to front	`append_left()`	`push_front()`
Add to back	`append_right()`	`push_back()`
Remove from front	`pop_left()`	`pop_front()`
Remove from back	`pop_right()`	`pop_back()`
View front	`peek_left()`	`front()`
View back	`peek_right()`	`back()`

deque = Deque()

# These are equivalent
deque.append_left(1)
deque.push_front(1)

# These are equivalent
deque.pop_right()
deque.pop_back()

# These are equivalent
deque.peek_left()
deque.front()

Comparison: Deque vs DynamicDeque

Feature	Deque	DynamicDeque
Capacity	Fixed	Dynamic
Memory	Predictable	Variable
Performance	Constant O(1)	Amortized O(1)
Use Case	Known max size	Unknown size
Exception on Full	Yes	No (auto-grows)
Shrinking	No	Yes (below 25%)

When to use Deque: Use when you know the maximum size in advance and want predictable memory usage.When to use DynamicDeque: Use when size varies significantly and you need automatic memory management.

Equality Comparison

Both deque types support equality comparison based on contents:

from dsa.deque import Deque, DynamicDeque

deque1 = Deque.from_list([1, 2, 3])
deque2 = DynamicDeque.from_list([1, 2, 3])
deque3 = Deque.from_list([1, 2, 4])

print(deque1 == deque2)  # True (same contents)
print(deque1 == deque3)  # False (different contents)

Best Practices

Check Before Pop

Always check if the deque is empty before popping:

if not deque.is_empty():
    value = deque.pop_left()

Use Peek for Inspection

Use peek_left() or peek_right() to inspect without removing:

if not deque.is_empty():
    front = deque.peek_left()
    back = deque.peek_right()

Choose Operations Wisely

Use appropriate end for your use case:

Stack behavior: use one end
Queue behavior: use both ends
Deque behavior: leverage both ends

Handle Exceptions

Wrap operations in try-except for robust code:

try:
    deque.append_right(value)
except Exception:
    # Handle full deque

Deque vs Stack vs Queue

Deque
Stack
Queue

Use Deque when:

You need access to both ends
You want to implement both stack and queue operations
You need flexibility in adding/removing elements

Example: Palindrome checking, sliding window algorithms

Get Started

Linear Data Structures

Tree Data Structures

Hash-Based Structures

Graphs

Algorithms

Utilities

Overview

Deque (Static)

Creating a Deque

Key Methods

Operations at the Front

Operations at the Back

Utility Methods

Circular Indexing

DynamicDeque

Creating a DynamicDeque

Automatic Resizing

Key Methods

Use Cases

Method Aliases

Comparison: Deque vs DynamicDeque

Equality Comparison

Best Practices

Check Before Pop

Use Peek for Inspection

Choose Operations Wisely

Handle Exceptions

Deque vs Stack vs Queue

Build docs developers (and LLMs) love

Get Started

Linear Data Structures

Tree Data Structures

Hash-Based Structures

Graphs

Algorithms

Utilities

​Overview

​Deque (Static)

​Creating a Deque

​Key Methods

​Operations at the Front

​Operations at the Back

​Utility Methods

​Circular Indexing

​DynamicDeque

​Creating a DynamicDeque

​Automatic Resizing

​Key Methods

​Use Cases

​Method Aliases

​Comparison: Deque vs DynamicDeque

​Equality Comparison

​Best Practices

Check Before Pop

Use Peek for Inspection

Choose Operations Wisely

Handle Exceptions

​Deque vs Stack vs Queue

Build docs developers (and LLMs) love

Overview

Deque (Static)

Creating a Deque

Key Methods

Operations at the Front

Operations at the Back

Utility Methods

Circular Indexing

DynamicDeque

Creating a DynamicDeque

Automatic Resizing

Key Methods

Use Cases

Method Aliases

Comparison: Deque vs DynamicDeque

Equality Comparison

Best Practices

Deque vs Stack vs Queue