Double Ended Queue Deque in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Double Ended Queue (Deque)?

A Double Ended Queue, or Deque, is a data structure where elements can be added or removed from both the front and the back.

beginner

Name two main operations you can perform on a Deque.

You can add elements (called enqueue) and remove elements (called dequeue) from both the front and the back ends.

beginner

How does a Deque differ from a regular Queue?

A regular Queue allows adding at the back and removing from the front only. A Deque allows adding and removing from both ends.

intermediate

What is the output after these operations on an empty Deque: add_front(1), add_back(2), remove_front(), add_back(3)?

After add_front(1): 1
After add_back(2): 1 -> 2
After remove_front(): 2
After add_back(3): 2 -> 3

beginner

Why is a Deque useful in real life?

Because it lets you add or remove items from both ends, it is like a line where people can enter or leave from front or back, useful for tasks like undo/redo or sliding windows.

Which operation is NOT possible in a Deque?

A Add element at front

B Add element in the middle

C Remove element from back

D Remove element from front

Deques allow adding/removing only at front or back, not in the middle.

What is the state of the Deque after add_back(5) on an empty Deque?

A Error

B Empty

C null

D 5

Adding 5 at back on empty Deque results in Deque with one element: 5.

If a Deque has elements 3 -> 4 -> 5, what is the result after remove_back()?

A 3 -> 4

B 4 -> 5

C 3 -> 5

D Empty

Removing from back removes 5, leaving 3 -> 4.

Which real-life example best matches a Deque?

A A line where people can enter or leave from front or back

B A stack of plates where you add/remove only from top

C A line where people enter only at the back

D A random pile of books

Deque allows adding/removing from both ends, like a line with two open doors.

What is the time complexity for adding or removing elements at either end of a Deque?

A O(n)

B O(log n)

C O(1)

D O(n^2)

Deque operations at front or back are done in constant time O(1).

Explain what a Double Ended Queue (Deque) is and how it works.

Think about a line where people can enter or leave from front or back.

Describe a real-life situation where using a Deque would be helpful and why.

Consider undo/redo or sliding window problems.

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