Collections.deque: примеры (PYTHON)

Примеры использования

Пример создания deque с ограничением длины:

from collections import deque
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
print(d)
d.append(4)
print(d)

deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)

Использование методов appendleft и popleft:

from collections import deque
d = deque([2, 3, 4])
d.appendleft(1)
print(d)
left_item = d.popleft()
print(left_item)
print(d)

deque([1, 2, 3, 4])
1
deque([2, 3, 4])

Метод extendleft добавляет элементы в обратном порядке:

from collections import deque
d = deque([4, 5, 6])
d.extendleft([1, 2, 3])
print(d)

deque([3, 2, 1, 4, 5, 6])

Циклический сдвиг с помощью rotate:

from collections import deque
d = deque([1, 2, 3, 4, 5])
d.rotate(2)
print(d)
d.rotate(-3)
print(d)

deque([4, 5, 1, 2, 3])
deque([2, 3, 4, 5, 1])

Похожие структуры данных в Python

В Python есть несколько встроенных структур, которые могут выполнять схожие задачи, но с разными характеристиками производительности.

list:

Список (list) поддерживает операции добавления и удаления с конца (append, pop), но операции с началом списка (insert(0, x), pop(0)) имеют линейную сложность O(n). Deque выполняет эти операции за O(1). Для реализации стека (LIFO) список подходит хорошо, но для очереди (FIFO) deque эффективнее.

queue.Queue:

Модуль queue предоставляет класс Queue, который предназначен для многопоточного программирования. Он обеспечивает безопасность при работе с потоками, но может быть менее производительным в однопоточных сценариях по сравнению с deque.

queue.LifoQueue:

Этот класс реализует стек (последний вошел, первый вышел) с поддержкой многопоточности. Для однопоточных стеков проще использовать список или deque.

array.array:

Массив (array) хранит однотипные данные компактно, но не поддерживает быстрые операции с обоих концов. Он полезен при работе с большими объемами числовых данных.

Альтернативы в других языках программирования

JavaScript: Array

Массивы в JavaScript имеют методы push, pop, shift, unshift для работы с концами. Однако операции shift и unshift могут быть медленными при больших объемах данных, так как требуют переиндексации.

let deque = [2, 3, 4];
deque.unshift(1);
deque.push(5);
console.log(deque); // [1, 2, 3, 4, 5]
let first = deque.shift();
console.log(first); // 1
let last = deque.pop();
console.log(last); // 5

[1, 2, 3, 4, 5]
1
5

Java: ArrayDeque

Класс ArrayDeque реализует двустороннюю очередь и предоставляет методы addFirst, addLast, pollFirst, pollLast. Он не имеет фиксированной емкости и работает быстрее, чем LinkedList в большинстве сценариев.

import java.util.ArrayDeque;
ArrayDeque deque = new ArrayDeque<>();
deque.addLast(2);
deque.addFirst(1);
deque.addLast(3);
System.out.println(deque); // [1, 2, 3]
int first = deque.pollFirst();
System.out.println(first); // 1

[1, 2, 3]
1

Golang: list.List

Пакет container/list предоставляет двусвязный список, который может использоваться как двусторонняя очередь. Элементы имеют тип *list.Element, что обеспечивает гибкость, но требует приведения типов.

package main
import (
    "container/list"
    "fmt"
)
func main() {
    deque := list.New()
    deque.PushBack(2)
    deque.PushFront(1)
    deque.PushBack(3)
    fmt.Println(deque.Front().Value) // 1
    fmt.Println(deque.Back().Value)  // 3
}

1
3

PHP: SplDoublyLinkedList

Класс SplDoublyLinkedList может работать в режиме очереди, стека или итератора. Он предоставляет методы push, pop, shift, unshift.

$deque = new SplDoublyLinkedList();
$deque->push(2);
$deque->unshift(1);
$deque->push(3);
echo $deque->shift(); // 1
echo $deque->pop();   // 3

1
3

Типичные ошибки

Обращение к элементу по индексу с помощью квадратных скобок

Deque поддерживает индексацию, но это операция O(n) для средних элементов, а не O(1) как в списках. Частое обращение по индексу может снизить производительность.

from collections import deque
d = deque([1, 2, 3, 4, 5])
print(d[2])  # Работает, но медленно для длинных очередей

3

Попытка изменить maxlen после создания

Атрибут maxlen доступен только для чтения. Для изменения максимальной длины нужно создать новую очередь.

from collections import deque
d = deque([1, 2, 3], maxlen=5)
try:
    d.maxlen = 10
except AttributeError as e:
    print(f'Ошибка: {e}')

Ошибка: attribute 'maxlen' of 'collections.deque' objects is not writable

Использование extendleft с итератором

Метод extendleft добавляет элементы в обратном порядке, что иногда приводит к неожиданным результатам.

from collections import deque
d = deque([4, 5, 6])
d.extendleft([1, 2, 3])
print(d)  # Обратите внимание на порядок

deque([3, 2, 1, 4, 5, 6])

Изменения в последних версиях Python

В Python 3.7 у объекта deque появился метод reverse(), который разворачивает очередь на месте и возвращает None. Ранее для разворота требовалось создание новой очереди.

Начиная с Python 3.8, метод rotate() стал более эффективным для больших значений n за счет использования n % len(deque).

В Python 3.10 был добавлен метод copy(), который создает поверхностную копию deque. Ранее для копирования использовали конструктор deque(original_deque).

from collections import deque
d = deque([1, 2, 3])
d.reverse()
print(d)  # deque([3, 2, 1])
d_copy = d.copy()
print(d_copy)  # deque([3, 2, 1])

deque([3, 2, 1])
deque([3, 2, 1])

Расширенные примеры

Реализация кеша LRU (Least Recently Used)

from collections import deque

class LRUCache:
    def __init__(self, capacity):
        self.cache = {}
        self.order = deque(maxlen=capacity)
    
    def get(self, key):
        if key in self.cache:
            # Обновляем порядок использования
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            self.order.remove(key)
        self.cache[key] = value
        self.order.append(key)
        # Если deque автоматически удалил элемент из-за maxlen,
        # нужно удалить его и из кеша
        if len(self.order) == self.order.maxlen:
            # Проверяем, был ли удален элемент
            if key != self.order[0]:
                removed_key = self.order[0]
                del self.cache[removed_key]

cache = LRUCache(2)
cache.put(1, 'a')
cache.put(2, 'b')
print(cache.get(1))  # 'a'
cache.put(3, 'c')    # Ключ 2 удаляется, так как достигнут лимит
print(cache.get(2))  # -1

a
-1

Скользящее среднее с использованием deque

from collections import deque
import random

def moving_average(iterable, window_size):
    it = iter(iterable)
    window = deque(maxlen=window_size)
    # Заполняем окно начальными значениями
    for _ in range(window_size):
        window.append(next(it))
        yield sum(window) / len(window)
    # Обрабатываем остальные элементы
    for value in it:
        window.append(value)
        yield sum(window) / len(window)

values = [random.randint(1, 100) for _ in range(10)]
print('Значения:', values)
print('Скользящее среднее (окно 3):')
for avg in moving_average(values, 3):
    print(f'{avg:.2f}', end=' ')

Значения: [84, 67, 61, 12, 70, 24, 69, 72, 38, 32]
Скользящее среднее (окно 3):
84.00 75.50 70.67 46.67 47.67 35.33 54.33 55.00 59.67 47.33

Обработка потоковых данных

from collections import deque
import time

def stream_processor(stream, max_size):
    buffer = deque(maxlen=max_size)
    for item in stream:
        buffer.append(item)
        if len(buffer) == max_size:
            # Обрабатываем заполненный буфер
            yield list(buffer)

# Имитация потока данных
stream = (i for i in range(1, 11))
for window in stream_processor(stream, 4):
    print(f'Окно: {window}')
    time.sleep(0.1)

Окно: [1, 2, 3, 4]
Окно: [2, 3, 4, 5]
Окно: [3, 4, 5, 6]
Окно: [4, 5, 6, 7]
Окно: [5, 6, 7, 8]
Окно: [6, 7, 8, 9]
Окно: [7, 8, 9, 10]

Обход дерева в ширину (BFS) с использованием deque

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
    
    def add_child(self, node):
        self.children.append(node)

def bfs(root):
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node.value)
        queue.extend(node.children)
    return result

# Создание дерева
root = TreeNode(1)
child2 = TreeNode(2)
child3 = TreeNode(3)
child4 = TreeNode(4)
child5 = TreeNode(5)
root.add_child(child2)
root.add_child(child3)
child2.add_child(child4)
child3.add_child(child5)

print('BFS обход:', bfs(root))

BFS обход: [1, 2, 3, 4, 5]