A deque is a double-ended queue in which elements can be both inserted and deleted from either the left or the right end of the queue. deque class in Python supports deque. It is a generalization of stacks and queues. It support thread-safe, memory efficient appends and pops from either side of the deque.
Syntax
To create a double ended queue, use below syntax
collections.deque([iterable[, maxlen]])
It returns a new deque object where
- iterable : Deque is initialized left-to-right with data from iterable. If iterable is not specified, the new deque is empty.
- maxlen : If not specified, deques may grow to an arbitrary length. Otherwise deque is bounded to the specified maxlen. Once a bounded length deque is full, a corresponding number of items are discarded from the opposite end when new items are added.
List objects also support similar operations, but deque is optimized.
Important Methods
Commonly used function defined in deque class are
- 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.
- count(x) : Count the number of deque elements equal to x.
- extend(iterable) : Extend the right side of the deque by appending elements from the iterable argument.
- extendleft(iterable) : Extend the left side of the deque by appending elements from iterable.
- index(x[, start[, stop]]) : Return the position of x in the deque (at or after index start and before index stop).
- insert(i, x) : Insert x into the deque at position i.
- pop() : Remove and return an element from the right side of the deque.
- 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.
- reverse() : Reverse the elements of the deque in-place
- rotate(n=1) : Rotate the deque n steps to the right. If n is negative, rotate to the left.
Example
Following example illustrates the various operation that can be performed on deque. First a deque of vowel is created. Then on that elements are appended and removed it. This example also shows how to reverse and rotate the entries of deque.
import collections
# Deque with lowercase letters
d = collections.deque(['a', 'e', 'i', 'o', 'u'])
# Count elements
print("Item count: " + str(len(d)))
# Output
# Item count: 5
# Iterated over deque
for elem in d:
print(elem, end=",")
# Output
# a,e,i,o,u,
print()
# POP entry from right
d.pop()
print(d)
# Output
# deque(['a', 'e', 'i', 'o'])
# POP entry from left
d.popleft()
print(d)
# Output
# deque(['e', 'i', 'o'])
# Add entry to right
d.append(2)
print(d)
# Output
# deque(['e', 'i', 'o', 2])
# Add entry to left
d.appendleft(1)
print(d)
# Output
# deque([1, 'e', 'i', 'o', 2])
# rotate the deque
d.rotate(4)
print(d)
# Output
# deque(['e', 'i', 'o', 2, 1])
# Add multiple elements at once
d.extend('jkl')
print(d)
# Output
# deque(['e', 'i', 'o', 2, 1, 'j', 'k', 'l'])
# Reverse element
d.reverse()
print(d)
# Output
# deque(['l', 'k', 'j', 1, 2, 'o', 'i', 'e'])