Python Deque Explained: Efficient Stack and Queue Operations
Deque in Python, also known as a double-ended queue, is a type of data structure that allows you to add and remove elements from either end. Python’s collections
module provides us with the deque
class to create deques.
They are different from queues and stacks as they support more flexible, memory-efficient, and in some cases, faster operations.
Unlike lists or tuples, deques are linked lists that can handle append and pop operations from both ends with fast time complexity.
This makes it suitable for data structures such as queues (FIFO – First In First Out) and stacks (LIFO – Last In First Out).
Let’s proceed with our Python deque tutorial.
- 1 Creating Deques in Python
- 2 Accessing Elements in a Deque
- 3 Modifying Elements
- 4 Deque Length
- 5 Adding Elements to the Right End (append())
- 6 Adding Elements to the Left End (appendleft())
- 7 Adding Multiple Elements to the Right End (extend())
- 8 Adding Multiple Elements to the Left End (extendleft())
- 9 Iterating over a deque
- 10 Sorting a Deque
- 11 Searching Deque
- 12 Removing Elements from a Deque
- 13 Deque Rotation
- 14 Using Deque as a Stack
- 15 Using Deque as a Queue
- 16 Using Deque as a Circular Queue
- 17 Nesting a Deque
- 18 Understanding Thread-Safety in Deque
- 19 Deque vs. Lists (Performance Comparison)
- 20 Memory Consumption of Deque vs. Lists
- 21 Common Mistakes and Pitfalls in Deque Usage
- 22 When to Use Deque vs. List
- 23 Real-world Applications of Deque
- 24 Resources
Creating Deques in Python
Here’s how you create a deque using the collections
module:
from collections import deque # Create a deque d = deque()
To add elements to the deque, you can use the append()
method:
d.append('a') d.append('b') d.append('c')
Now, if we print our deque, we’ll get:
print(d)
Output:
deque(['a', 'b', 'c'])
In the above code, we first import the deque
class from the collections
module. Then we create a deque d
. We append three elements ‘a’, ‘b’, and ‘c’ to the right end of the deque using the append()
method.
When we print the deque, we see these elements in the order they were added.
You can also initialize a deque with multiple elements at once, and optionally set a maximum length:
d = deque(['x', 'y', 'z'], maxlen=5)
This creates a deque with a maximum length of 5. If more elements are added, it will automatically remove elements from the opposite end to maintain the size.
Accessing Elements in a Deque
Accessing elements in a deque is done by indexing, similar to how you would access elements in a list:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) # Access elements print(d[0]) print(d[-1])
Output:
'a' 'e'
In the code above, we create a deque d
with five elements.
When we print d[0]
, we get the first element ‘a’. When we print d[-1]
, we get the last element ‘e’.
Python allows negative indexing where -1 refers to the last element, -2 refers to the second last, and so on.
However, unlike lists, deques do not support slicing because they are designed to be primarily append and pop operations on both ends and thus are optimized for such operations.
Modifying Elements
Here’s how you modify an element:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) # Modify an element d[0] = 'z' print(d)
Output:
deque(['z', 'b', 'c', 'd', 'e'])
In this code, we first create a deque d
with five elements. Then we change the first element (at index 0) to ‘z’.
When we print the deque, we see that the first element has been modified to ‘z’.
Remember that modifying an element in a deque has a time complexity of O(n) as it has to iterate through the deque to find the element.
Therefore, if you need frequent modifications in the middle of your data structure, choose a different data type.
Deque Length
You can use the built-in len()
function to get the number of items in a deque:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) print(len(d))
Output:
5
In this code, we first create a deque d
with five elements. Then we print the length of the deque using len(d)
, and we get 5, which is the number of elements in the deque.
You can also check if a deque is empty or not:
# Check if deque is empty if not d: print("Deque is empty.") else: print("Deque is not empty.")
Output:
Deque is not empty.
Here, not d
checks if the deque d
is empty. If it is, it prints “Deque is empty.” If it’s not, it prints “Deque is not empty.”
Adding Elements to the Right End (append())
You can add elements to the end of a deque using the append()
method. Here’s how you do it:
from collections import deque d = deque(['a', 'b', 'c']) # Add element to the right end d.append('d') print(d)
Output:
deque(['a', 'b', 'c', 'd'])
In the code above, we first create a deque d
with three elements. Then we add ‘d’ to the right end of the deque using the append()
method.
When we print the deque, we see ‘d’ at the right end of the deque.
The append()
operation has a time complexity of O(1), which means it’s a very fast operation no matter how large the deque is.
Adding Elements to the Left End (appendleft())
You can also add elements to the left end of a deque using the appendleft()
method. Here’s how:
from collections import deque d = deque(['b', 'c', 'd']) # Add element to the left end d.appendleft('a') print(d)
Output:
deque(['a', 'b', 'c', 'd'])
In the code above, we first create a deque d
with three elements. Then we add ‘a’ to the left end of the deque using the appendleft()
method. When we print the deque, we see ‘a’ at the left end of the deque.
Similar to append()
, the appendleft()
operation also has a time complexity of O(1).
Adding Multiple Elements to the Right End (extend())
The extend()
method allows you to add multiple elements to the right end of a deque. Here’s how:
from collections import deque d = deque(['a', 'b']) # Add multiple elements to the right end d.extend(['c', 'd', 'e']) print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
In the code above, we first create a deque d
with two elements. Then we add three elements ‘c’, ‘d’, and ‘e’ to the right end of the deque using the extend()
method.
When we print the deque, we see these new elements at the right end.
The time complexity of the extend()
operation is O(k), where k is the number of elements to be added.
Adding Multiple Elements to the Left End (extendleft())
The extendleft()
method allows you to add multiple elements to the left end of a deque. Here’s how you do it:
from collections import deque d = deque(['d', 'e']) # Add multiple elements to the left end d.extendleft(['c', 'b', 'a']) print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
In the code above, we first create a deque d
with two elements. Then we add three elements ‘c’, ‘b’, and ‘a’ to the left end of the deque using the extendleft()
method. When we print the deque, we see these new elements at the left end.
Notice that the extendleft() method iterates over the input in reverse order, which can be observed in the output.
Similar to extend()
, the time complexity of extendleft()
operation is also O(k).
Iterating over a deque
You can iterate over a deque in the same way you would iterate over a list.
Here is how you can iterate over a deque in forward direction:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) # Forward iteration for i in d: print(i)
Output:
'a' 'b' 'c' 'd' 'e'
And for backward iteration, you can use the reversed()
function:
# Backward iteration for i in reversed(d): print(i)
Output:
'e' 'd' 'c' 'b' 'a'
In the code above, we first create a deque d
with five elements. Then, we iterate over the deque in forward and backward direction and print each element.
Sorting a Deque
Deques do not have a built-in sort method, but you can use the sorted()
function to get a sorted list from the deque.
Here’s an example:
from collections import deque d = deque([3, 1, 4, 1, 5, 9, 2]) # Get a sorted list from the deque sorted_d = sorted(d) print(sorted_d)
Output:
[1, 1, 2, 3, 4, 5, 9]
In the code above, we first create a deque d
with seven elements. Then, we create a sorted list sorted_d
from the deque using the sorted()
function.
The resulting list is in ascending order.
Remember that sorted()
doesn’t sort the deque in-place, but returns a new list.
This is because deques are designed to have fast append and pop operations from both ends, but not for operations like sorting that require random access to the elements.
Searching Deque
You can perform a linear search in a deque using the index()
method. The index()
method returns the index of the first occurrence of the specified value.
Here’s an example:
from collections import deque d = deque(['a', 'b', 'c', 'b', 'a']) # Get the index of 'b' index = d.index('b') print(index)
Output:
1
In the code above, we first create a deque d
with five elements. Then, we use the index()
method to get the index of the first occurrence of ‘b’, which is 1.
Removing Elements from a Deque
Deque provides methods to remove elements from either end: pop()
removes and returns an element from the right end of the deque, and popleft()
removes and returns an element from the left end. Let’s look at an example:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) # Remove elements from either end right_end = d.pop() left_end = d.popleft() print(right_end) print(left_end) print(d)
Output:
'e' 'a' deque(['b', 'c', 'd'])
In the code above, we first create a deque d
with five elements. Then we remove an element from the right end using pop()
and from the left end using popleft()
.
When we print the deque, we see that the left and right end elements are removed.
Remove all elements
The clear()
method removes all elements from the deque:
d.clear() print(d)
Output:
deque([])
Here, after invoking d.clear()
, all elements in the deque are removed, and we get an empty deque as the output.
The time complexity of pop()
, popleft()
, and clear()
operations is O(1).
Deque Rotation
Deque provides a rotate()
method that allows you to rotate the deque by n steps to the right. If n is negative, rotate to the left.
Here’s an example:
from collections import deque d = deque(['a', 'b', 'c', 'd', 'e']) # Rotate deque by 2 steps to the right d.rotate(2) print(d)
Output:
deque(['d', 'e', 'a', 'b', 'c'])
In the code above, we first create a deque d
with five elements.
Then we rotate the deque by 2 steps to the right using rotate(2)
. The last two elements are shifted to the front of the deque.
Negative Rotation
If you rotate by a negative value, it rotates to the left:
# Rotate deque by 2 steps to the left d.rotate(-2) print(d)
Output:
deque(['a', 'b', 'c', 'd', 'e'])
Here, after invoking d.rotate(-2)
, the first two elements are shifted to the end of the deque.
The rotate()
operation has a time complexity of O(k), where k is the number of steps.
Using Deque as a Stack
A stack is a LIFO (Last In, First Out) data structure. In Python, you can use a deque to implement a stack.
Here’s how you do it:
from collections import deque stack = deque() # Add elements to the stack stack.append('a') stack.append('b') stack.append('c') print(stack) # Remove elements from the stack top = stack.pop() print(top) print(stack)
Output:
deque(['a', 'b', 'c']) 'c' deque(['a', 'b'])
In the code above, we first create an empty deque stack
. Then we add three elements to the stack using the append()
method, which adds elements to the right end of the deque.
To remove elements from the stack, we use the pop()
method, which removes and returns the rightmost element.
Thus, the last element added is the first one to be removed, following the LIFO principle.
Using Deque as a Queue
A queue is a FIFO (First In, First Out) data structure. You can use a deque to implement a queue.
Here’s how:
from collections import deque queue = deque() # Add elements to the queue queue.append('a') queue.append('b') queue.append('c') print(queue) # Remove elements from the queue front = queue.popleft() print(front) print(queue)
Output:
deque(['a', 'b', 'c']) 'a' deque(['b', 'c'])
In the code above, we first create an empty deque queue
. Then we add three elements to the queue using the append()
method.
To remove elements from the queue, we use the popleft()
method, which removes and returns the leftmost element.
Thus, the first element added is the first one to be removed, following the FIFO principle.
Using Deque as a Circular Queue
A circular queue, also known as a ring buffer, is a queue in which the last element points to the first element making a circular link.
Deque in Python can be used to implement a circular queue by using the rotate()
function. Here’s how:
from collections import deque circular_queue = deque(['a', 'b', 'c', 'd', 'e'], maxlen=5) # Rotate the queue to the right circular_queue.rotate(1) print(circular_queue)
Output:
deque(['e', 'a', 'b', 'c', 'd'], maxlen=5)
In the code above, we first create a deque circular_queue
with five elements and a maxlen
of 5.
Then we rotate the deque by one step to the right using rotate(1)
.
The last element ‘e’ is shifted to the front of the deque, making it act like a circular queue.
Nesting a Deque
Similar to lists, deques can also contain other deques (or lists) as elements. This is called nesting.
Here’s an example:
from collections import deque # Initialize a deque with another deque as an element d = deque(['a', deque(['b', 'c', 'd']), 'e']) print(d)
Output:
deque(['a', deque(['b', 'c', 'd']), 'e'])
In the code above, we create a deque d
with three elements.
The second element is another deque with three elements. The output shows a deque within a deque.
Remember that when you modify a nested deque, the changes reflect in the outer deque as well.
Understanding Thread-Safety in Deque
Deque operations (append(), appendleft(), pop(), popleft(), and so on) are thread-safe in Python.
This makes deque a suitable choice when implementing data structures that need to handle concurrent operations.
Here’s a simple example:
from collections import deque from threading import Thread # This function appends 100000 elements to the deque def append_elements(d): for i in range(100000): d.append(i) d = deque() # Create two threads that execute the same function t1 = Thread(target=append_elements, args=(d,)) t2 = Thread(target=append_elements, args=(d,)) # Start the threads t1.start() t2.start() # Wait for both threads to finish t1.join() t2.join() print(len(d))
Output:
200000
In this code, we define a function append_elements()
that appends 100000 elements to the deque. We then create two threads that execute this function concurrently.
Since deque operations are thread-safe, we don’t need to worry about any race conditions that might occur due to simultaneous access and modification of the deque.
Deque vs. Lists (Performance Comparison)
Deques and lists have different performance characteristics, and understanding these differences can help you choose the right data structure for your use case.
For operations involving appending or popping elements at the ends (either end for deques, right end for lists), deques are more efficient than lists.
This is because these operations have a time complexity of O(1) for deques.
from collections import deque from timeit import timeit # A large number of elements N = 10**6 lst = [0] * N deq = deque(lst) # Measure the time taken to append and pop elements at the ends list_time = timeit(lambda: lst.append(10) or lst.pop(), number=N) deque_time = timeit(lambda: deq.append(10) or deq.pop(), number=N) print(f"List time: {list_time}") print(f"Deque time: {deque_time}")
Output:
List time: 0.2596190000003844 Deque time: 0.20638569999937317
In this code, we first create a list and a deque with a large number of elements.
Then we measure the time taken to append and pop elements at the ends for both data structures. You’ll find that deque is faster.
On the other hand, for operations involving accessing or modifying elements in the middle, lists are much more efficient than deques.
This is because lists in Python are implemented as dynamic arrays, which provide fast O(1) random access.
list_time = timeit(lambda: lst[N//2] or lst.insert(N//2, 10), number=N) deque_time = timeit(lambda: deq[N//2] or deq.insert(N//2, 10), number=N) print(f"List time: {list_time}") print(f"Deque time: {deque_time}")
Output:
List time: 0.1969280000012077 Deque time: 50.14866749999965
In this code, we measure the time taken to access and modify an element in the middle for both data structures. You’ll find that list is significantly faster.
Memory Consumption of Deque vs. Lists
In addition to time complexity, another important factor to consider when choosing between a deque and a list is memory consumption.
Deques are implemented as a doubly-linked list, which means they require storing two pointers (next and prev) for each item.
This results in higher memory overhead compared to lists.
Let’s look at a simple comparison using the sys
module to measure the size of a list and a deque with the same elements:
import sys from collections import deque # Create a list and a deque with 1 million elements lst = [0] * 10**6 deq = deque(lst) list_size = sys.getsizeof(lst) deque_size = sys.getsizeof(deq) print(f"List size: {list_size} bytes") print(f"Deque size: {deque_size} bytes")
Output:
List size: 8000056 bytes Deque size: 8250624 bytes
The deque has a larger size than the list.
The additional memory overhead of deques is a trade-off for their flexibility and performance advantages in certain scenarios (like efficient appends/pops at both ends).
Common Mistakes and Pitfalls in Deque Usage
When using deques, it’s important to be aware of some common mistakes and pitfalls that could lead to errors or unexpected behavior.
Over-Popping a Deque
When you pop from an empty deque, Python raises an IndexError
. Always ensure your deque has elements before you attempt to pop.
from collections import deque d = deque() try: d.pop() except IndexError: print("Cannot pop from an empty deque.")
Output:
Cannot pop from an empty deque.
Ignoring Maxlen Parameter
If you specify a maxlen
when creating a deque, when the deque is full, adding new elements will discard elements from the opposite end.
If you do not wish for elements to be automatically discarded, do not set a maxlen
.
from collections import deque d = deque(maxlen=3) d.append(1) d.append(2) d.append(3) d.append(4) print(d) # Output: deque([2, 3, 4], maxlen=3)
In this code, when we append the element 4 to a deque that is already full, the element 1 is automatically discarded to make room.
When to Use Deque vs. List
Understanding when to use a deque versus other data structures is key to writing efficient code.
- Deque: Use a deque when you need to efficiently add or remove items from the ends, such as when implementing queues, stacks, or circular queues. Deques are also a good choice for maintaining a ‘sliding window’ of elements, thanks to the
maxlen
parameter. - List: Use a list when you need to access or modify items by index, as lists provide O(1) time complexity for these operations. Lists also consume less memory than deques.
In the end, the choice of data structure will largely depend on the specific requirements of your application.
Real-world Applications of Deque
The deque data structure is quite versatile and finds utility in numerous real-world applications.
- Undo Operations: Many applications provide an undo feature, which can be implemented with a deque. Each operation is added to the deque, and when the user requests an undo, the operation from the end of the deque is taken and reversed.
- Maintaining History: Deque can be used to maintain history in applications where only a certain number of recent records are needed.
- Scheduling Algorithms: Deques can be used to implement scheduling algorithms like Round Robin Scheduling, which is used in the design of time-sharing systems.
Remember, when the problem involves adding or removing elements from either end of the collection, consider using a deque.
That brings us to the end of this tutorial on Python deques. I hope you found this information useful and that it deepens your understanding of deque in Python and when to use them.
Resources
https://docs.python.org/3/library/collections.html#collections.deque
Mokhtar is the founder of LikeGeeks.com. He is a seasoned technologist and accomplished author, with expertise in Linux system administration and Python development. Since 2010, Mokhtar has built an impressive career, transitioning from system administration to Python development in 2015. His work spans large corporations to freelance clients around the globe. Alongside his technical work, Mokhtar has authored some insightful books in his field. Known for his innovative solutions, meticulous attention to detail, and high-quality work, Mokhtar continually seeks new challenges within the dynamic field of technology.