DSA Deques

A deque (pronounced "deck") is a double-ended queue. A regular queue adds items at the back and removes them from the front. A deque allows both actions at either end. The structure gives you the freedom of a stack and a queue in one container.

Picture a train with doors at both ends. Passengers can board or leave from the front door or the back door. Nobody needs to shuffle through the middle. A deque works the same way with data.

How a Deque Looks

        add front                 add back
            |                         |
            v                         v
   +----+----+----+----+----+----+----+
   | 10 | 20 | 30 | 40 | 50 | 60 |    |
   +----+----+----+----+----+----+----+
            ^                         ^
            |                         |
      remove front              remove back

Core Operations

Python provides a ready-made deque in the collections module. Every end operation runs in O(1) time.

from collections import deque

d = deque([20, 30, 40])
d.append(50)        # add at back    -> [20, 30, 40, 50]
d.appendleft(10)    # add at front   -> [10, 20, 30, 40, 50]
d.pop()             # remove back    -> [10, 20, 30, 40]
d.popleft()         # remove front   -> [20, 30, 40]
print(d[0], d[-1])  # 20 40

• append(x) adds an item at the back.
• appendleft(x) adds an item at the front.
• pop() removes and returns the back item.
• popleft() removes and returns the front item.

Why Not Use a List

A Python list handles back operations quickly. Removing the first item with pop(0) forces every remaining item to shift one slot left, which costs O(n) time. A list of one million items makes that shift painfully slow. A deque removes the front item in O(1) time because it stores items in linked blocks instead of one long row.

List pop(0):
[A, B, C, D]  remove A  ->  [B, C, D, _]
 every item slides left (slow)

Deque popleft():
A -> B -> C -> D  remove A  ->  B -> C -> D
 only the front pointer moves (fast)

Example: Palindrome Checker

A deque compares the front and back characters in turn and shrinks inward.

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

print(is_palindrome("madam"))   # True
print(is_palindrome("table"))   # False

Example: Keep the Last Few Items

The maxlen option creates a deque with a fixed size. Adding a new item at full size pushes out the oldest item automatically.

recent = deque(maxlen=3)
for page in ["Home", "Shop", "Cart", "Pay"]:
    recent.append(page)
print(list(recent))   # ['Shop', 'Cart', 'Pay']

A browser history list or a "recently viewed" panel can use this pattern.

Rotating a Deque

The rotate method shifts items around the loop. A positive number moves items right, and a negative number moves them left.

d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(list(d))   # [4, 5, 1, 2, 3]

Real-Life Uses

Text editors use deques to track undo history, since the oldest actions drop off one end while new actions arrive at the other. Task schedulers let a worker steal jobs from the opposite end of a busy partner's list. Games store the last few moves of a player. Sliding window problems use a deque to track the largest value in the current window.

Common Mistakes

Reading the middle of a deque with an index works but costs O(n) time, so avoid heavy middle access. Calling pop on an empty deque raises an error, so check the length first. Beginners sometimes mix up pop and popleft. Remember that "left" refers to the front of the structure.

Deque vs Stack vs Queue

A stack uses one end only, so the last item added leaves first. A queue adds at one end and removes at the other, so the first item added leaves first. A deque supports both patterns. Choose a deque when a problem needs flexible access at the front and the back, such as undo history that trims old entries.

Complexity Summary

• Add or remove at either end: O(1)
• Access by index in the middle: O(n)
• Search for a value: O(n)
• Space: O(n)

Key Points

• A deque adds and removes items at both ends in O(1) time.
• Python offers deque in the collections module.
• Lists are slow at the front, and deques fix that weakness.
• The maxlen option keeps only the newest items.
• A deque can act as a stack, a queue, or both.