DSA Interview Prep · leksjon

Gjensidig simulering av stakk og kø

Implementer en kø med to stacker og en stakk med to køer, og forklar den amortiserte kostnaden ved hver fremgangsmåte.

Leksjon 4 av 413 trinn

Gjensidig simulering av stakk og kø er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 4 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hvorfor simulere den ene med den andre?

Å implementere en kø ved hjelp av to stabler og en stakk ved hjelp av to køer er klassiske designspørsmål i jobbintervjuer. De tester forståelsen av invariantene for begge datastrukturene og evnen til å opprettholde garantien til én struktur ved hjelp av primitive operasjoner fra en annen. Intervjuere bruker også disse oppgavene som utgangspunkt for å diskutere amortisert kompleksitet.

Hovedinnsikten er at stabler følger LIFO, mens køer følger FIFO. For å konvertere mellom dem må rekkefølgen snus – og når en stakk snus ved å legge elementene over i en annen stakk, får man den opprinnelige innleggingsrekkefølgen, som er FIFO.

Kø ved hjelp av to stabler (lat tilnærming)

Den late tilnærmingen bruker en inbox-stakk for push-operasjoner og en outbox-stakk for pop-operasjoner. Når dequeue kalles, og outbox er tom, overføres alle elementene fra inbox til outbox – denne reverseringen gjenoppretter FIFO-rekkefølgen. Hvis outbox ikke er tom, tas elementet direkte ut derfra. Overføringene skjer sent og fordeler kostnaden på O(n) over mange operasjoner.

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())   # 3

Amortisert O(1)-analyse for kø fra stabler

Hvert element overføres fra inbox til outbox høyst én gang. Når uttak fra outbox er O(1), og overføringer bare skjer når outbox er tom, er det totale arbeidet for n push-operasjoner og n pop-operasjoner høyst 2n stakkoperasjoner – totalt O(n), altså amortisert O(1) per operasjon. Det betyr at enkeltoperasjoner i verste fall kan være O(n), mens gjennomsnittet er 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 n

Stakk ved hjelp av to køer (lat pop)

Det er mindre naturlig å implementere en stakk med to køer fordi køer følger FIFO. Den late pop-tilnærmingen bruker én hovedkø og én midlertidig kø. Ved push legges elementet i hovedkøen (O(1)). Ved pop eller peek tas alle unntatt det siste elementet ut av køen og legges i den midlertidige køen. Det siste elementet lagres, og køene bytter plass. Dette gir 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())  # 2

Stakk ved hjelp av én kø (roter ved push)

En elegant implementasjon med én kø: Ved push legges det nye elementet i køen, og deretter roteres køen slik at det nye elementet kommer først. Rotering betyr at alle elementene som var der før push-operasjonen, tas ut og legges inn igjen. Deretter er pop og peek O(1) (de tar bare ut eller ser på det første elementet). Push er O(n) – det motsatte kompromisset av varianten med to 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())  # 2

Oppsummering av kompromisser: Hvilken variant bør man velge?

For kø fra to stabler: push O(1), pop/peek amortisert O(1) – foretrekk dette når pop-operasjoner er hyppige. For stakk fra to køer: push O(1), pop O(n) – foretrekk dette når push-operasjoner er langt hyppigere enn pop-operasjoner. For stakk fra én kø: push O(n), pop O(1) – foretrekk dette når pop-operasjoner dominerer. Oppgi disse kompromissene tydelig i et intervju for å vise at De tenker lenger enn bare «det fungerer».

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)')

Hvorfor gjenoppretter reversering FIFO?

Når elementene 1, 2 og 3 legges på en stakk (inbox), ligger de i rekkefølgen 1, 2, 3 fra bunn til topp. Hvis alle tas ut og legges på en stakk nummer to (outbox), snus rekkefølgen: I outbox ligger 3 nederst og 1 øverst. Når elementene tas ut av outbox, kommer 1, deretter 2 og så 3 – nøyaktig innleggingsrekkefølgen i FIFO. Derfor gjenoppretter nøyaktig to reverseringer (to stabler) FIFO, mens én stakk alene gir 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: Implementer kø ved hjelp av stabler

LeetCode 232 er det direkte problemet «kø fra to stabler». Den forventede løsningen er den late overføringen til outbox. I et intervju bør man oppgi at hvert element flyttes fra inbox til outbox høyst én gang, slik at alle operasjoner blir amortisert O(1). Nevn at individuelle pop-kall i verste fall kan være O(n) (når outbox er tom), men at gjennomsnittet over n operasjoner er 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()) # False

LeetCode 225: Implementer stakk ved hjelp av køer

LeetCode 225 er problemet «stakk fra køer». Løsningen med én kø som roteres ved push, er den ryddigste. Etter at elementet x er lagt inn, roteres køen ved å flytte alle elementene som allerede lå der, bak x. Dette koster O(n) per push, men gjør top og pop til O(1). Oppgi kompromisset, og bekreft at det passer med begrensningene (for eksempel en arbeidsbelastning med få push-operasjoner eller mange pop-operasjoner).

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()) # False

Utvidelse til tre stacker i ett array

En beslektet designutfordring er å implementere tre stacker ved hjelp av ett enkelt array. Én tilnærming deler arrayet inn i tre like, faste seksjoner. En mer fleksibel tilnærming bruker interlevert lagring med pekere, der hver stack vokser innenfor sitt område, og elementene kopieres når grensene kolliderer. Dette tester håndtering av dynamiske arrayer og dukker opp i intervjuer på seniornivå. Tilnærmingen med faste seksjoner er enklere, men sløser med plass hvis stackene vokser ujevnt.

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 30

Viktigste læringspunkter: simuleringsmønstre

Problemene med gjensidig simulering lærer bort et bredere prinsipp: Enhver datastruktur kan bygges ved hjelp av en annen, gitt tilstrekkelig mellomlagring og reversering. Kostnaden ved simuleringen avhenger av hvilke operasjoner De optimaliserer — De kan alltid gjøre push O(1) eller pop O(1), men for å gjøre begge O(1) kreves amortisering eller flere hjelpestrukturer.

I et intervju bør De alltid spørre: «Hvilke operasjoner forekommer oftest?» Dette gir en veiledning for valg av implementasjonsvariant og viser at De tenker på seniornivå om operasjonelle krav.

Kort kontroll

Test forståelsen Deres av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De at en kø bygget av to stacker oppnår amortisert pop på O(1) ved å overføre elementer fra innboks til utboks først når det er nødvendig, at en stack bygget av én kø oppnår pop på O(1) ved å rotere køen ved hver push (push på O(n)), og at valget av hvilken operasjon som skal være O(1), avhenger av bruksmønsteret. Neste tema er hvordan hash maps fungerer internt, og hvordan kollisjoner håndteres.

Gratis å komme i gang

Lær deg Python 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: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Gjensidig simulering av stakk og kø» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Gjensidig simulering av stakk og kø», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «Gjensidig simulering av stakk og kø»?

Implementer en kø med to stacker og en stakk med to køer, og forklar den amortiserte kostnaden ved hver fremgangsmåte. Du øver på DSA Interview Prep 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 DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep 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 4 av 4.

Hvor lang tid tar leksjonen «Gjensidig simulering av stakk og kø»?

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 DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-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ø

← Tilbake til DSA Interview Prep