DSA using Python: Deque

Follow me

If you want to understand with Graphical Representation click on it.

You can find the explanatory video at the bottom of this page.

Study Guide: Understanding Deque in Python

What is a Deque? A Simple Introduction

Imagine you have a stack of plates in your home. Sometimes you add a new plate to the top of the stack, and sometimes you take one from the top. But what if you could also add a plate to the bottom or take one from the bottom? This idea of working from both ends of a line is the core concept of a Deque.

Deque stands for Double Ended Queue. In simple terms, a Deque is a special kind of list where you can add or remove items from both the front and the back. This makes it a very flexible and powerful tool. The most important thing to remember is that with a Deque, you can perform actions on both sides.

Deque vs. a Normal Queue

To understand what makes a Deque special, it helps to compare it to a normal queue.

Feature	Normal Queue	Deque
Adding Items	Only at the back.	Can add at the back and the front.
Removing Items	Only from the front.	Can remove from the front and the back.

Because a Deque allows you to add and remove items from both ends, it is considered more powerful and versatile than a normal queue.

Real-Life Examples of Deque

The idea of a Deque appears in many everyday situations:

• A Stack of Plates: You can add a new plate to the top (the back of the line) or take the top one off. You could also carefully slide a plate onto the bottom or remove one from the bottom.
• A School Line: A teacher might remove a student from the front of the line, while a new student joins at the very back.
• A Web Browser: The back and forward buttons work like a Deque. The "Back" button takes you to the item at the front (previous page), while the "Forward" button takes you to the item at the back (next page).
• A Music Playlist: Skipping to the "previous song" is like accessing the front of the list, while playing the "next song" means accessing the back of the list.

In all these examples, the core idea is the same: actions are happening on both sides of the line.

Understanding Deque Operations

There are four basic operations you need to know to work with a Deque. Let's imagine our Deque as a horizontal line of items.

• append(): This operation adds a new item to the right side (the back) of the Deque.
• appendleft(): This operation adds a new item to the left side (the front) of the Deque.
• pop(): This operation removes an item from the right side (the back) of the Deque.
• popleft(): This operation removes an item from the left side (the front) of the Deque.

Simply put, a Deque is all about adding and removing items from the left and the right.

Deque in Action: A Visual Example

Let's see how these operations change a Deque. Imagine our Deque starts with these numbers:

[10, 20, 30]

Here, 10 is on the left side and 30 is on the right side.

1. Perform appendleft(5): A 5 is added to the left.
   • The Deque becomes: [5, 10, 20, 30]
2. Perform append(40): A 40 is added to the right.
   • The Deque becomes: [5, 10, 20, 30, 40]
3. Perform popleft(): The item on the far left (5) is removed.
   • The Deque becomes: [10, 20, 30, 40]
4. Perform pop(): The item on the far right (40) is removed.
   • The Deque becomes: [10, 20, 30]

This shows how you have complete control over both ends of the list.

How to Use Deque in Python

Here is a simple Python code example that shows how to create and use a Deque.

from collections import deque

# Create an empty deque
d = deque()

# Add items to the deque
d.append(10)
d.append(20)
d.appendleft(5)

# Print the current deque
print(d)

# Remove items from the deque
d.pop()
print(d)

d.popleft()
print(d)

Line-by-Line Code Explanation

• from collections import deque
  • This line tells Python that we want to use the deque tool, which is located in a library called collections.
• d = deque()
  • This line creates a new, empty Deque and we give it the name d.
• d.append(10)
  • This adds the number 10 to the right side of our Deque.
• d.append(20)
  • This adds the number 20 to the right side, after 10.
• d.appendleft(5)
  • This adds the number 5 to the left side of our Deque.
• print(d)
  • This displays the current state of the Deque on the screen.
• d.pop()
  • This removes the last item from the right side of the Deque.
• d.popleft()
  • This removes the first item from the left side of the Deque.

Understanding the Output

When you run the code above, the output will show how the Deque changes with each operation:

• After adding items: deque([5, 10, 20])
• After pop(): deque([5, 10])
• After popleft(): deque([10])

Common Mistakes to Avoid

When you are first learning about Deques, there are a few common mistakes to watch out for.

1. Forgetting to import deque: You must always include the line from collections import deque at the beginning of your code. Without it, Python won't know what a Deque is.
2. Confusing pop() and popleft(): It's easy to mix these up. Just remember: pop() removes from the right, and popleft() removes from the left.
3. Thinking a Deque is just a normal list: While it looks similar, a Deque is much faster and more powerful for adding and removing items from the ends.

Quick Revision

The simplest way to remember what a Deque is: A Deque is like a line where people can enter and exit from the front and the back. It is a double ended queue, meaning both sides are open for action.

--------------------------------------------------------------------------------

Quiz: Test Your Understanding

Answer the following questions in 2-3 sentences based on the information provided in this guide.

1. What does "Deque" stand for, and what is its main feature?
2. What is the main difference between a Deque and a normal Queue?
3. To add an item to the very beginning (left side) of a Deque, which operation would you use?
4. What does the pop() operation do in a Deque?
5. If a Deque contains [1, 2, 3] and you perform the popleft() operation, what will the Deque contain afterward?
6. Describe a real-life example of a Deque and explain why it fits the definition.
7. In Python, what is the first line of code you must write before you can create a Deque?
8. Why is a Deque considered more powerful than a normal list or queue for certain tasks?
9. If you have an empty Deque and perform append(10) followed by appendleft(5), what will the Deque look like?
10. What is a common mistake beginners make when trying to remove an item from the left side of a Deque?

--------------------------------------------------------------------------------

Answer Key

1. "Deque" stands for Double Ended Queue. Its main feature is that you can add and remove items from both the front (left) and the back (right) of the list.
2. The main difference is that a normal Queue only allows you to add items to the back and remove them from the front. A Deque allows you to add and remove items from both ends.
3. To add an item to the very beginning (left side) of a Deque, you would use the appendleft() operation. This places the new item at the front of the line.
4. The pop() operation removes the item from the far right side (the back) of the Deque. It is the opposite of the append() operation.
5. If a Deque is [1, 2, 3], performing popleft() will remove the leftmost item, which is 1. The Deque will then contain [2, 3].
6. A web browser's back/forward history is a real-life example. Clicking "Back" is like taking an item from the front of the list, and clicking "Forward" is like accessing an item from the back.
7. The first line of code you must write is from collections import deque. This imports the necessary tool from the collections library.
8. A Deque is considered more powerful because it offers the flexibility to add or remove elements from both ends efficiently. This makes it faster than a normal list for these specific operations.
9. After append(10), the Deque is [10]. After appendleft(5), the 5 is added to the left, so the final Deque will look like deque([5, 10]).
10. A common mistake is to confuse pop() and popleft(). Beginners might use pop() expecting to remove the left-most item, when they should be using popleft() for that action.

--------------------------------------------------------------------------------

Essay Questions

1. Using the analogy of a stack of plates, explain the concept of a Deque. Describe how each of the four main operations (append, appendleft, pop, popleft) would correspond to actions performed on the stack of plates.
2. Compare and contrast a Deque with a normal Queue. Provide a detailed explanation of why a Deque is considered "more powerful" and describe a scenario where that extra power would be useful.
3. Choose two of the real-life examples mentioned (school line, browser history, or playlist) and describe them in detail. For each example, explain which specific Deque operations would be used to model the actions that occur.
4. Walk through the provided Python code example step-by-step. For each line of code that modifies the Deque, describe the state of the Deque and explain exactly what change was made.
5. Discuss the three common beginner mistakes listed in the guide. For each mistake, explain why it causes a problem and provide the correct approach to avoid it.

--------------------------------------------------------------------------------

Glossary of Key Terms

Term	Definition
Deque	A special type of list, short for Double Ended Queue, that allows you to add and remove items from both the front and the back.
Double Ended Queue	The full name for Deque. It emphasizes that both ends of the queue are open for operations.
Queue	A list where you can only add items to the back and remove items from the front, like a line of people waiting.
append()	A Deque operation that adds a new item to the right side (the back) of the list.
appendleft()	A Deque operation that adds a new item to the left side (the front) of the list.
pop()	A Deque operation that removes an item from the right side (the back) of the list.
popleft()	A Deque operation that removes an item from the left side (the front) of the list.
collections	A built-in Python library that contains specialized data structures, including the Deque.
import	A Python command used to bring a library or a specific tool from a library into your code so you can use it.