1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
\section{\module{collections} ---
High-performance container datatypes}
\declaremodule{standard}{collections}
\modulesynopsis{High-performance datatypes}
\moduleauthor{Raymond Hettinger}{python@rcn.com}
\sectionauthor{Raymond Hettinger}{python@rcn.com}
\versionadded{2.4}
This module implements high-performance container datatypes. Currently, the
only datatype is a deque. Future additions may include B-trees
and Fibonacci heaps.
\begin{funcdesc}{deque}{\optional{iterable}}
Returns a new deque objected initialized left-to-right (using
\method{append()}) with data from \var{iterable}. If \var{iterable}
is not specified, the new deque is empty.
Deques are a generalization of stacks and queues (the name is pronounced
``deck'' and is short for ``double-ended queue''). Deques support
thread-safe, memory efficient appends and pops from either side of the deque
with approximately the same \code{O(1)} performance in either direction.
Though \class{list} objects support similar operations, they are optimized
for fast fixed-length operations and incur \code{O(n)} memory movement costs
for \samp{pop(0)} and \samp{insert(0, v)} operations which change both the
size and position of the underlying data representation.
\versionadded{2.4}
\end{funcdesc}
Deque objects support the following methods:
\begin{methoddesc}{append}{x}
Add \var{x} to the right side of the deque.
\end{methoddesc}
\begin{methoddesc}{appendleft}{x}
Add \var{x} to the left side of the deque.
\end{methoddesc}
\begin{methoddesc}{clear}{}
Remove all elements from the deque leaving it with length 0.
\end{methoddesc}
\begin{methoddesc}{extend}{iterable}
Extend the right side of the deque by appending elements from
the iterable argument.
\end{methoddesc}
\begin{methoddesc}{extendleft}{iterable}
Extend the left side of the deque by appending elements from
\var{iterable}. Note, the series of left appends results in
reversing the order of elements in the iterable argument.
\end{methoddesc}
\begin{methoddesc}{pop}{}
Remove and return an element from the right side of the deque.
If no elements are present, raises a \exception{LookupError}.
\end{methoddesc}
\begin{methoddesc}{popleft}{}
Remove and return an element from the left side of the deque.
If no elements are present, raises a \exception{LookupError}.
\end{methoddesc}
\begin{methoddesc}{rotate}{n}
Rotate the deque \var{n} steps to the right. If \var{n} is
negative, rotate to the left. Rotating one step to the right
is equivalent to: \samp{d.appendleft(d.pop())}.
\end{methoddesc}
In addition to the above, deques support iteration, pickling, \samp{len(d)},
\samp{reversed(d)}, \samp{copy.copy(d)}, \samp{copy.deepcopy(d)}, and
membership testing with the \keyword{in} operator.
Example:
\begin{verbatim}
>>> 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']
>>> 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()
LookupError: pop from an empty deque
>>> d.extendleft('abc') # extendleft() reverses the input order
>>> d
deque(['c', 'b', 'a'])
\end{verbatim}
|
