Køer og collections.deque
Legg til og fjern elementer raskt fra begge ender
Køer og collections.deque er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Først inn, først ut
En kø behandler elementene i den rekkefølgen de kom inn, akkurat som en kø i en butikk. Det første elementet inn er det første ut.
Hvorfor ikke bruke en liste
En liste kan ta ut et element fra fronten, men pop(0) bruker O(n)-tid fordi alle de andre elementene må flyttes til venstre. Det er for tregt for store inndata.
q = []
q.pop(0) # O(n), avoid thisBli kjent med collections.deque
deque fra collections er en dobbeltendet kø som legger til og fjerner elementer fra begge ender på O(1)-tid. Det er førstevalget ditt i konkurranseprogrammering.
from collections import deque
q = deque()Legg til bakerst
Legg til nye elementer i høyre ende med append, akkurat som med en liste. Dette er baksiden av køen.
q.append(1)
q.append(2)Ta ut fra fronten
Fjern det eldste elementet fra venstre side med popleft. Operasjonen bruker konstant tid og gir ekte FIFO-oppførsel.
first = q.popleft() # returns 1Begge ender er åpne
En deque støtter også appendleft og pop fra høyre side. Denne fleksibiliteten lar én datastruktur fungere som både stakk og kø.
q.appendleft(0)
last = q.pop()Sjekk før du tar ut et element
Hvis du fjerner et element fra en tom deque, oppstår det en feil. Test derfor while q i løkker, slik at gjennomgangen forblir trygg.
while q:
x = q.popleft()Køer driver BFS
Den vanligste bruken i konkurranseprogrammering er BFS. Du legger en startnode i køen, tar deretter stadig ut elementet foran og legger naboene inn.
Et lite BFS-skjelett
Denne løkken besøker noder lag for lag. Hver nabo blir appended og behandles senere i den rekkefølgen de kom inn.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Begrens størrelsen på deque-en
Hvis du angir maxlen, forkaster en deque det eldste elementet når den er full. Det passer perfekt for glidende vinduer og sporing av nylig historikk.
window = deque(maxlen=3)Én struktur, mange roller
Husk at en deque er rask i begge ender. Bruk den derfor når du trenger en kø, en stakk eller en buffer for et glidende vindu.
Hurtigsjekk
Du trenger rask fjerning fra fronten av en kø. Hvilket valg er riktig?
Oppsummering: Deque er den raske køen
Du har blitt kjent med collections.deque: append og popleft for FIFO på O(1)-tid, åpne ender på begge sider og maxlen for vinduer. Den er selve grunnlaget for BFS. 🎯
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Køer og collections.deque» gratis?
Ja – hele teksten i «Køer og collections.deque» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Køer og collections.deque»?
Legg til og fjern elementer raskt fra begge ender Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Køer og collections.deque»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Stakker for samsvarende parenteser
- Monoton stakk: neste større element
- Køer og collections.deque
- Maksimum i et skyvevindu med deque