Kolejki i collections.deque
Szybkie dodawanie i usuwanie z obu końców
Kolejki i collections.deque to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Pierwszy wchodzi, pierwszy wychodzi
Kolejka obsługuje elementy w kolejności ich przybycia, podobnie jak kolejka w sklepie. Pierwszy dodany element jest pierwszym usuwanym.
Dlaczego nie użyć listy
Lista może usuwać element z początku, ale pop(0) działa w czasie O(n), ponieważ każdy pozostały element przesuwa się w lewo. Przy dużych danych jest to zbyt wolne.
q = []
q.pop(0) # O(n), avoid thisPoznaj collections.deque
deque z modułu collections to kolejka dwustronna, która dodaje i usuwa elementy z obu końców w czasie O(1). To podstawowe narzędzie w konkursach programistycznych.
from collections import deque
q = deque()Dodawanie na końcu
Dodawaj nowe elementy na prawym końcu za pomocą append, dokładnie tak jak w przypadku listy. To jest koniec kolejki.
q.append(1)
q.append(2)Usuwanie z początku
Usuwaj najstarszy element z lewej strony za pomocą popleft. Operacja działa w czasie stałym i zapewnia prawdziwą kolejność FIFO.
first = q.popleft() # returns 1Oba końce są dostępne
Deque obsługuje także appendleft oraz pop z prawej strony. Ta elastyczność pozwala jednej strukturze działać jak stos albo kolejka.
q.appendleft(0)
last = q.pop()Sprawdzaj przed usunięciem
Usunięcie elementu z pustego deque powoduje błąd, dlatego w pętlach należy sprawdzać while q, aby przechodzenie było bezpieczne.
while q:
x = q.popleft()Kolejki napędzają BFS
Najczęstszym zastosowaniem w konkursach jest BFS. Dodaje się wierzchołek początkowy do kolejki, a następnie zdejmuje element z początku i dodaje jego sąsiadów.
Minimalny szkielet BFS
Ta pętla odwiedza wierzchołki warstwa po warstwie. Każdy sąsiad zostaje dodany, a później przetworzony w kolejności przybycia.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Ogranicz rozmiar deque
Przekazanie parametru maxlen sprawia, że pełny deque usuwa najstarszy element. Jest to idealne rozwiązanie dla okien przesuwnych i śledzenia najnowszej historii.
window = deque(maxlen=3)Jedna struktura, wiele zastosowań
Warto pamiętać, że deque działa szybko na obu końcach, więc należy po niego sięgać zawsze, gdy potrzebna jest kolejka, stos albo bufor przesuwny.
Szybkie sprawdzenie
Potrzebne jest szybkie usuwanie elementów z początku kolejki. Który wybór jest właściwy?
Podsumowanie: deque to szybka kolejka
Poznali Państwo collections.deque: append i popleft zapewniają FIFO w czasie O(1), oba końce są dostępne, a maxlen służy do obsługi okien. To podstawa algorytmu BFS. 🎯
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Kolejki i collections.deque” jest bezpłatna?
Tak — pełny tekst „Kolejki i collections.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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Kolejki i collections.deque”?
Szybkie dodawanie i usuwanie z obu końców Ćwiczysz Coding 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding 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 3 z 4.
Ile czasu zajmuje lekcja „Kolejki i collections.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 Coding Interview Prep?
Tak. Każda lekcja Coding 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
- Stosy do dopasowywania nawiasów
- Stos monotoniczny: następny większy element
- Kolejki i collections.deque
- Maksimum w przesuwanym oknie za pomocą deque