Implementering av kø og deque
Bygg en kø med Pythons deque, implementer en sirkulær kø og løs sliding-window maximum med en monoton deque.
Implementering av kø og deque er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 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 Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Datastrukturen kø
En kø er en datastruktur med først inn, først ut (FIFO). Det første elementet som legges i køen, er det første som tas ut – som en kø i en butikk. De viktigste operasjonene er enqueue (legge bakerst) og dequeue (ta ut forrest). Begge må være O(1) for at køen skal være effektiv.
Det kan virke fristende å bruke en Python-liste som kø, men det blir feil: list.pop(0) tar O(n) fordi alle elementene forskyves. Det riktige verktøyet er collections.deque, som gir O(1) for appendleft, append, popleft og pop.
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])Køklasse med deque
Pakk deque inn i en Queue-klasse med navngitte operasjoner, slik intervjuere forventer. Internt kaller enqueue på append, og dequeue kaller på popleft. Operasjonen peek leser queue[0] uten å fjerne elementet.
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 med en kø
Det klassiske bruksområdet for en kø er bredde-først-søk (BFS). Legg roten i køen; så lenge køen ikke er tom, tas en node ut, den behandles, og de ubesøkte naboene legges i køen. Fordi noder behandles nivå for nivå, finner BFS naturlig den korteste veien i en uvektet graf. Køen inneholder alltid noder fra høyst to tilstøtende nivåer.
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]Sirkulær kø (LeetCode 622)
LeetCode 622 «Utform sirkulær kø»: implementer en kø med fast kapasitet som går rundt. Bruk en array med størrelse k og to pekere: head og tail. Utfør enqueue ved tail, dequeue ved head, og beregn posisjonene modulo k. En count-variabel skiller mellom full og tom kø (ellers har begge 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 i et glidende vindu med monoton deque
LeetCode 239 «Maksimum i et glidende vindu»: finn maksimumselementet for hvert vindu med størrelse k. En uttømmende løsning tar O(n*k). Løsningen med O(n)-tid bruker en monoton avtakende deque som lagrer indekser. For hvert nye element fjernes indekser utenfor vinduet fra fronten; indekser med mindre verdier fjernes fra baksiden (de kan aldri bli maksimum i et fremtidig vindu). Fronten inneholder alltid maksimumet.
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]Hvorfor deque og ikke bare en liste som kø
Pythons list.pop(0) fjerner det første elementet på O(n), fordi hvert gjenværende element må forskyves én posisjon mot venstre. For n innsettinger og n slettinger gir dette totalt O(n²). collections.deque er en dobbeltlenket liste med blokker av fast størrelse; popleft tar O(1) fordi den bare justerer en peker. For BFS på en graf med 10^5 noder er forskjellen mellom O(n) og O(n²) forskjellen mellom 100 ms og 100 sekunder.
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')Nivåvis gjennomløping av et binærtre (LeetCode 102)
LeetCode 102 «Nivåvis gjennomløping av et binærtre»: returner alle nodeverdier nivå for nivå. Bruk en kø; ved starten av hvert nivå noterer De køens størrelse (det er antallet noder på dette nivået). Ta ut nøyaktig så mange noder, samle verdiene deres og legg barna deres i køen. Gjenta til køen er tom.
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]]Prioritetskø med heapq
Pythons heapq-modul tilbyr en min-heap (prioritetskø): Det minste elementet tas alltid først ut av køen. heapq.heappush(h, item) legger til et element i O(log n), og heapq.heappop(h) fjerner minimumselementet i O(log n). For oppgaver som Dijkstras algoritme og top-k-problemer erstatter heapq den enkle køen.
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}')Mønster i praksis: Kø for ordstige
LeetCode 127 «Word Ladder»: Finn det minste antallet enkelttegnsutskiftinger som kreves for å omforme ett ord til et annet, og bruk bare ord fra ordlisten. Modeller dette som en graf der kanter kobler sammen ord som skiller seg med ett tegn. BFS i denne grafen finner den korteste stien (minste antall trinn) i O(n * L²), der n er størrelsen på ordlisten og L er ordlengden.
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 som en dobbeltsidig kø
collections.deque er en dobbeltsidig kø (deque): Man kan effektivt legge til og fjerne elementer fra begge ender. Metodene appendleft og popleft brukes foran, mens append og pop brukes bak. Dermed kan deque fungere både som en FIFO-kø (appendright + popleft) og som en LIFO-stakk (append + pop). Maksimumet i et glidende vindu bruker begge endene: Fjern gamle indekser fra venstre og mindre verdier fra høyre.
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]Sammendrag: kø kontra deque kontra heap
Velg riktig verktøy for problemet. Bruk en enkel kø (deque) til FIFO-behandling og BFS. Bruk en monoton deque når De trenger maksimum eller minimum i et glidende vindu – den opprettholder en sorteringsinvariant ved å fjerne dominerte elementer. Bruk en prioritetskø (heapq) når De trenger det globale minimumet eller maksimumet uavhengig av rekkefølgen, for eksempel i Dijkstras algoritme eller top-k-problemer. Å vite hvilket verktøy man skal velge, og hvorfor, er en viktig ferdighet som testes i jobbintervjuer.
Hurtigsjekk
Test forståelsen av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De at collections.deque tilbyr innlegging og uttak fra køen i O(1), noe som gjør den til den riktige køimplementasjonen i Python, at BFS bruker en kø til å behandle noder nivå for nivå og finne korteste stier i uvektede grafer, og at en monoton synkende deque løser maksimumsproblemet for glidende vinduer i O(n) ved å fjerne dominerte indekser. Deretter utforsker vi mønsteret med monotone stabler i detalj.
Lær deg Forberedelse til kodeintervjuer 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
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Implementering av kø og deque» gratis?
Ja – hele teksten i «Implementering av kø og 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 Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Implementering av kø og deque»?
Bygg en kø med Pythons deque, implementer en sirkulær kø og løs sliding-window maximum med en monoton deque. Du øver på Forberedelse til kodeintervjuer 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 Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer 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 2 av 4.
Hvor lang tid tar leksjonen «Implementering av kø og 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 Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-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
- Implementering og bruksområder for stakk
- Implementering av kø og deque
- Mønsteret med monoton stakk
- Gjensidig simulering av stakk og kø