Queue-implementatie en deque
Bouw een queue met Python's deque, implementeer een circulaire queue en los sliding-window maximum op met een monotone deque.
Queue-implementatie en deque is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
De queuegegevensstructuur
Een queue is een first-in-first-out- (FIFO-)gegevensstructuur. Het eerste element dat je in de queue zet, is het eerste element dat je eruit haalt — net als bij een wachtrij bij de kassa. De belangrijkste bewerkingen zijn enqueue (achteraan toevoegen) en dequeue (vooraan verwijderen). Beide moeten O(1) kosten om de queue efficiënt te houden.
Een Python-list als queue gebruiken is verleidelijk maar verkeerd: list.pop(0) kost O(n), omdat alle elementen worden verschoven. Het juiste hulpmiddel is collections.deque, dat O(1) biedt voor appendleft, append, popleft en 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])Queueklasse met deque
Verpak deque in een Queue-klasse met benoemde bewerkingen, zoals interviewers verwachten. Intern roept enqueue append aan en roept dequeue popleft aan. De bewerking peek leest queue[0] zonder het element te verwijderen.
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 met een queue
De klassieke toepassing van een queue is breedte-eerst zoeken (BFS). Zet de wortel in de queue; zolang de queue niet leeg is, haal je een knooppunt uit de queue, verwerk je het en zet je de nog niet bezochte buren in de queue. Omdat knooppunten niveau voor niveau worden verwerkt, vindt BFS vanzelf het kortste pad in een ongerichte graaf. De queue bevat altijd knooppunten van hoogstens twee aangrenzende niveaus.
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]Circulaire queue (LeetCode 622)
LeetCode 622 'Een circulaire queue ontwerpen': implementeer een queue met vaste capaciteit die rondloopt. Gebruik een array met grootte k en twee pointers: head en tail. Voeg elementen toe bij tail, verwijder ze bij head en bereken posities modulo k. Een count-variabele maakt onderscheid tussen vol en leeg (anders geldt voor beide 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)) # TrueMaximum in een schuivend venster met een monotone deque
LeetCode 239 'Maximum in een schuivend venster': vind voor elk venster met grootte k het grootste element. De bruteforcebenadering kost O(n*k). De O(n)-aanpak gebruikt een monotoon dalende deque die indexen opslaat. Voor elk nieuw element: verwijder indexen buiten het venster aan de voorkant; verwijder indexen met kleinere waarden aan de achterkant (zij kunnen in geen enkel toekomstig venster meer het maximum zijn). Aan de voorkant staat altijd het maximum.
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]Waarom een deque en niet gewoon een list voor een queue?
list.pop(0) van Python verwijdert het eerste element in O(n), omdat elk overgebleven element één positie naar links moet worden verschoven. Voor n invoegingen en n verwijderingen levert dit in totaal O(n²) op. collections.deque is een dubbel gelinkte lijst van blokken met vaste grootte; popleft kost O(1), omdat alleen een pointer wordt aangepast. Bij BFS op een graaf met 10^5 knooppunten is het verschil tussen O(n) en O(n²) het verschil tussen 100 ms en 100 seconden.
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')Niveausgewijze doorloop van een binaire boom (LeetCode 102)
LeetCode 102 'Niveausgewijze doorloop van een binaire boom': geef alle waarden van de knooppunten niveau voor niveau terug. Gebruik een queue; noteer aan het begin van elk niveau de grootte van de queue (dat is het aantal knooppunten op dit niveau). Haal precies dat aantal knooppunten uit de queue, verzamel hun waarden en zet hun kinderen in de queue. Herhaal dit totdat de queue leeg is.
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]]Prioriteitswachtrij met heapq
De Python-module heapq biedt een min-heap (prioriteitswachtrij): het kleinste element wordt altijd als eerste uit de wachtrij gehaald. heapq.heappush(h, item) voegt een element toe in O(log n) en heapq.heappop(h) verwijdert het minimum in O(log n). Voor taken zoals het algoritme van Dijkstra en top-k-problemen vervangt heapq de eenvoudige wachtrij.
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}')Behangpatroon: wachtrij voor Word Ladder
LeetCode 127 'Word Ladder': zoek het minimale aantal vervangingen van één teken om het ene woord in het andere te veranderen, waarbij je alleen woorden uit het woordenboek gebruikt. Modelleer dit als een graaf waarin ribben woorden verbinden die één teken verschillen. BFS op deze graaf vindt het kortste pad (het minimale aantal stappen) in O(n * L²), waarbij n de grootte van het woordenboek is en L de woordlengte.
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 als dubbelzijdige wachtrij
collections.deque is een dubbelzijdige wachtrij (deque): je kunt efficiënt aan beide uiteinden elementen toevoegen en verwijderen. Methoden: appendleft en popleft voor de voorkant; append en pop voor de achterkant. Daardoor kan deque zowel dienen als een FIFO-wachtrij (appendright + popleft) als een LIFO-stapel (append + pop). Het maximum in een schuivend venster gebruikt beide uiteinden: verwijder oude indexen aan de linkerkant en kleinere waarden aan de rechterkant.
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]Samenvatting: wachtrij versus deque versus heap
Kies het juiste hulpmiddel voor het probleem. Gebruik een eenvoudige wachtrij (deque) voor FIFO-verwerking en BFS. Gebruik een monotone deque wanneer je het maximum of minimum in een schuivend venster nodig hebt — deze handhaaft een sorteereigenschap door elementen die niet meer kunnen winnen te verwijderen. Gebruik een prioriteitswachtrij (heapq) wanneer je het globale minimum of maximum nodig hebt, ongeacht de volgorde, bijvoorbeeld bij Dijkstra of top-k-problemen. Weten welk hulpmiddel je wanneer kiest en waarom is een belangrijke vaardigheid waarop interviewers je toetsen.
Korte toets
Toets je begrip van de concepten van Data Structures & Algorithms — Coding Interview Prep uit deze les.
Lesoverzicht
In deze les heb je geleerd: collections.deque biedt O(1)-bewerkingen voor toevoegen aan en verwijderen uit de wachtrij, waardoor dit de juiste wachtrij-implementatie in Python is, BFS gebruikt een wachtrij om knopen niveau voor niveau te verwerken en zo kortste paden in ongewogen grafen te vinden, en een monotone aflopende deque lost het maximum in een schuivend venster op in O(n) door indexen die niet meer kunnen winnen te verwijderen. Hierna bekijken we het patroon van de monotone stapel uitgebreid.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Queue-implementatie en deque” gratis?
Ja — de volledige tekst van “Queue-implementatie en deque” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Queue-implementatie en deque”?
Bouw een queue met Python's deque, implementeer een circulaire queue en los sliding-window maximum op met een monotone deque. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Queue-implementatie en deque”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Stackimplementatie en toepassingen
- Queue-implementatie en deque
- Patroon van de monotone stack
- Stack en queue wederzijds simuleren