Python TutorialGetting Started with PythonPython Basic SyntaxPython DatatypesPython IndentationPython Collection TypesPython Basic Input and OutputPython Built in Modules and FunctionsPython FunctionsChemPy - python packageCreating Python packagesFunctional Programming in PythonIncompatibilities moving from Python 2 to Python 3IoT Programming with Python and Raspberry PIKivy - Cross-platform Python Framework for NUI DevelopmentMutable vs Immutable (and Hashable) in PythonPyInstaller - Distributing Python CodePython *args and **kwargsPython 2to3 toolPython Abstract Base Classes (abc)Python Abstract syntax treePython Alternatives to switch statement from other languagesPython and ExcelPython Anti-PatternsPython ArcPyPython ArraysPython Asyncio ModulePython Attribute AccessPython AudioPython Binary DataPython Bitwise OperatorsPython Boolean OperatorsPython Checking Path Existence and PermissionsPython ClassesPython CLI subcommands with precise help outputPython Code blocks, execution frames, and namespacesPython Collections modulePython Comments and DocumentationPython Common PitfallsPython Commonwealth ExceptionsPython ComparisonsPython Complex mathPython concurrencyPython ConditionalsPython configparserPython Context Managers (with Statement)Python Copying dataPython CountingPython ctypesPython Data SerializationPython Data TypesPython Database AccessPython Date and TimePython Date FormattingPython DebuggingPython DecoratorsPython Defining functions with list argumentsPython DeploymentPython Deque ModulePython DescriptorPython Design PatternsPython DictionaryPython Difference between Module and PackagePython DistributionPython DjangoPython Dynamic code execution with `exec` and `eval`Python EnumPython ExceptionsPython ExponentiationPython Files & Folders I/OPython FilterPython FlaskPython Functools ModulePython Garbage CollectionPython GeneratorsPython getting start with GZipPython graph-toolPython groupby()Python hashlibPython HeapqPython Hidden FeaturesPython HTML ParsingPython HTTP ServerPython IdiomsPython ijsonPython Immutable datatypes(int, float, str, tuple and frozensets)Python Importing modulesPython Indexing and SlicingPython Input, Subset and Output External Data Files using PandasPython Introduction to RabbitMQ using AMQPStorm

Python Deque Module

From WikiOD

Syntax[edit | edit source]

  • 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

Parameters[edit | edit source]

Parameter Details
iterable Creates the deque with initial elements copied from another iterable.
maxlen Limits how large the deque can be, pushing out old elements as new are added.

Remarks[edit | edit source]

This class is useful when you need an object similar to a list that allows fast append and pop operations from either side (the name deque stands for “double-ended queue”).

The methods provided are indeed very similar, except that some like pop, append, or extend can be suffixed with left. The deque data structure should be preferred to a list if one needs to frequently insert and delete elements at both ends because it allows to do so in constant time O(1).

Basic deque using[edit | edit source]

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])

Available methods in deque[edit | edit source]

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])

limit deque size[edit | edit source]

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[edit | edit source]

The Deque is the only Python data structure with fast Queue operations. (Note queue.Queue isn't normally suitable, since it's meant for communication between threads.) 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.
    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}