Python Data Structures Collections Deque

Deque
A double-ended queue, or deque, supports adding and removing elements from either
end. The more commonly used structures, stacks, and queues

Example:

1 2 3 4 5 6 7 8 9

def deque_example(): import collections d = collections.deque('abcdefg') print 'Deque:', d print 'Length:', len(d) print 'Left end:', d[0] print 'Right end:', d[-1] d.remove('c') print 'remove(c):', d

Output:

1 2 3 4 5 6 7

output: $ python collections_deque.py Deque: deque('a', 'b', 'c', 'd', 'e', 'f', 'g']) Length: 7 Left end: a Right end: g remove(c): deque([’a’, ’b’, ’d’, ’e’, ’f’, ’g’])

Populating
A deque can be populated from either end, termed “left” and “right” in the Python
implementation.

Example:

1 2 3 4 5 6 7

output: $ python collections_deque.py Deque: deque([’a’, ’b’, ’c’, ’d’, ’e’, ’f’, ’g’]) Length: 7 Left end: a Right end: g remove(c): deque([’a’, ’b’, ’d’, ’e’, ’f’, ’g’])

Output:

1 2 3 4 5

$ python collections_deque_populating.py extend : deque([’a’, ’b’, ’c’, ’d’, ’e’, ’f’, ’g’]) append : deque([’a’, ’b’, ’c’, ’d’, ’e’, ’f’, ’g’, ’h’]) extendleft: deque([5, 4, 3, 2, 1, 0]) appendleft: deque([6, 5, 4, 3, 2, 1, 0])

Consuming
Similarly, the elements of the deque can be consumed from both ends or either end,
depending on the algorithm being applied

Example:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

def deque_consume(): import collections print 'From the right:' d = collections.deque('abcdefg') while True: try: print d.pop() except IndexError: break print print '\nFrom the left:' d = collections.deque(xrange(6)) while True: try: print d.popleft() except IndexError: break print deque_comsume()

Output:

1 2 3 4 5

$ python collections_deque_consuming.py From the right: g f e d c b a From the left: 0 1 2 3 4 5

Rotating
Another useful capability of the deque is to rotate it in either direction, to skip over
some items.

Example:

1 2 3 4 5 6 7 8 9 10 11 12

def deque_rotate(): import collections d = collections.deque(xrange(10)) print 'Normal :', d d = collections.deque(xrange(10)) d.rotate(2) print 'Right rotation:', d d = collections.deque(xrange(10)) d.rotate(-2) print 'Left rotation :', d deque_rotate()