Implementacja kolejki i deque
Zbudują Państwo kolejkę za pomocą deque z Pythona, zaimplementują kolejkę cykliczną i rozwiążą problem maksimum w oknie przesuwnym z użyciem monotonicznego deque.
Implementacja kolejki i deque to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Struktura danych kolejki
Kolejka to struktura danych działająca zgodnie z zasadą first-in, first-out (FIFO). Pierwszy element dodany do kolejki jest pierwszym elementem z niej usuwanym — podobnie jak osoba stojąca pierwsza w kolejce do kasy. Podstawowe operacje to enqueue (dodanie na końcu) i dequeue (usunięcie z początku). Aby kolejka była wydajna, obie operacje muszą mieć złożoność O(1).
Użycie listy Pythona jako kolejki jest kuszące, ale niepoprawne: list.pop(0) ma złożoność O(n), ponieważ wszystkie pozostałe elementy są przesuwane. Właściwym narzędziem jest collections.deque, które zapewnia operacje appendleft, append, popleft i pop w czasie O(1).
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])Klasa Queue wykorzystująca deque
Należy opakować deque w klasę Queue z nazwanymi operacjami, aby odpowiadała oczekiwaniom rekruterów. Wewnątrz enqueue wywołuje append, a dequeue wywołuje popleft. Operacja peek odczytuje queue[0] bez usuwania elementu.
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)) # 2BFS z użyciem kolejki
Klasycznym zastosowaniem kolejki jest przeszukiwanie wszerz (Breadth-First Search, BFS). Należy dodać korzeń do kolejki; dopóki kolejka nie jest pusta, usuwać z niej węzeł, przetwarzać go i dodawać jego nieodwiedzonych sąsiadów. Ponieważ węzły są przetwarzane poziomami, BFS naturalnie znajduje najkrótszą ścieżkę w grafie nieważonym. Kolejka zawsze zawiera węzły z najwyżej dwóch sąsiednich poziomów.
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]Kolejka cykliczna (LeetCode 622)
LeetCode 622 „Design Circular Queue”: zaimplementowanie kolejki o stałej pojemności, która zawija się po osiągnięciu końca. Należy użyć tablicy o rozmiarze k i dwóch wskaźników: head oraz tail. Elementy należy dodawać na pozycji tail, usuwać z pozycji head, a pozycje obliczać modulo k. Zmienna count pozwala odróżnić kolejkę pełną od pustej (w przeciwnym razie w obu przypadkach head == tail modulo 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)) # TrueMaksimum w przesuwanym oknie za pomocą monotonicznej kolejki dwustronnej
LeetCode 239 „Sliding Window Maximum”: dla każdego okna o rozmiarze k należy znaleźć największy element. Naiwne rozwiązanie ma złożoność O(n*k). Rozwiązanie o złożoności O(n) wykorzystuje monotoniczną malejącą kolejkę dwustronną, która przechowuje indeksy. Dla każdego nowego elementu należy: usunąć z początku indeksy znajdujące się poza oknem; usunąć z końca indeksy o mniejszych wartościach (nie mogą już być maksimum w żadnym przyszłym oknie). Na początku kolejki zawsze znajduje się maksimum.
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]Dlaczego deque, a nie zwykła lista do kolejki?
Pythonowe list.pop(0) usuwa pierwszy element w czasie O(n), ponieważ każdy pozostały element musi przesunąć się o jedną pozycję w lewo. Dla n wstawień i n usunięć daje to łącznie O(n²). collections.deque jest dwukierunkową listą wiązaną złożoną z bloków o stałym rozmiarze; popleft ma złożoność O(1), ponieważ modyfikuje tylko wskaźnik. W przypadku BFS grafu zawierającego 10^5 węzłów różnica między O(n) a O(n²) może oznaczać różnicę między 100 ms a 100 sekundami.
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')Przechodzenie drzewa binarnego poziomami (LeetCode 102)
LeetCode 102 „Binary Tree Level Order Traversal”: zwrócenie wszystkich wartości węzłów poziomami. Należy użyć kolejki; na początku każdego poziomu zapisać rozmiar kolejki (czyli liczbę węzłów na tym poziomie). Następnie usunąć z kolejki dokładnie tyle węzłów, zebrać ich wartości i dodać ich dzieci. Powtarzać te czynności, aż kolejka będzie pusta.
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]]Kolejka priorytetowa z heapq
Moduł heapq języka Python udostępnia kopiec minimalny (kolejkę priorytetową): najmniejszy element jest zawsze pobierany jako pierwszy. heapq.heappush(h, item) dodaje element w czasie O(log n), a heapq.heappop(h) usuwa minimum w czasie O(log n). W zadaniach takich jak algorytm Dijkstry i problemy top-k moduł heapq zastępuje prostą kolejkę.
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}')Wzorzec algorytmiczny: kolejka dla Word Ladder
LeetCode 127 „Word Ladder”: należy znaleźć minimalną liczbę podstawień pojedynczych znaków potrzebnych do przekształcenia jednego słowa w inne, używając wyłącznie słów ze słownika. Należy zamodelować problem jako graf, w którym krawędzie łączą słowa różniące się jednym znakiem. BFS w tym grafie znajduje najkrótszą ścieżkę (minimalną liczbę kroków) w czasie O(n * L²), gdzie n oznacza rozmiar słownika, a L — długość słowa.
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'])) # 5deque jako kolejka dwustronna
collections.deque to kolejka dwustronna (deque): można efektywnie dodawać i usuwać elementy z obu końców. Metody appendleft i popleft służą do obsługi początku, a append i pop — końca. Dzięki temu deque może pełnić zarówno funkcję kolejki FIFO (appendright + popleft), jak i stosu LIFO (append + pop). Maksimum w przesuwanym oknie wykorzystuje oba końce: usuwa stare indeksy z lewej strony, a mniejsze wartości z prawej.
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]Podsumowanie: kolejka, deque czy kopiec
Należy wybrać narzędzie odpowiednie do problemu. Prosta kolejka (deque) służy do przetwarzania FIFO i BFS. Monotoniczny deque stosuje się wtedy, gdy potrzebne jest maksimum lub minimum w przesuwanym oknie — utrzymuje on uporządkowany niezmiennik, usuwając elementy zdominowane. Kolejkę priorytetową (heapq) należy wybrać, gdy potrzebne jest globalne minimum lub maksimum niezależnie od kolejności, na przykład w algorytmie Dijkstry lub problemach top-k. Umiejętność rozpoznania, którego narzędzia użyć i dlaczego, jest kluczową kompetencją sprawdzaną przez osoby przeprowadzające rozmowy techniczne.
Szybkie sprawdzenie
Proszę sprawdzić swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznano: collections.deque zapewnia operacje dodawania i usuwania elementów w czasie O(1), dzięki czemu jest właściwą implementacją kolejki w Pythonie, BFS używa kolejki do przetwarzania wierzchołków poziom po poziomie i znajdowania najkrótszych ścieżek w grafach nieważonych oraz monotoniczny deque malejący rozwiązuje problem maksimum w przesuwanym oknie w czasie O(n), usuwając zdominowane indeksy. Następnie szczegółowo omówimy wzorzec stosu monotonicznego.
Często zadawane pytania
Czy lekcja „Implementacja kolejki i deque” jest bezpłatna?
Tak — pełny tekst „Implementacja kolejki i deque” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Implementacja kolejki i deque”?
Zbudują Państwo kolejkę za pomocą deque z Pythona, zaimplementują kolejkę cykliczną i rozwiążą problem maksimum w oknie przesuwnym z użyciem monotonicznego deque. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Implementacja kolejki i deque”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Implementacja stosu i zastosowania
- Implementacja kolejki i deque
- Wzorzec stosu monotonicznego
- Wzajemna symulacja stosu i kolejki