Stack en queue wederzijds simuleren
Implementeer een queue met twee stacks en een stack met twee queues en leg de geamortiseerde kosten van elke aanpak uit.
Stack en queue wederzijds simuleren is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Waarom simuleer je het ene met het andere?
Een wachtrij met twee stapels en een stapel met twee wachtrijen implementeren zijn klassieke ontwerpvragen in sollicitatiegesprekken. Ze toetsen je begrip van de invarianten van beide datastructuren en je vermogen om de garantie van de ene structuur te handhaven met basisbewerkingen van een andere. Interviewers gebruiken deze vragen ook als opstap naar een bespreking van geamortiseerde complexiteit.
Het kerninzicht: stapels werken volgens LIFO en wachtrijen volgens FIFO. Om de ene structuur in de andere om te zetten, moet je de volgorde omkeren — en door een stapel naar een andere stapel over te brengen, ontstaat de oorspronkelijke invoegvolgorde, oftewel FIFO.
Wachtrij met twee stapels (uitgestelde aanpak)
De uitgestelde aanpak: gebruik een inbox-stapel voor toevoegingen en een outbox-stapel voor verwijderingen. Wanneer dequeue wordt aangeroepen, verplaats je, als outbox leeg is, alle elementen van inbox naar outbox — deze omkering herstelt de FIFO-volgorde. Als outbox niet leeg is, verwijder je er rechtstreeks een element uit. De verplaatsingen gebeuren uitgesteld, waardoor de O(n)-kosten van het verplaatsen over veel bewerkingen worden geamortiseerd.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3Geamortiseerde O(1)-analyse voor een wachtrij uit stapels
Elk element wordt hoogstens eenmaal van inbox naar outbox verplaatst. Omdat verwijderen uit outbox O(1) kost en verplaatsingen alleen plaatsvinden wanneer outbox leeg is, bedraagt het totale werk voor n toevoegingen en n verwijderingen hoogstens 2n stapelbewerkingen — in totaal O(n), dus geamortiseerd O(1) per bewerking. Dit betekent dat afzonderlijke bewerkingen in het slechtste geval O(n) kunnen kosten, maar dat het gemiddelde O(1) is.
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most nStapel met twee wachtrijen (uitgestelde pop)
Een stapel implementeren met twee wachtrijen is minder natuurlijk, omdat wachtrijen FIFO werken. De aanpak met een uitgestelde popbewerking: houd één hoofdwachtrij en één tijdelijke wachtrij bij. Voeg bij push een element toe aan de hoofdwachtrij (O(1)). Haal bij pop of peek alle elementen behalve het laatste naar de tijdelijke wachtrij, bewaar het laatste element en wissel daarna de wachtrijen om. Dit kost O(n) per pop, maar O(1) per push.
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2Stapel met één wachtrij (roteren bij push)
Een elegante implementatie met één wachtrij: voeg bij push het nieuwe element toe en roteer daarna de wachtrij zodat het nieuwe element vooraan staat. Roteren betekent dat je alle elementen die er vóór de push al stonden uit de wachtrij haalt en opnieuw toevoegt. Pop en peek zijn vervolgens O(1) (je hoeft alleen het voorste element te verwijderen of te bekijken). Push kost O(n) — precies de omgekeerde afweging van de versie met twee wachtrijen.
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2Samenvatting van de afwegingen: welke variant kies je?
Voor een wachtrij uit twee stapels: push O(1), pop/peek geamortiseerd O(1) — kies deze wanneer pop-bewerkingen vaak voorkomen. Voor een stapel uit twee wachtrijen: push O(1), pop O(n) — kies deze wanneer push-bewerkingen veel vaker voorkomen dan pop-bewerkingen. Voor een stapel uit één wachtrij: push O(n), pop O(1) — kies deze wanneer pop-bewerkingen overheersen. Benoem deze afwegingen expliciet tijdens een sollicitatiegesprek om te laten zien dat je verder denkt dan alleen 'het werkt'.
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')Waarom herstelt omkeren FIFO?
Wanneer de elementen 1, 2 en 3 op een stapel (inbox) worden geplaatst, liggen ze van onder naar boven in de volgorde 1, 2, 3. Door ze allemaal naar een tweede stapel (outbox) te verplaatsen, wordt de volgorde omgekeerd: in outbox ligt 3 onderaan en 1 bovenaan. Als je elementen uit outbox verwijdert, krijg je eerst 1, daarna 2 en vervolgens 3 — precies de volgorde waarin ze zijn toegevoegd. Daarom herstellen precies twee omkeringen (twee stapels) FIFO, terwijl één stapel LIFO oplevert.
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232: implementeer een wachtrij met stapels
LeetCode 232 is het directe probleem van een 'wachtrij uit twee stapels'. De verwachte oplossing is het uitgestelde overbrengen naar outbox. Leg tijdens een sollicitatiegesprek uit dat elk element hoogstens eenmaal van inbox naar outbox wordt verplaatst, waardoor alle bewerkingen geamortiseerd O(1) kosten. Vermeld dat afzonderlijke pop-aanroepen in het slechtste geval O(n) kunnen kosten wanneer outbox leeg is, maar dat het gemiddelde over n bewerkingen O(1) is.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225: implementeer een stapel met wachtrijen
LeetCode 225 is het probleem van een 'stapel uit wachtrijen'. De oplossing met één wachtrij waarbij je bij push roteert is het duidelijkst. Nadat je element x hebt toegevoegd, roteer je de wachtrij door alle elementen die er al stonden achter x te plaatsen. Dit kost O(n) per push, maar maakt top en pop O(1). Benoem de afweging en bevestig dat deze past bij de beperkingen, bijvoorbeeld een werklast met weinig push-aanroepen of veel pop-aanroepen.
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # FalseUitbreiden naar drie stacks in één array
Een verwante ontwerpopgave: implementeer drie stacks met één array. Een aanpak verdeelt de array in drie even grote vaste delen. Een flexibelere aanpak gebruikt afwisselende opslag met pointers, waarbij elke stack vanuit zijn eigen gebied groeit en elementen worden gekopieerd wanneer de grenzen elkaar raken. Dit toetst het beheer van dynamische arrays en komt aan bod in sollicitatiegesprekken voor seniorfuncties. De aanpak met vaste delen is eenvoudiger, maar verspilt ruimte als de stacks niet gelijkmatig groeien.
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30Belangrijkste punten: simulatiepatronen
De problemen met wederzijdse simulatie leren een breder principe: elke gegevensstructuur kan met voldoende tussenliggende buffering en omkering uit een andere worden opgebouwd. De kosten van de simulatie hangen af van welke bewerkingen je optimaliseert — je kunt push altijd O(1) maken of pop altijd O(1), maar beide O(1) maken vereist amortisering of meerdere hulpstructuren.
Vraag tijdens een sollicitatiegesprek altijd: "Welke bewerkingen komen vaker voor?" Dit helpt je de implementatievariant te kiezen en laat zien dat je op seniorniveau over operationele vereisten nadenkt.
Korte controle
Toets je begrip van de concepten uit de les van Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les heb je geleerd dat een queue uit twee stacks een geamortiseerde pop in O(1) bereikt door elementen pas van inbox naar outbox over te dragen wanneer dat nodig is, dat een stack uit één queue een pop in O(1) bereikt door de queue bij elke push te roteren (push in O(n)) en dat de keuze van de bewerking die je O(1) maakt afhangt van het gebruikspatroon. Hierna bekijken we de interne werking van hashmaps en de afhandeling van botsingen.
Leer Python 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
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Stack en queue wederzijds simuleren” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Stack en queue wederzijds simuleren”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Stack en queue wederzijds simuleren”?
Implementeer een queue met twee stacks en een stack met twee queues en leg de geamortiseerde kosten van elke aanpak uit. Je oefent met DSA Interview Prep 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 DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep 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 4 van 4.
Hoe lang duurt de les “Stack en queue wederzijds simuleren”?
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 DSA Interview Prep?
Ja. Elke les over DSA Interview Prep 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