все Python 3Алгоритмы и структуры данныхфункция

Очередь (queue)

структуры

FIFO — первый вошёл, первый вышел. Реализуется через deque. Применения: BFS, задачи планирования.

Синтаксис

from collections import deque
queue = deque()
queue.append(x)   # enqueue
queue.popleft()   # dequeue

Причина брать deque, а не список, одна: list.pop(0) сдвигает все оставшиеся элементы и стоит O(n), превращая линейный BFS в квадратичный, тогда как deque.popleft() — O(1). Расплата — случайный доступ: обращение к середине deque по индексу тоже O(n), так что для произвольных позиций он не годится. А для передачи данных между потоками нужен не deque, а queue.Queue — с блокировкой и ожиданием.

Примеры

from collections import deque
queue = deque()
queue.append('a')
queue.append('b')
queue.append('c')
print(queue.popleft())  # → a
print(queue.popleft())  # → b
print(queue)  # → deque(['c'])

from collections import deque
# BFS обход графа
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order
g = {1:[2,3],2:[4],3:[4],4:[]}
print(bfs(g, 1))  # → [1,2,3,4]

# queue.Queue (потокобезопасный)
import queue
q = queue.Queue()
q.put(1); q.put(2)
print(q.get())  # → 1
print(q.qsize())  # → 1

# Скользящее окно максимума
from collections import deque
def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i-k: dq.popleft()
        if i >= k-1: result.append(nums[dq[0]])
    return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # → [3,3,5,5,6,7]

from collections import deque
import queue
# Задача Джозефуса
def josephus(n, k):
    queue = deque(range(1, n+1))
    while len(queue) > 1:
        for _ in range(k-1):
            queue.append(queue.popleft())
        queue.popleft()
    return queue[0]
print(josephus(7, 3))  # → 4

См. также

Частые ошибки

Открыть в полном глоссарииdocs.python.orgСообщить о неточности