all Python 3Algorithms & data structuresfunction

Queue

data structures

FIFO — first in, first out. Implemented with a deque. Uses: BFS and scheduling problems.

Syntax

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

The one reason to reach for deque instead of a list is list.pop(0): it shifts every remaining element, costs O(n) and turns a linear BFS into a quadratic one, while deque.popleft() is O(1). The trade-off is random access — indexing into the middle of a deque is also O(n), so it is a poor fit when you need arbitrary positions. For handing items between threads use queue.Queue, which adds blocking and waiting; deque has neither.

Examples

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

See also

Common errors

Open in the full glossarydocs.python.orgReport an inaccuracy