Double Ended Queue Deque in DSA Python - Build from Scratch

Double Ended Queue (Deque) Operations

📖 Scenario: Imagine you are managing a line of customers waiting for service at a store. Sometimes customers join the line at the front (priority customers), and sometimes at the back (regular customers). You also serve customers from both ends depending on the situation.

🎯 Goal: You will create a double ended queue (deque) using a Python list, add customers to both ends, remove customers from both ends, and finally display the current state of the queue.

📋 What You'll Learn

Create a deque with initial customers

Add customers to the front and back of the deque

Remove customers from the front and back of the deque

Print the final state of the deque showing the order of customers

💡 Why This Matters

🌍 Real World

Deques are used in real life to manage lines where people can join or leave from both ends, like customer service lines or task scheduling.

💼 Career

Understanding deques helps in jobs involving data processing, scheduling, and designing efficient algorithms for real-time systems.

1

Create the initial deque

Create a list called deque with these exact customers in order: 'Alice', 'Bob', 'Charlie'

DSA Python

# Create the initial deque with customers
# Your code here

Hint

Use a Python list with the exact names in the given order.

2

Add customers to both ends

Add 'Diana' to the front of deque using insert(0, 'Diana') and add 'Evan' to the back of deque using append('Evan')

DSA Python

deque = ['Alice', 'Bob', 'Charlie']
# Add 'Diana' to the front and 'Evan' to the back
# Your code here

Hint

Use insert(0, 'Diana') to add at front and append('Evan') to add at back.

3

Remove customers from both ends

Remove the customer from the front of deque using pop(0) and remove the customer from the back of deque using pop()

DSA Python

deque = ['Alice', 'Bob', 'Charlie']
deque.insert(0, 'Diana')
deque.append('Evan')
# Remove one customer from front and one from back
# Your code here

Hint

Use pop(0) to remove from front and pop() to remove from back.

4

Print the final deque state

Print the deque list to show the current order of customers

DSA Python

deque = ['Alice', 'Bob', 'Charlie']
deque.insert(0, 'Diana')
deque.append('Evan')
deque.pop(0)
deque.pop()
# Print the deque
# Your code here

Hint

Use print(deque) to display the list.

Practice

1. What is a deque in Python's collections module?

easy

A. A list that automatically sorts elements when inserted

B. A queue that only allows insertion at the rear and removal from the front

C. A stack that only allows insertion and removal from the top

D. A double-ended queue allowing insertion and removal from both ends

Solution

1. Step 1: Understand the deque concept

   A deque is a data structure that supports adding and removing elements from both the front and the back efficiently.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, deque allows operations on both ends, not just one end.

3. Final Answer:

   A double-ended queue allowing insertion and removal from both ends -> Option D

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Remember: deque means double-ended queue [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque only works like a queue
• Assuming deque sorts elements automatically

2. Which of the following is the correct way to import and create an empty deque in Python?

easy

A. import collections\nd = collections.deque[]

B. from collections import deque\nd = deque()

C. from collections import Deque\nd = Deque()

D. import deque\nd = deque()

Solution

1. Step 1: Check the correct import statement

   The deque class is in the collections module and must be imported as from collections import deque.

2. Step 2: Verify deque creation syntax

   Creating an empty deque is done by calling deque() with parentheses, not brackets.

3. Final Answer:

   from collections import deque\nd = deque() -> Option B

4. Quick Check:

   Correct import and empty deque creation [OK]

Hint: Use 'from collections import deque' and call deque() [OK]

Common Mistakes:

• Using uppercase 'Deque' instead of 'deque'
• Trying to import deque directly without collections
• Using square brackets [] instead of parentheses ()

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

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

medium

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

B. [1, 2, 3, 0, 4]

C. [0, 1, 2, 3, 4]

D. [1, 2, 3, 4, 0]

Solution

1. Step 1: Trace deque initialization and appendleft

   Deque starts as [1, 2, 3]. After appendleft(0), it becomes [0, 1, 2, 3].

2. Step 2: Trace append operation

   After append(4), 4 is added to the right end, making deque [0, 1, 2, 3, 4].

3. Final Answer:

   [0, 1, 2, 3, 4] -> Option C

4. Quick Check:

   appendleft adds front, append adds end [OK]

Hint: appendleft adds front, append adds end [OK]

Common Mistakes:

• Confusing appendleft with append
• Assuming append adds to front
• Not converting deque to list before printing

4. Find the error in the following code snippet:

from collections import deque
d = deque()
d.appendleft(1)
d.append(2)
d.pop()
d.pop()
d.pop()

medium

A. Calling pop() on an empty deque causes an IndexError

B. appendleft() is not a valid method for deque

C. deque() cannot be initialized empty

D. append() requires two arguments

Solution

1. Step 1: Analyze deque operations

   Deque starts empty, then 1 is added to front, 2 to end. After two pops, deque is empty.

2. Step 2: Identify error on third pop

   The third pop tries to remove from empty deque, causing IndexError.

3. Final Answer:

   Calling pop() on an empty deque causes an IndexError -> Option A

4. Quick Check:

   pop on empty deque throws error [OK]

Hint: pop() on empty deque causes error [OK]

Common Mistakes:

• Thinking appendleft() is invalid
• Assuming deque can't be empty
• Believing append() needs two arguments

5. You have a deque initialized as d = deque([10, 20, 30, 40]). You want to rotate it so that the element 30 becomes the first element. Which code snippet achieves this correctly?

hard

A. d.rotate(-2)

B. d.rotate(2)

C. d.rotate(-3)

D. d.rotate(3)

Solution

1. Step 1: Understand deque rotation

   Positive rotate moves elements to the right; negative rotate moves to the left.

2. Step 2: Calculate rotation to bring 30 to front

   30 is at index 2. Rotating left by 2 (rotate(-2)) moves 30 to front.

3. Final Answer:

   d.rotate(-2) -> Option A

4. Quick Check:

   Negative rotate shifts left, bringing 30 front [OK]

Hint: Negative rotate shifts left; positive shifts right [OK]

Common Mistakes:

• Using positive rotate instead of negative
• Confusing rotation direction
• Not counting index positions correctly