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.

Practice

1. What is the main feature of a deque (double-ended queue) compared to a regular queue?

easy

A. It only stores unique elements

B. Elements can only be added at the rear

C. Elements can be added or removed from both ends

D. Elements can only be removed from the front

Solution

1. Step 1: Understand queue vs deque

   A regular queue allows adding at rear and removing from front only.

2. Step 2: Identify deque feature

   A deque allows adding and removing elements from both front and rear ends.

3. Final Answer:

   Elements can be added or removed from both ends -> Option C

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended, so both ends work [OK]

Common Mistakes:

• Thinking deque works like a normal queue
• Assuming elements can only be added at one end
• Confusing deque with stack

2. Which of the following is the correct syntax to add an element '5' to the front of a deque named d in Python?

easy

A. d.push_front(5)

B. d.addfront(5)

C. d.insert_front(5)

D. d.appendleft(5)

Solution

1. Step 1: Recall deque methods in Python

   Python's collections.deque uses appendleft() to add at front.

2. Step 2: Check method names

   Other options are not valid deque methods in Python.

3. Final Answer:

   d.appendleft(5) -> Option D

4. Quick Check:

   appendleft adds to front [OK]

Hint: Use appendleft() to add front in Python deque [OK]

Common Mistakes:

• Using non-existent methods like push_front
• Confusing append() with appendleft()
• Trying to use list methods on deque

3. What will be the output of the following code?

from collections import deque
d = deque([1, 2, 3])
d.appendleft(0)
d.pop()
print(list(d))

medium

A. [0, 1, 2]

B. [1, 2, 3, 0]

C. [0, 1, 2, 3]

D. [1, 2]

Solution

1. Step 1: Initial deque and appendleft

   Start with deque [1, 2, 3]. appendleft(0) adds 0 at front: [0, 1, 2, 3].

2. Step 2: pop removes from rear

   pop() removes last element 3: [0, 1, 2].

3. Final Answer:

   [0, 1, 2] -> Option A

4. Quick Check:

   appendleft + pop = [0,1,2] [OK]

Hint: appendleft adds front, pop removes rear [OK]

Common Mistakes:

• Thinking pop removes from front
• Ignoring appendleft effect
• Confusing list(d) output

4. Identify the error in the following code snippet:

from collections import deque
d = deque([10, 20, 30])
d.removeleft()
print(d)

medium

A. removeleft() is not a valid deque method

B. deque cannot be initialized with a list

C. print(d) should be print(list(d))

D. No error, code runs fine

Solution

1. Step 1: Check deque methods

   deque has no method named removeleft(); correct method to remove front is popleft().

2. Step 2: Validate other parts

   deque can be initialized with list; print(d) works; so no other errors.

3. Final Answer:

   removeleft() is not a valid deque method -> Option A

4. Quick Check:

   Use popleft() to remove front [OK]

Hint: Use popleft(), not removeleft() [OK]

Common Mistakes:

• Using non-existent removeleft() method
• Thinking print(d) causes error
• Confusing initialization syntax

5. You have a deque d = deque([1, 2, 3, 4]). You perform these operations:

d.pop()
d.appendleft(0)
d.popleft()
d.append(5)
print(list(d))

What is the final state of the deque?

hard

A. [0, 1, 2, 3, 5]

B. [1, 2, 3, 5]

C. [2, 3, 4, 5]

D. [0, 2, 3, 5]

Solution

1. Step 1: Trace each operation on deque

   Start: [1, 2, 3, 4]
   d.pop() removes 4: [1, 2, 3]
   d.appendleft(0): [0, 1, 2, 3]
   d.popleft() removes 0: [1, 2, 3]
   d.append(5): [1, 2, 3, 5]

2. Step 2: Confirm final deque state

   After all operations, deque is [1, 2, 3, 5].

3. Final Answer:

   [1, 2, 3, 5] -> Option B

4. Quick Check:

   pop + appendleft + popleft + append = [1,2,3,5] [OK]

Hint: Apply operations step-by-step on deque [OK]

Common Mistakes:

• Forgetting popleft removes front
• Mixing order of operations
• Assuming appendleft stays after popleft