Dequeue Operation in DSA Python

Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway where people can enter or exit from either the front door or the back door freely.

front -> [ ] -> [ ] -> [ ] -> back
↑front pointer
↑back pointer

Dry Run Walkthrough

Input: dequeue with elements 10 -> 20 -> 30, remove from front, then remove from back

Goal: Remove one element from the front and one from the back, showing how the dequeue changes

Step 1: remove element from front (10)

front -> [20] -> [30] -> back

Why: Removing from front shifts the front pointer to the next element

Step 2: remove element from back (30)

front -> [20] -> back

Why: Removing from back moves the back pointer one element backward, removing last element

Result:

front -> [20] -> back

Annotated Code

DSA Python

class Dequeue:
    def __init__(self):
        self.items = []

    def add_front(self, item):
        self.items.insert(0, item)  # add item at front

    def add_back(self, item):
        self.items.append(item)  # add item at back

    def remove_front(self):
        if not self.items:
            return None  # empty dequeue
        return self.items.pop(0)  # remove front item

    def remove_back(self):
        if not self.items:
            return None  # empty dequeue
        return self.items.pop()  # remove back item

    def __str__(self):
        return ' -> '.join(str(i) for i in self.items) + ' -> null'

# Driver code
queue = Dequeue()
queue.add_back(10)
queue.add_back(20)
queue.add_back(30)
print(queue)  # initial state
removed_front = queue.remove_front()
print(f'Removed from front: {removed_front}')
print(queue)  # after removing front
removed_back = queue.remove_back()
print(f'Removed from back: {removed_back}')
print(queue)  # after removing back

return self.items.pop(0) # remove front item

remove and return the first element to simulate removing from front

return self.items.pop() # remove back item

remove and return the last element to simulate removing from back

Output

10 -> 20 -> 30 -> null

Removed from front: 10

20 -> 30 -> null

Removed from back: 30

20 -> null

Complexity Analysis

Time: O(n) for remove_front because removing first element shifts all others; O(1) for remove_back because last element removal is direct

Space: O(n) because the dequeue stores all elements in a list

vs Alternative: Using a linked list would make remove_front O(1) as no shifting is needed, but here list shifting costs O(n)

Edge Cases

empty dequeue

remove operations return None safely without error

DSA Python

if not self.items:
            return None  # empty dequeue

single element dequeue

removing front or back removes the only element, leaving dequeue empty

DSA Python

return self.items.pop(0)  # remove front item

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, think of the dequeue operation to handle front and back changes.

Common Mistakes

Mistake: Using pop(0) without checking if the dequeue is empty causes errors.
Fix: Always check if the dequeue is empty before removing from front or back.

Mistake: Confusing add_front with add_back and removing from wrong ends.
Fix: Remember add_front inserts at start, add_back appends at end; remove_front removes first, remove_back removes last.

Summary

It allows removing elements from both the front and back ends of a dequeue.

Use it when you need flexible removal from either end of a collection.

The key is that removing from front may shift elements in a list, while removing from back is direct.