In this tutorial we’ll take a look at the Python Deque container type. It’s a special variant of the popular list container type, that stands for “Double Ended Queue”. If you’re familiar with Data structures like Queue or Stacks, then you might have already understood how the Deque container works. Don’t worry, there is a complete explanation included below for those who are new to this concept.
The Deque container is available from the collections library in Python, which is included in the standard Library. So no need to install any extra libraries.
Understanding Deque
Before explaining Deque’s, allow me to talk a bit about Queue’s and Stack’s.
The Stack Data structure follows a FILO concept, which stands for “First in, last out”. Imagine “stacking” 10 objects on top of each other vertically. If you want to access the first one you placed, you will have to remove the other 9 objects first. In others words, the first object placed in the stack, is the last one to be removed.
With Queue’s, we have the opposite as they follow the FIFO concept which means “First in, First out”. Queue refers to a sort of line that you might see in many real world situations. Such as waiting for their order in a restaurant. The first person to order something, is the first one to receive his meal.
Deque’s on the other hand, allow you to access it’s objects from both ends in Constant time. Unlike for example the stack, where to access the first object placed you would need O(n) amount of time, the Deque would only require a single operation ( O(1) ).
In short Deque has some performance benefits over other data structures such as the Python list. It does however have a slightly larger memory footprint because it’s a double-linked list.
Using Deque in Python
For the most part, Deque is same as Lists when in terms of available methods and functionality. Several functions that work on Lists will also work on the Deque as well.
Creating a Deque
Creating Deque’s is fairly simple. As mentioned earlier, Deque’s are located in the collections library, which is part of the standard Python library. Simply import it as shown below.
import collections
myDeque = collections.deque([1, 2, 3, 4])
Alternatively, you can import it directly to make things easier later on.
from collections import deque
myDeque = deque([1, 2, 3, 4])
Alternatively, there is another interesting way you can create Deque’s in Python using the maxlen option.
This restricts the max size of the Deque, and if a new element is added, an element from the opposite end of the Deque is removed and the new one inserted. (so if an element is added from the end of the list, an element from the beginning will be removed)
# Method 1
myDeque = deque([1, 2, 3, 4], maxlen = 3)
print(myDeque)
# Method 2
myDeque = deque(maxlen = 3)
print(myDeque)
deque([2, 3, 4], maxlen=3)
deque([], maxlen=3)The point of the above example is to show how maxlen works, and how you can initialize an empty deque with maxlen.
Basic Operations
append(): Appends a new element to the end of the Deque.
appendleft(): Appends a new element to the start of the Deque.
from collections import deque
myDeque = deque([3, 4, 1, 2])
myDeque.append(5)
print("After append: ", myDeque)
myDeque.appendleft(0)
print("After append left: ", myDeque)
After append: deque([3, 4, 1, 2, 5])
After append left: deque([0, 3, 4, 1, 2, 5])pop(): Removes the last element from the end of the Deque (the right side).
popleft(): Removes the first element from the beginning of the Deque (the left side).
from collections import deque
myDeque = deque([0, 3, 4, 1, 2, 5])
myDeque.pop()
print("After pop: ", myDeque)
myDeque.popleft()
print("After pop left: ", myDeque)
After pop: deque([0, 3, 4, 1, 2])
After pop left: deque([3, 4, 1, 2])index(value, start, end): Takes a value as it’s first parameters, and two more “position” parameters which specify a start point and an end point. Returns the index of the first occurrence of the value passed into the arguments.
from collections import deque
myDeque = deque([3, 3, 1, 2, 4, 1])
index = myDeque.index(1, 0, len(myDeque))
print(index)
index = myDeque.index(1, index + 1, len(myDeque))
print(index)
2
5remove(value): Removes the first occurrence of the value passed into it’s arguments.
count(value): Returns of the number of occurrences of a certain value in the Deque.
insert(value, index): Inserts a value at the selected index.
from collections import deque
myDeque = deque([3, 3, 1, 2, 4, 1])
# Insert
myDeque.insert(1, 4)
print("After inserting 4: ", myDeque)
myDeque.insert(0, 1)
print("After inserting : 1", myDeque)
# Count
print("Number of 1's: ", myDeque.count(1))
print("Number of 3's: ", myDeque.count(3))
# Remove
myDeque.remove(3)
print("After Removing 3: ", myDeque)
myDeque.remove(2)
print("After Removing 2: ", myDeque)
After inserting 4: deque([3, 4, 3, 1, 2, 4, 1])
After inserting : 1 deque([1, 3, 4, 3, 1, 2, 4, 1])
Number of 1's: 3
Number of 3's: 2
After Removing 3: deque([1, 4, 3, 1, 2, 4, 1])
After Removing 2: deque([1, 4, 3, 1, 4, 1])extend(iterable): Similar to append, but used for adding multiple values at once using lists or other iterable objects.
extendleft(iterable): Similar to appendleft, but used for adding multiple values at once using lists or other iterable objects.
reverse(): Completely reverses the order of all the elements in the Deque.
rotate(value): Controls by how much the Deque will be reversed. It’s like a controlled reverse, where by passing “5”, only 5 values will be flipped.
from collections import deque
myDeque = deque([1, 2, 4])
myDeque.extend([3, 5, 2])
print("After extending: ", myDeque)
myDeque.extendleft([3, 1, 4])
print("After extending left: ", myDeque)
myDeque.reverse()
print("After reversing: ", myDeque)
myDeque.rotate(4)
print("After rotating by 4: ", myDeque)
myDeque.rotate(-4)
print("After rotating by -4: ", myDeque)
After extending: deque([1, 2, 4, 3, 5, 2])
After extending left: deque([4, 1, 3, 1, 2, 4, 3, 5, 2])
After reversing: deque([2, 5, 3, 4, 2, 1, 3, 1, 4])
After rotating by 4: deque([1, 3, 1, 4, 2, 5, 3, 4, 2])
After rotating by -4: deque([2, 5, 3, 4, 2, 1, 3, 1, 4])This marks the end of the Python Deque tutorial. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.
