Модуль deque

Введение

Примеры

  • 3

    Основное использование deque

    Основные методы, которые полезны с этим классом являются popleft и 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]) 
  • 1

    ограничение размера deque

    Используйте maxlen параметр при создании 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) 
  • 2

    Доступные методы в deque

    Создание пустой декы:

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

    Создание дек с некоторыми элементами:

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

    Добавление элемента в deque:

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

    Добавление элемента левой стороны deque:

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

    Добавление списка элементов в deque:

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

    Добавление списка элементов с левой стороны:

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

    Использование .pop() элемента естественно удалить элемент с правой стороны:

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

    Используя .popleft() элемент , чтобы удалить элемент с левой стороны:

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

    Удалить элемент по его значению:

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

    Обратный порядок элементов в deque:

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

    Ширина Первый Поиск

    Deque является единственной структурой данных Python с быстрой Очереди операций . (Примечание queue.Queue обычно не подходит, так как он предназначен для связи между потоками.) Основной случай использования из очереди является поиск в ширину .

     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
    
     

    Скажем, у нас есть простой ориентированный граф:

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

    Теперь мы можем найти расстояния от некоторой начальной позиции:

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

Синтаксис

Параметры

Примечания