Ömsesidig simulering av stack och kö
Implementera en kö med två stackar och en stack med två köer och förklara den amortiserade kostnaden för varje metod.
Ömsesidig simulering av stack och kö är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Varför simulera den ena med den andra?
Att implementera en kö med två stackar och en stack med två köer är klassiska designfrågor på tekniska intervjuer. De testar din förståelse av båda datastrukturernas invarianter och din förmåga att upprätthålla den ena strukturens garantier när du använder primitiva operationer från en annan. Intervjuare använder också dessa frågor som en ingång till att diskutera amortiserad komplexitet.
Den viktiga insikten är att stackar är LIFO och köer är FIFO. För att konvertera mellan dem måste ordningen vändas – och när en stack vänds genom att lägga över den i en annan stack återställs den ursprungliga insättningsordningen, som är FIFO.
Kö med två stackar (lat strategi)
Den lata strategin: använd en inbox-stack för push och en outbox-stack för pop. När dequeue anropas, och outbox är tom, flyttas alla element från inbox till outbox – denna vändning återställer FIFO-ordningen. Om outbox inte är tom tas elementet bort direkt därifrån. Flyttningarna sker först när de behövs, vilket amorterar kostnaden O(n) för flyttningen över många operationer.
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()) # 3Amortiserad O(1)-analys för kö från stackar
Varje element flyttas från inbox till outbox högst en gång. När borttagning från outbox tar O(1) och flyttningar bara sker när outbox är tom, är det totala arbetet för n push och n pop högst 2n stackoperationer – totalt O(n), vilket ger O(1) amortiserat per operation. Det innebär att enskilda operationer kan vara O(n) i värsta fall, men genomsnittet är O(1).
# 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 nStack med två köer (lat pop)
Att implementera en stack med två köer är mindre naturligt eftersom köer är FIFO. Strategin med lat pop: använd en huvudkö och en tillfällig kö. Vid push läggs elementet till i huvudkön (O(1)). Vid pop eller peek tas alla element utom det sista bort från huvudkön och läggs i den tillfälliga kön. Spara det sista elementet och byt sedan plats på köerna. Detta är O(n) per pop men 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()) # 2Stack med en kö (rotera vid push)
En elegant implementering med en kö: vid push läggs det nya elementet till i kön, som sedan roteras så att det nya elementet hamnar längst fram. Att rotera innebär att ta bort från kön och lägga tillbaka alla element som fanns där före push. Pop och peek är då O(1) (bara ta bort eller läsa av det främsta elementet). Push är O(n) – den motsatta avvägningen jämfört med versionen med två köer.
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()) # 2Sammanfattning av avvägningar: vilken variant ska du välja?
För kö med två stackar: push O(1), pop/peek O(1) amortiserat – välj den när pop-operationer är vanliga. För stack med två köer: push O(1), pop O(n) – välj den när push-operationer är mycket vanligare än pop-operationer. För stack med en kö: push O(n), pop O(1) – välj den när pop-operationer dominerar. Beskriv uttryckligen dessa avvägningar i en intervju för att visa att du tänker längre än bara 'det fungerar'.
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)')Varför återställer en vändning FIFO?
När elementen 1, 2, 3 läggs på en stack (inbox) ligger de från botten till toppen i ordningen 1, 2, 3. När alla tas bort till en andra stack (outbox) vänds ordningen: outbox har 3 längst ned och 1 överst. När elementen tas bort från outbox får du 1, sedan 2, sedan 3 – exakt insättningsordningen enligt FIFO. Därför återställer exakt två vändningar (två stackar) FIFO, medan en enda stack ger LIFO.
# 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: Implementera kö med stackar
LeetCode 232 är det direkta problemet 'kö med två stackar'. Den förväntade lösningen är den lata outbox-överföringen. I en intervju ska du ange att varje element flyttas från inbox till outbox högst en gång, vilket gör alla operationer amortiserat O(1). Nämn att enskilda pop-anrop kan vara O(n) i värsta fall när outbox är tom, men att genomsnittet över n operationer är O(1).
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: Implementera stack med köer
LeetCode 225 är problemet 'stack med köer'. Lösningen med en kö som roteras vid push är den renaste. Efter att elementet x har lagts till roteras kön genom att alla element som redan fanns där flyttas bakom x. Detta kostar O(n) per push men gör top och pop till O(1). Ange avvägningen och bekräfta att den matchar begränsningarna, till exempel en arbetsbelastning med få push-anrop eller många pop-anrop.
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()) # FalseUtvidgning till tre stackar i en array
En relaterad designutmaning är att implementera tre stackar med hjälp av en enda array. Ett tillvägagångssätt delar upp arrayen i tre lika stora, fasta sektioner. Ett mer flexibelt tillvägagångssätt använder sammanflätad lagring med pekare, där varje stack växer inom sitt område och kopieras när gränserna kolliderar. Detta testar er förmåga att hantera dynamiska arrayer och förekommer i intervjuer på seniornivå. Tillvägagångssättet med fasta sektioner är enklare, men slösar utrymme om stackarna växer ojämnt.
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 30Viktiga slutsatser: Simuleringsmönster
Problemen med ömsesidig simulering lär ut en bredare princip: alla datastrukturer kan byggas utifrån andra datastrukturer, förutsatt att ni har tillräckligt med mellanlagring och kan vända på ordningen. Kostnaden för simuleringen beror på vilka operationer ni optimerar — ni kan alltid göra push O(1) eller pop O(1), men att göra båda O(1) kräver amortisering eller flera hjälpstrukturer.
Fråga alltid i en intervju: ”Vilka operationer utförs oftast?” Det vägleder valet av implementeringsvariant och visar att ni på seniornivå tänker på de operationella kraven.
Snabb kontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde ni er: en kö som byggs av två stackar uppnår amortiserad O(1) för pop genom att överföra element från inbox till outbox vid behov, en stack som byggs av en kö uppnår O(1) för pop genom att rotera kön vid varje push (push kostar O(n)), och valet av vilken operation som ska ha kostnaden O(1) beror på användningsmönstret. Härnäst går vi igenom hur hash maps är uppbyggda internt och hur kollisioner hanteras.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Ömsesidig simulering av stack och kö” gratis?
Ja – hela texten till ”Ömsesidig simulering av stack och kö” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Ömsesidig simulering av stack och kö”?
Implementera en kö med två stackar och en stack med två köer och förklara den amortiserade kostnaden för varje metod. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Ömsesidig simulering av stack och kö”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Implementering och användning av stackar
- Implementering av köer och deque
- Mönstret monoton stack
- Ömsesidig simulering av stack och kö