Kolejki i collections.deque
Szybkie dodawanie i usuwanie z obu końców
Kolejki i collections.deque to bezpłatna lekcja Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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ę Python 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
- 30
- Lekcje
- 120
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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Kolejki i collections.deque”?
Szybkie dodawanie i usuwanie z obu końców Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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