[Python] deque in collections

Deque is a Double-Ended Queue.

Deque supports thread-safe, memory-efficient appends and pops from either side.

Import

from collections import deque

Attributes

maxlen

Maximum size of a deque or None if unbounded.

Once a bounded length deque is full, when new items are added, a corresponding number of items are discarded from the opposite end.

d = deque([1, 2, 3], 3)
print(d)
# deque([1, 2, 3], maxlen=3)

d.append(4)
print(d)
# deque([2, 3, 4], maxlen=3)

d.appendleft(0)
print(d)
# deque([0, 2, 3], maxlen=3)

Methods

append(x)

Add x to the right side of the deque.

appendleft(x)

Add x to the left side of the deque.

clear()

Remove all elements from the deque leaving it with length 0.

copy()

Create a shallow copy of the deque.

v3.5 or later

count(x)

Count the number of deque elements equal to x.

v3.2 or later

extend(iterable)

Extend the right side of the deque by appending elements from the iterable argument.

d = deque([1, 2, 3])
d.extend([4, 5])
print(d)
# deque([1, 2, 3, 4, 5])

extendleft(iterable)

Extend the left side of the deque by appending elements from iterable.

d = deque([1, 2, 3])
d.extendleft([4, 5])
print(d)
# deque([5, 4, 1, 2, 3])

index(x[, start[, stop]])

Return the position of x in the deque the first match or raises ValueError if not found.

v3.5 or later

insert(i, x)

Insert x into the deque at position i.

If the insertion would cause a bounded deque to grow beyond maxlen, an IndexError is raised.

v3.5 or later

d = deque([1, 2, 3])
d.insert(1, 7)
print(d)
# deque([1, 7, 2, 3])

pop()

Remove and return an element from the right side of the deque.

If no elements are present, raises, , an IndexError.

popleft()

Remove and return an element from the left side of the deque.

If no elements are present, raises an IndexError.

remove(value)

Remove the first occurrence of value.

If not found, raises a ValueError.

reverse()

Reverse the elements of the deque in-place and then return None.

v3.2 or later

d = deque([1, 2, 3])
d.reverse()
print(d)
# deque([3, 2, 1])

rotate(n=1)

Rotate the deque n steps to the right.

If n is negative, rotate to the left.

d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)
# deque([4, 5, 1, 2, 3])

d.rotate(-1)
print(d)
# deque([5, 1, 2, 3, 4])

Conclusion

List can also be used as queue in addion to stack. But it is less efficient than deque.

List is only fast in append and pop case. When you insert and pop at the first element from list, it will be inefficient.

Therefore, if you need to use queue, it is recommended to use deque module.