Implementering af kø og deque
Opbyg en kø med Pythons deque, implementer en cirkulær kø, og løs sliding-window maximum med en monoton deque.
Implementering af kø og deque er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Kødatastrukturen
En kø er en datastruktur efter princippet først ind, først ud (FIFO). Det første element, der lægges i køen, er det første, der tages ud — ligesom en kø ved kassen i en butik. De grundlæggende operationer er enqueue (tilføj bagest) og dequeue (fjern forrest). Begge skal tage O(1), for at køen kan være effektiv.
Det kan være fristende, men er forkert, at bruge en Python-liste som kø: list.pop(0) tager O(n), fordi alle elementer skal flyttes. Det rigtige værktøj er collections.deque, som giver 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
Pak deque ind i en Queue-klasse med navngivne operationer, så den svarer til det, interviewere forventer. Internt kalder enqueue append, og dequeue kalder popleft. Operationen peek læser queue[0] uden at 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ø
Den klassiske anvendelse af en kø er bredde-først-søgning (BFS). Læg roden i køen; mens køen ikke er tom, tager du en node ud, behandler den og lægger dens ubesøgte naboer i køen. Fordi noderne behandles niveau for niveau, finder BFS naturligt den korteste vej i en uvægtet graf. Køen indeholder altid noder fra højst to tilstødende niveauer.
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]Cirkulær kø (LeetCode 622)
LeetCode 622 'Udformning af cirkulær kø': implementér en kø med fast kapacitet, der går rundt fra slutningen til begyndelsen. Brug et array med størrelsen k og to pointere: head og tail. Læg elementer i køen ved tail, tag dem ud ved head, og beregn positioner modulo k. En count-variabel skelner mellem fuld og tom (begge har ellers 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 vindue med monoton deque
LeetCode 239 'Maksimum i et glidende vindue': find det største element for hvert vindue med størrelsen k. En naiv løsning tager O(n*k). Tilgangen med O(n) bruger en monoton faldende deque, der gemmer indekser. For hvert nyt element skal du fjerne indekser uden for vinduet fra forenden og fjerne indekser med mindre værdier fra bagenden (de kan aldrig være maksimum i et fremtidigt vindue). Forenden indeholder altid maksimum.
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 til en kø?
Pythons list.pop(0) fjerner det første element i O(n), fordi hvert resterende element skal flyttes én position til venstre. For n indsættelser og n sletninger giver det i alt O(n²). collections.deque er en dobbeltlænket liste af blokke med fast størrelse; popleft tager O(1), fordi den kun justerer en pointer. Ved BFS på en graf med 10^5 noder er forskellen mellem O(n) og O(n²) forskellen mellem 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')Niveauvist gennemløb af binært træ (LeetCode 102)
LeetCode 102 'Niveauvist gennemløb af binært træ': returnér alle nodeværdier niveau for niveau. Brug en kø; ved begyndelsen af hvert niveau registrerer du køens størrelse (det er antallet af noder på dette niveau). Tag præcis så mange noder ud af køen, saml deres værdier, og læg deres børn i køen. Gentag, indtil 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 tilbyder en min-heap (prioritetskø): Det mindste element tages altid ud først. heapq.heappush(h, item) tilføjer et element i O(log n), og heapq.heappop(h) fjerner minimumselementet i O(log n). Til opgaver som Dijkstras algoritme og top-k-problemer erstatter heapq den simple kø.
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 fokus: kø til Word Ladder
LeetCode 127 'Word Ladder': Find det mindste antal udskiftninger af et enkelt tegn for at omdanne ét ord til et andet, hvor du kun må bruge ord fra ordbogen. Modellér problemet som en graf, hvor kanter forbinder ord, der adskiller sig med ét tegn. BFS i denne graf finder den korteste sti (det mindste antal trin) i O(n * L²), hvor n er ordbogens størrelse, og L er ordlængden.
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 dobbeltsidet kø
collections.deque er en dobbeltsidet kø (deque): Du kan effektivt tilføje og fjerne elementer fra begge ender. Metoderne appendleft og popleft bruges til forenden, mens append og pop bruges til bagenden. Det gør, at deque kan fungere både som en FIFO-kø (appendright + popleft) og som en LIFO-stak (append + pop). Maksimum i et glidende vindue bruger begge ender: Fjern gamle indekser fra venstre og mindre værdier fra højre.
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]Opsummering: kø vs. deque vs. heap
Vælg det rette værktøj til problemet. Brug en simpel kø (deque) til FIFO-behandling og BFS. Brug en monoton deque, når du har brug for maksimum eller minimum i et glidende vindue — den opretholder en sorteret invariant ved at fjerne dominerede elementer. Brug en prioritetskø (heapq), når du har brug for det globale minimum eller maksimum uanset rækkefølgen, f.eks. i Dijkstras eller top-k-problemer. At vide, hvilket værktøj du skal vælge, og hvorfor, er en vigtig færdighed, som interviewere afprøver.
Hurtigt tjek
Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du: collections.deque giver O(1)-indsættelse i køen og fjernelse fra køen, hvilket gør den til den korrekte køimplementering i Python, BFS bruger en kø til at behandle knuder niveau for niveau og finde korteste veje i uvægtede grafer, og en monoton faldende deque løser maksimum i et glidende vindue i O(n) ved at fjerne dominerede indekser. Dernæst går vi i dybden med mønsteret monoton stak.
Lær Python 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
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Implementering af kø og deque” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Implementering af kø og deque”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Implementering af kø og deque”?
Opbyg en kø med Pythons deque, implementer en cirkulær kø, og løs sliding-window maximum med en monoton deque. Du øver dig i DSA Interview Prep 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å DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep 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 2 af 4.
Hvor lang tid tager lektionen “Implementering af kø og 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 DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-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
- Implementering og anvendelse af stacks
- Implementering af kø og deque
- Mønsteret med monoton stack
- Gensidig simulering af stack og kø