Queue
from collections import deque
my_deque = deque()
Add O(1)
my_deque.append(item)
my_deque.appendleft(item)
Remove O(1)
my_deque.pop()
my_deque.popleft()
Extend O(k)
my_deque.extend(iterable)
my_deque.extendleft(iterable)
Remove O(n)
Clear
Example
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry") # Terry arrives
queue.append("Graham") # Graham arrives
queue.popleft() # The first to arrive now leaves
queue.popleft() # The second to arrive now leaves
queue # Remaining queue in order of arrival
> from collections import deque
> d = deque('ghi') # make a new deque with three items
> for elem in d: # iterate over the deque's elements
... print(elem.upper())
G
H
I
> d.append('j') # add a new entry to the right side
> d.appendleft('f') # add a new entry to the left side
> d # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])
> d.pop() # return and remove the rightmost item
'j'
> d.popleft() # return and remove the leftmost item
'f'
> list(d) # list the contents of the deque
['g', 'h', 'i']
> d[0] # peek at leftmost item
'g'
> d[-1] # peek at rightmost item
'i'
> list(reversed(d)) # list the contents of a deque in reverse
['i', 'h', 'g']
> 'h' in d # search the deque
True
> d.extend('jkl') # add multiple elements at once
> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
> d.rotate(1) # right rotation
> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
> d.rotate(-1) # left rotation
> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
> deque(reversed(d)) # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
> d.clear() # empty the deque
> d.pop() # cannot pop from an empty deque
Traceback (most recent call last):
File "<pyshell#6>", line 1, in -toplevel-
d.pop()
IndexError: pop from an empty deque
> d.extendleft('abc') # extendleft() reverses the input order
> d
deque(['c', 'b', 'a'])
Moving Average
def moving_average(iterable, n=3):
# moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
# http://en.wikipedia.org/wiki/Moving_average
it = iter(iterable)
d = deque(itertools.islice(it, n-1))
d.appendleft(0)
s = sum(d)
for elem in it:
s += elem - d.popleft()
d.append(elem)
yield s / n