deque module

suggest change

Deque (double-ended queue) is a list that allows fast adding and removing an item from both the beginning and the end of the list. In a traditional list only adding/removing at the end is fast.

Name	description
dq = deque()	Creates an empty deque
dq = deque(iterable)	Creates a deque with some elements
dq.append(object)	Adds object to the right of the deque
dq.appendleft(object)	Adds object to the left of the deque
dq.pop() -> object	Removes and returns the right most object
dq.popleft() -> object	Removes and returns the left most object
dq.extend(iterable)	Adds some elements to the right of the deque
dq.extendleft(iterable)	Adds some elements to the left of the deque

Basic use

The main methods that are useful with this class are popleft and appendleft

from collections import deque

d = deque([1, 2, 3])
p = d.popleft()        # p = 1, d = deque([2, 3])
d.appendleft(5)        # d = deque([5, 2, 3])

Limit deque size

Use the maxlen parameter while creating a deque to limit the size of the deque:

from collections import deque
d = deque(maxlen=3)  # only holds 3 items
d.append(1)  # deque([1])
d.append(2)  # deque([1, 2])
d.append(3)  # deque([1, 2, 3])
d.append(4)  # deque([2, 3, 4]) (1 is removed because its maxlen is 3)

Breadth First Search

A basic use case of a Queue is the breadth first search:

from collections import deque

def bfs(graph, root):
    distances = {}
    distances[root] = 0
    q = deque([root])
    while q:
        # The oldest seen (but not yet visited) node will be the left most one.
        current = q.popleft()
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                # When we see a new node, we add it to the right side of the queue.
                q.append(neighbor)
    return distances

Say we have a simple directed graph:

graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}

We can now find the distances from some starting position:

>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}

Available methods in deque

Creating empty deque:

dl = deque()  # deque([]) creating empty deque

Creating deque with some elements:

dl = deque([1, 2, 3, 4])  # deque([1, 2, 3, 4])

Adding element to deque:

dl.append(5)  # deque([1, 2, 3, 4, 5])

Adding element left side of deque:

dl.appendleft(0)  # deque([0, 1, 2, 3, 4, 5])

Adding list of elements to deque:

dl.extend([6, 7])  # deque([0, 1, 2, 3, 4, 5, 6, 7])

Adding list of elements to from the left side:

dl.extendleft([-2, -1])  # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])

Using .pop() element will naturally remove an item from the right side:

dl.pop()  # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

Using .popleft() element to remove an item from the left side:

dl.popleft()  # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])

Remove element by its value:

dl.remove(1)  # deque([-2, 0, 2, 3, 4, 5, 6])

Reverse the order of the elements in deque:

dl.reverse()  # deque([6, 5, 4, 3, 2, 0, -2])

Found a mistake? Have a question or improvement idea? Let me know.

deque module:

* Basic use

* Limit deque size

* Breadth First Search

* Available methods in deque

Table Of Contents

0 Getting Started

1 List comprehension

2 Filter

3 List

4 Functions

5 Decorators

6 Math module

7 Loops

8 Random module

9 Comparisons

10 Importing modules

11 Sorting Minimum and Maximium

12 Operator module

13 Variable Scope and Binding

14 Basic Input and Output

15 Files, Folders, I/O

16 JSON Module

17 String Methods

18 Metaclasses

19 Indexing and Slicing

20 Generators

21 Simple Mathematical Operators

22 Reduce

23 Map Function

24 Exponentation

25 Searching

26 Dictionary

27 Classes

28 Counting

29 Manipulating XML

30 Date and Time

31 Set

32 Collections module

33 Parallel computation

34 Multithreading

35 Writing C extensions

36 Unit Testing

37 Regular Expressions

38 Bitwise Operators

39 Incompatibilities moving from Python 2 to Python 3

40 Virtual environments

41 Copying data

42 Tuple

43 Context Managers with Statement

44 Hidden Features

45 Enum

46 String Formatting

47 Conditionals

48 Complex math

49 Unicode and bytes

50 The __name__ special variable

51 Check if path exists

52 Networking

53 Asyncio Module

54 Print Function

55 os.path module

56 Creating Python packages

57 Parsing Command Line Arguments

58 HTML Parsing

59 Subprocess Library

60 setup.py

61 List slicing

62 Sockets

63 Itertools Module

64 Recursion

65 Boolean Operators

66 dis module

67 Type Hints

68 pip PyPI Package Manager

69 locale module

70 Exceptions

71 Web scraping

72 deque module

73 Distributing self-contained applications

74 Property Objects

75 Overloading

76 Debugging

77 Reading and Writing CSV

78 Dynamic code execution with exec and eval

79 PyInstaller - Distributing Python Code

80 Iterables and Iterators

81 Data Visualization

82 The interpreter command line console

83 args and kwargs

84 functools module

85 Garbage Collection

86 Indentation

87 Security and Cryptograhy

88 Pickle data serialization

89 urllib

90 Binary Data

91 Python and Excel

92 Idioms

93 Method Overriding

94 Difference between a module and a package

95 Data Serialization

96 Python Concurrency

97 RabbitMQ using AMQPStorm

98 PostgreSQL

99 Descriptor

100 Common Pitfalls

101 Multiprocessing

102 Creating temporary files with tempfile

103 Working with ZIP files

104 Stack

105 Profiling

106 User-Defined Methods

107 Working around Global Interpreter Lock

108 Deployment using conda

109 Logging

110 Processes and Threads

111 os module

112 Comments and documentation

113 Database Access

114 Python HTTP Server

115 Alternatives to switch statement from other languages

116 List destructuring

117 Accessing Python source code and bytecode

118 Mixins

119 Attribute Access

120 ArcPy

121 Python Anti-Patterns

122 Plugin and Extension Classes

123 Websockets

124 Immutable data types

125 String representations of class

126 Arrays

127 Operator Precedence

128 Polymorphism

129 Alternative Python implementations

130 List Comprehensions

131 Web Server Gateway Intrerface WSGI

132 2to3 tool

133 Abstract Syntax Tree

134 Abstract Base Classes

135 Unicode

136 ssh in Python

137 Serial Communication with pyserial

138 Neo4j

139 Performance optimization

140 Curses

141 Templates

142 pass statement

143 Testing with py.test

144 Date Formatting

145 heapq

146 tkinter

147 CLI subcommands

148 Defining functions with list arguments

149 SQLite3 module

150 Persistence with pickle

151 Connecting to SQL Server

152 Design Patterns

153 Multidimensional arrays

154 Audio

155 pyglet

156 queue module

157 ijson

158 webbrowser module

159 base64 module

160 Flask

161 Groupby

162 Sockets and Message Encryption / Decryption

163 pygame

164 Input Subset and Output External Data Files using Pandas

165 hashlib

166 Gzip

167 ctypes

168 Creating a Windows Service

169 Mutable vs. Immutable

170 configparser

171 Common Exceptions

172 Optical Character Recognition OCR

173 Python Data Types

174 Partial functions

175 Generating graphs

176 Unzipping Files

177 Functional Programming

178 Python Virtual Environment - virtualenv

179 sys module

180 virtual environment with virtualenvwrapper

181 virtualenvwrapper on Windows

182 Python Requests Post

183 Plotting with Matplotlib

184 Python Lex-Yacc

185 pyaudio

186 shelve

187 pip and PyPI Package Manager

188 Writing to CSV from String or List

189 Raise Custom Errors Exceptions

190 Using loops within functions

191 Contributors