Køer og collections.deque
Indsæt og fjern hurtigt fra begge ender
Køer og collections.deque er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Først ind, først ud
En kø behandler elementer i den rækkefølge, de ankom i, ligesom en kø i en butik. Det første element, der kommer ind, er det første, der kommer ud.
Hvorfor ikke bruge en liste
En liste kan fjerne det første element, men pop(0) tager O(n)-tid, fordi alle andre elementer flyttes én plads til venstre. Det er for langsomt ved store input.
q = []
q.pop(0) # O(n), avoid thisMød collections.deque
deque fra collections er en dobbeltsidet kø, der kan tilføje og fjerne elementer fra begge ender på O(1)-tid. Den er dit foretrukne valg i konkurrencer.
from collections import deque
q = deque()Sæt ind bagest
Tilføj nye elementer i højre side med append, præcis som med en liste. Det er køens bagende.
q.append(1)
q.append(2)Fjern fra fronten
Fjern det ældste element fra venstre side med popleft. Det tager konstant tid og giver ægte FIFO-adfærd.
first = q.popleft() # returns 1Begge ender er åbne
En deque understøtter også appendleft og pop fra højre side. Denne fleksibilitet lader den samme datastruktur fungere som både stak og kø.
q.appendleft(0)
last = q.pop()Tjek før du fjerner
Hvis du fjerner et element fra en tom deque, opstår der en fejl. Test derfor while q i loops, så din gennemgang forbliver sikker.
while q:
x = q.popleft()Køer driver BFS
Den mest almindelige anvendelse i konkurrencer er BFS. Du sætter en startknude i køen, tager derefter løbende det forreste element ud og sætter dets naboer i køen.
En lille BFS-skeletkode
Denne loop besøger knuder lag for lag. Hver nabo bliver tilføjet og behandlet senere i den rækkefølge, de ankom i.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Begræns deque-størrelsen
Hvis du angiver maxlen, fjerner en deque det ældste element, når den er fuld. Det er perfekt til glidende vinduer og sporing af den seneste historik.
window = deque(maxlen=3)Én datastruktur, mange roller
Husk, at en deque er hurtig i begge ender, så brug den, når du har brug for en kø, en stak eller en glidende buffer.
Hurtigt tjek
Du har brug for hurtig fjernelse fra fronten af en kø. Hvilket valg er det rigtige?
Opsummering: Deque er den hurtige kø
Du har mødt collections.deque: append og popleft til O(1) FIFO, åbne ender i begge sider og maxlen til vinduer. Den er grundlaget for BFS. 🎯
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Køer og collections.deque” gratis?
Ja — hele teksten til “Køer og collections.deque” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Køer og collections.deque”?
Indsæt og fjern hurtigt fra begge ender Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Køer og collections.deque”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Stakke til matchende parenteser
- Monoton stack: næste større element
- Køer og collections.deque
- Maksimum i et glidende vindue med deque