Очереди и collections.deque
Быстро добавляйте и удаляйте элементы с обоих концов
«Очереди и collections.deque» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Первым вошёл — первым вышел
Очередь обслуживает элементы в порядке их появления, как очередь в магазине. Первый вошедший выходит первым.
Почему не стоит использовать список
Список умеет извлекать элемент с начала, но pop(0) работает за O(n), потому что все остальные элементы сдвигаются влево. Для больших входных данных это слишком медленно.
q = []
q.pop(0) # O(n), avoid thisПознакомьтесь с collections.deque
Двусторонняя очередь из collections позволяет добавлять и удалять элементы с обоих концов за O(1). Это основной инструмент на соревнованиях.
from collections import deque
q = deque()Добавляйте в конец
Добавляйте новые элементы в правый конец с помощью append, точно как в списке. Это конец очереди.
q.append(1)
q.append(2)Извлекайте из начала
Удаляйте самый старый элемент слева с помощью popleft. Операция выполняется за постоянное время и обеспечивает настоящее поведение FIFO.
first = q.popleft() # returns 1Оба конца доступны
Двусторонняя очередь также поддерживает appendleft и pop справа. Благодаря такой гибкости одна структура может работать как стек или очередь.
q.appendleft(0)
last = q.pop()Проверяйте перед извлечением
Удаление из пустой двусторонней очереди вызывает ошибку, поэтому в циклах проверяйте while q, чтобы обход оставался безопасным.
while q:
x = q.popleft()Очереди лежат в основе BFS
Самое распространённое применение на соревнованиях — BFS. Вы помещаете начальную вершину в очередь, затем извлекаете элементы спереди и добавляете их соседей.
Небольшой каркас BFS
Этот цикл посещает вершины послойно. Каждый сосед добавляется и позже обрабатывается в порядке поступления.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Ограничьте размер двусторонней очереди
Передача параметра maxlen заставляет двустороннюю очередь удалять самый старый элемент при заполнении. Это идеально подходит для скользящих окон и хранения недавней истории.
window = deque(maxlen=3)Одна структура — множество ролей
Помните, что двусторонняя очередь быстро работает с обоих концов, поэтому выбирайте её, когда Вам нужна очередь, стек или скользящий буфер.
Быстрая проверка
Вам нужно быстро удалять элементы из начала очереди. Какой вариант подходит?
Итоги: двусторонняя очередь — быстрая очередь
Вы познакомились с collections.deque: append и popleft обеспечивают FIFO за O(1), оба конца доступны, а maxlen подходит для окон. Это основа BFS. 🎯
Часто задаваемые вопросы
Урок «Очереди и collections.deque» бесплатный?
Да — полный текст урока «Очереди и collections.deque» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Очереди и collections.deque»?
Быстро добавляйте и удаляйте элементы с обоих концов Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Очереди и collections.deque»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Стеки для сопоставления скобок
- Монотонный стек: следующий больший элемент
- Очереди и collections.deque
- Максимум в скользящем окне с деком