Deque

A Deque (Double-Ended Queue) is a data structure that allows insert and delete from both ends: front and back.

Basic Operations

• add_front: Add an element at the front.
• add_rear: Add an element at the back.
• remove_front: Remove an element from the front.
• remove_rear: Remove an element from the back.

Implementation with Python collections.deque

from collections import deque

dq = deque()

# Add operations
dq.append(10)        # add rear: [10]
dq.append(20)        # add rear: [10, 20]
dq.appendleft(5)     # add front: [5, 10, 20]

# Remove operations
dq.pop()             # remove rear: [5, 10]
dq.popleft()         # remove front: [10]

print(dq)            # deque([10])

Class Implementation

class Deque:
    def __init__(self):
        self.items = deque()

    def add_front(self, item):
        self.items.appendleft(item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.popleft()

    def remove_rear(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items[0]

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items[-1]

Time Complexity

Deque Applications

1. Palindrome Checker: Check whether text reads the same both ways.
2. Sliding Window: Maximum/minimum within a window.
3. Queue and Stack implementation: Flexible for both.
4. Browser Navigation: Back and forward history.
5. Work Stealing Queue: Parallelism in schedulers.

Example: Palindrome Checker

from collections import deque

def is_palindrome(s):
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

Example: Sliding Window Maximum

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

A Deque is versatile for two-ended access. Now let's study the Hash Table for key-based data access.