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
127
128
129
130
131
132
|
\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{IndexError}.
\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{IndexError}.
\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)},
membership testing with the \keyword{in} operator, and subscript references
such as \samp{d[-1]}.
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']
>>> 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'])
\end{verbatim}
|
