DSA — Deques

What is a Deque?

A double-ended queue that allows insertion and deletion at both ends.

from collections import deque

# Create deque
dq = deque()

# Operations
dq.append(1)      # Add to rear
dq.appendleft(0)  # Add to front
dq.pop()          # Remove from rear
dq.popleft()      # Remove from front

Operations

Operation	Time Complexity
append	O(1)
appendleft	O(1)
pop	O(1)
popleft	O(1)

Custom Deque

class Deque:
    def __init__(self):
        self.items = []
    
    def add_front(self, item):
        self.items.insert(0, item)
    
    def add_rear(self, item):
        self.items.append(item)
    
    def remove_front(self):
        if not self.is_empty():
            return self.items.pop(0)
    
    def remove_rear(self):
        if not self.is_empty():
            return self.items.pop()
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

Usage Examples

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

Mini Practice

1. Implement a deque
2. Check for palindromes
3. Use deque for sliding window
4. Implement a card game

Up Next

Continue with Hash Tables — hash table data structure.