Queue in Python - Part 2

Double ended queues with deque

The deque class in the collections module makes it easy to create deques or double ended queues. Deques allow you to append and delete elements from both ends more efficiently than in lists.

Import the module:

from collections import deque

Instantiate deque:

d = deque()

Append to right and left:

d.append("b")
d.appendleft("a")
print(d)
# output is: deque(['a', 'b'])

In the same fashion, elements can be deleted (popped) :

d.pop()
d.popleft()
print(d)
# outputs: deque([])

Starting from Python 2.6 you can limit the maximum numbers of elements in a deque passing the maxlen argument to the constructor. If the limit is exceeded, items from the opposite end will be popped as new ones are appended to this end:

d = deque(maxlen=3)
deque([], maxlen=3)
for i in range(4):
    d.append(i)
    print(d)
...
# Output:
deque([0], maxlen=3)
deque([0, 1], maxlen=3)
deque([0, 1, 2], maxlen=3)
deque([1, 2, 3], maxlen=3)

Double ended queues with deque#

Double ended queues with deque