DSA Interview Prep · Lektion

Gensidig simulering af stack og kø

Implementer en kø med to stacks og en stack med to køer, og forklar den amortiserede pris for hver metode.

Lektion 4 af 413 trin

Gensidig simulering af stack og kø er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 4 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.

Hvorfor simulere den ene med den anden

At implementere en kø ved hjælp af to stakke og en stak ved hjælp af to køer er klassiske designspørgsmål i jobsamtaler. De afprøver din forståelse af begge datastrukturers invarianter og din evne til at opretholde den ene strukturs garanti ved hjælp af primitiver fra en anden. Interviewere bruger også disse opgaver som udgangspunkt for at tale om amortiseret kompleksitet.

Den vigtigste indsigt er, at stakke følger LIFO, mens køer følger FIFO. For at omdanne den ene til den anden skal du vende rækkefølgen — og når du vender en stak over i en anden stak, får du den oprindelige indsættelsesrækkefølge, som er FIFO.

Kø ved hjælp af to stakke (udskudt tilgang)

Den udskudte tilgang bruger en inbox-stak til indsættelser og en outbox-stak til fjernelser. Når dequeue kaldes, og outbox er tom, overføres alle elementer fra inbox til outbox — denne vending genskaber FIFO-rækkefølgen. Hvis outbox ikke er tom, fjernes elementet direkte fra den. Overførslerne sker efter behov, så omkostningen på O(n) amortiseres over mange 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())   # 3

Amortiseret O(1)-analyse for kø bygget af stakke

Hvert element overføres fra inbox til outbox højst én gang. Når fjernelse fra outbox tager O(1), og overførsler kun sker, når outbox er tom, er det samlede arbejde for n push-operationer og n pop-operationer højst 2n stakoperationer — O(n) i alt og O(1) amortiseret pr. operation. Det betyder, at individuelle operationer i værste fald kan tage O(n), men gennemsnittet 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

Stak ved hjælp af to køer (udskudt fjernelse)

Det er mindre naturligt at implementere en stak med to køer, fordi køer følger FIFO. Tilgangen med udskudt fjernelse bruger én hovedkø og én midlertidig kø. Ved push indsættes elementet i hovedkøen (O(1)). Ved pop eller peek fjernes alle elementer undtagen det sidste til den midlertidige kø, det sidste element gemmes, og køerne byttes derefter. Det tager O(n) pr. pop, men O(1) pr. 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

Stak ved hjælp af én kø (rotation ved push)

En elegant implementering med én kø: Ved push indsættes det nye element, hvorefter køen roteres, så det nye element står forrest. Rotation betyder, at alle elementer, der var i køen før indsættelsen, fjernes og indsættes igen. Derefter tager pop og peek O(1) (du fjerner eller ser blot på det forreste element). Push tager O(n) — det modsatte kompromis af versionen 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

Opsummering af kompromiser: Hvilken variant skal du vælge

For kø bygget af to stakke: push O(1), pop/peek O(1) amortiseret — foretræk den, når pop-operationer er hyppige. For stak bygget af to køer: push O(1), pop O(n) — foretræk den, når push-operationer er langt hyppigere end pop-operationer. For stak bygget af én kø: push O(n), pop O(1) — foretræk den, når pop-operationer dominerer. Forklar disse kompromiser tydeligt i en jobsamtale for at vise, at du tænker længere end blot 'det virker'.

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 genskaber vending FIFO-rækkefølgen

Når elementerne 1, 2 og 3 lægges på en stak (inbox), ligger de fra bund til top i rækkefølgen 1, 2, 3. Når alle elementerne fjernes og lægges på en anden stak (outbox), vendes rækkefølgen: outbox har 3 i bunden og 1 på toppen. Når du fjerner elementer fra outbox, får du 1, derefter 2 og derefter 3 — præcis den rækkefølge, som FIFO indsætter dem i. Derfor genskaber præcis to vendinger (to stakke) FIFO, mens en enkelt stak ville give 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: Implementér en kø ved hjælp af stakke

LeetCode 232 er det direkte problem med at bygge en 'kø ved hjælp af to stakke'. Den forventede løsning er den udskudte overførsel til outbox. I en jobsamtale skal du sige, at hvert element flyttes fra inbox til outbox højst én gang, så alle operationer er O(1) amortiseret. Nævn, at individuelle pop-kald i værste fald kan tage O(n), når outbox er tom, men at gennemsnittet over n operationer 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: Implementér en stak ved hjælp af køer

LeetCode 225 er problemet med at bygge en 'stak ved hjælp af køer'. Løsningen med én kø og rotation ved push er den enkleste. Når elementet x er lagt på, roteres køen ved at flytte alle elementer, der allerede var i den, om bag x. Det koster O(n) pr. push, men gør top og pop til O(1). Angiv kompromiset, og bekræft, at det passer til begrænsningerne, f.eks. en arbejdsbelastning med få push-operationer eller mange pop-operationer.

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

Udvidelse til tre stakke i ét array

En beslægtet konstruktionsudfordring er at implementere tre stakke ved hjælp af ét array. Én tilgang opdeler arrayet i tre lige store sektioner med fast størrelse. En mere fleksibel tilgang bruger sammenflettet lagring med pegere, hvor hver stak vokser inden for sit område, og elementerne kopieres, når grænserne kolliderer. Det tester håndtering af dynamiske arrays og stilles ved interviews på seniorniveau. Tilgangen med faste sektioner er enklere, men spilder plads, hvis stakkene vokser ujævnt.

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

Vigtigste pointer: simuleringsmønstre

Problemer med gensidig simulering lærer dig et bredere princip: Enhver datastruktur kan bygges ud fra en anden, hvis du har tilstrækkelig mellemlagring og kan vende rækkefølgen. Omkostningen ved simuleringen afhænger af, hvilke operationer du optimerer — du kan altid gøre indsættelse O(1) eller fjernelse O(1), men hvis begge skal være O(1), kræver det amortisering eller flere hjælpestrukturer.

Ved et interview skal du altid spørge: "Hvilke operationer forekommer oftest?" Det hjælper med at vælge den rigtige implementeringsvariant og viser, at du tænker på operationelle krav på seniorniveau.

Hurtigt tjek

Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.

Besvar den i den interaktive lektion

Opsamling på lektionen

I denne lektion har du lært: En kø, der bygges af to stakke, opnår amortiseret O(1)-tid for fjernelse ved dovent at overføre elementer fra indbakken til udbakken, en stak, der bygges af én kø, opnår O(1)-tid for fjernelse ved at rotere køen ved hver indsættelse (indsættelse i O(n)), og valget af, hvilken operation der skal have O(1)-tid, afhænger af brugsmønsteret. Næste emne er hashmap-interne og håndtering af kollisioner.

Gratis at komme i gang

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

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Gensidig simulering af stack og kø” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Gensidig simulering af stack og kø”, 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 “Gensidig simulering af stack og kø”?

Implementer en kø med to stacks og en stack med to køer, og forklar den amortiserede pris for hver metode. 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 4 af 4.

Hvor lang tid tager lektionen “Gensidig simulering af stack og kø”?

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

← Tilbage til DSA Interview Prep