DSA Interview Prep · Урок

Реализация очереди и дека

Создайте очередь с помощью deque Python, реализуйте кольцевую очередь и решите задачу поиска максимума в скользящем окне с помощью монотонного дека

«Реализация очереди и дека» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Структура данных «очередь»

Очередь — это структура данных, работающая по принципу «первым вошёл — первым вышел» (FIFO). Первый элемент, добавленный с помощью enqueue, извлекается с помощью dequeue первым — как человек, первым вставший в очередь в магазине. Основные операции — enqueue (add — добавить в конец) и dequeue (удалить из начала). Для эффективной работы очереди обе операции должны выполняться за O(1).

Использовать список Python как очередь заманчиво, но неправильно: list.pop(0) выполняется за O(n), поскольку все элементы приходится сдвигать. Правильный инструмент — collections.deque, который обеспечивает операции O(1) для appendleft, append, popleft и pop.

from collections import deque

queue = deque()

# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue)          # deque([10, 20, 30])

# Peek front
print('Front:', queue[0])       # 10

# Dequeue (remove from front)
print('Dequeued:', queue.popleft())  # 10
print('Queue after:', queue)         # deque([20, 30])

Класс Queue с использованием двусторонней очереди

Оберните deque в класс Queue с именованными операциями — именно этого ожидают интервьюеры. Внутри класса enqueue вызывает append, а dequeue вызывает popleft. Операция peek читает queue[0], не удаляя элемент.

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if self.is_empty():
            raise IndexError('dequeue from empty queue')
        return self._data.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty queue')
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek())     # 1
print(q.dequeue())  # 1
print(len(q))       # 2

BFS с очередью

Классическое применение очереди — поиск в ширину (BFS). Добавьте корень с помощью enqueue; пока очередь не пуста, извлекайте узел с помощью dequeue, обрабатывайте его и добавляйте в очередь его непосещённых соседей. Поскольку узлы обрабатываются уровень за уровнем, BFS естественным образом находит кратчайший путь в невзвешенном графе. В очереди всегда находятся узлы не более чем двух соседних уровней.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue   = deque([start])
    order   = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order

graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0))  # [0, 1, 2, 3, 4, 5]

Циклическая очередь (LeetCode 622)

LeetCode 622 «Проектирование циклической очереди»: реализуйте очередь фиксированной вместимости, которая замыкается в кольцо. Используйте массив размера k и два указателя: head и tail. Добавляйте элементы в хвост с помощью enqueue, удаляйте элементы из начала с помощью dequeue, а позиции вычисляйте по модулю k. Переменная для подсчёта отличает заполненную очередь от пустой (в противном случае в обоих случаях выполняется head == tail по модулю k).

class MyCircularQueue:
    def __init__(self, k):
        self.data  = [0] * k
        self.head  = 0
        self.tail  = 0
        self.count = 0
        self.k     = k

    def enQueue(self, value):
        if self.isFull(): return False
        self.data[self.tail] = value
        self.tail  = (self.tail + 1) % self.k
        self.count += 1
        return True

    def deQueue(self):
        if self.isEmpty(): return False
        self.head  = (self.head + 1) % self.k
        self.count -= 1
        return True

    def Front(self):
        return -1 if self.isEmpty() else self.data[self.head]

    def Rear(self):
        return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]

    def isEmpty(self): return self.count == 0
    def isFull(self):  return self.count == self.k

cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3))  # True True True
print(cq.enQueue(4))   # False (full)
print(cq.Rear())       # 3
print(cq.isFull())     # True
print(cq.deQueue())    # True
print(cq.enQueue(4))   # True

Максимум в скользящем окне с монотонной декой

LeetCode 239 «Максимум в скользящем окне»: для каждого окна размера k найдите максимальный элемент. Полный перебор занимает O(n*k). Подход за O(n) использует монотонную убывающую двустороннюю очередь, в которой хранятся индексы. Для каждого нового элемента удаляйте с начала индексы, вышедшие за пределы окна; затем удаляйте с конца индексы элементов с меньшими значениями (они уже никогда не смогут стать максимумом ни в одном будущем окне). В начале очереди всегда находится максимум.

from collections import deque

def maxSlidingWindow(nums, k):
    dq     = deque()   # stores indices, decreasing values
    result = []
    for i, n in enumerate(nums):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove smaller elements from back
        while dq and nums[dq[-1]] < n:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

Почему для очереди нужна двусторонняя очередь, а не просто список

list.pop(0) в Python удаляет первый элемент за O(n), поскольку каждый оставшийся элемент нужно сдвинуть на одну позицию влево. Для n вставок и n удалений это даёт общую сложность O(n²). collections.deque — это двусвязный список блоков фиксированного размера; popleft выполняется за O(1), поскольку изменяется только указатель. При BFS графа со 100 000 узлов разница между O(n) и O(n²) — это разница между 100 мс и 100 секундами.

import timeit

n = 10000

# Using list (O(n) per popleft)
list_time = timeit.timeit(
    stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
    globals={'n': n}, number=10
)

# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
    stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
    globals={'n': n, 'deque': deque}, number=10
)

print(f'List:  {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')

Поуровневый обход бинарного дерева (LeetCode 102)

LeetCode 102 «Поуровневый обход бинарного дерева»: верните все значения узлов, уровень за уровнем. Используйте очередь; в начале каждого уровня запишите размер очереди — это количество узлов на данном уровне. Извлеките ровно столько узлов, собрав их значения и добавив в очередь их дочерние узлы. Повторяйте эти действия, пока очередь не опустеет.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def levelOrder(root):
    if not root:
        return []
    result = []
    queue  = deque([root])
    while queue:
        level      = []
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root))  # [[3], [9, 20], [15, 7]]

Очередь с приоритетом на основе heapq

Модуль Python heapq предоставляет мин-кучу (очередь с приоритетом): наименьший элемент всегда извлекается первым. heapq.heappush(h, item) добавляет элемент за O(log n), а heapq.heappop(h) удаляет минимальный элемент за O(log n). Для таких задач, как алгоритм Дейкстры и задачи на поиск k наибольших элементов, heapq заменяет простую очередь.

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)

print('Min:', heapq.heappop(pq))  # 1
print('Min:', heapq.heappop(pq))  # 2
print('Min:', heapq.heappop(pq))  # 3

# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'Priority {priority}: {task}')

Шаблон обоев: очередь для лестницы слов

LeetCode 127 «Лестница слов»: найдите минимальное количество замен одного символа, необходимое для преобразования одного слова в другое, используя только слова из словаря. Представьте задачу в виде графа, где рёбра соединяют слова, отличающиеся одним символом. BFS на этом графе находит кратчайший путь (минимальное количество шагов) за O(n * L²), где n — размер словаря, а L — длина слова.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    queue    = deque([(beginWord, 1)])
    visited  = {beginWord}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + ch + word[i+1:]
                if new_word == endWord:
                    return steps + 1
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))
    return 0

print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog']))  # 5

Двусторонняя очередь

collections.deque — это двусторонняя очередь: вы можете эффективно добавлять и удалять элементы с обоих концов. Методы: appendleft и popleft — для начала; append и pop — для конца. Благодаря этому двусторонняя очередь может работать и как FIFO-очередь (добавление в конец и popleft), и как LIFO-стек (добавление и pop). При поиске максимума в скользящем окне используются оба конца: старые индексы удаляются слева, а меньшие значения — справа.

from collections import deque

dq = deque([3, 4, 5])

dq.appendleft(2)   # add to front: [2,3,4,5]
dq.appendleft(1)   # add to front: [1,2,3,4,5]
dq.append(6)       # add to rear:  [1,2,3,4,5,6]

print(dq.popleft())  # 1 (from front)
print(dq.pop())      # 6 (from rear)
print(list(dq))      # [2, 3, 4, 5]

Итоги: очередь, двусторонняя очередь и куча

Выбирайте подходящий инструмент для каждой задачи. Используйте простую очередь (двустороннюю очередь) для обработки в порядке FIFO и BFS. Используйте монотонную двустороннюю очередь, когда нужно найти максимум или минимум в скользящем окне: она поддерживает упорядоченное инвариантное условие, удаляя элементы, которые уже не могут стать ответом. Используйте очередь с приоритетом (heapq), когда нужно находить глобальный минимум или максимум независимо от порядка, например в алгоритме Дейкстры или задачах на поиск k наибольших элементов. Умение понимать, какой инструмент выбрать и почему, — важный навык, который проверяют на собеседованиях.

Быстрая проверка

Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке вы узнали, что collections.deque обеспечивает добавление и извлечение из очереди за O(1), поэтому является правильной реализацией очереди в Python, BFS использует очередь для обработки узлов по уровням и поиска кратчайших путей в невзвешенных графах, а убывающая монотонная двусторонняя очередь решает задачу поиска максимума в скользящем окне за O(n), удаляя элементы, которые уже не могут стать ответом. Далее мы подробно рассмотрим шаблон монотонного стека.

Часто задаваемые вопросы

Урок «Реализация очереди и дека» бесплатный?

Да — полный текст урока «Реализация очереди и дека» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Реализация очереди и дека»?

Создайте очередь с помощью deque Python, реализуйте кольцевую очередь и решите задачу поиска максимума в скользящем окне с помощью монотонного дека Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Реализация очереди и дека»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к DSA Interview Prep