Gegenseitige Simulation von Stapel und Warteschlange
Implementieren Sie eine Warteschlange mit zwei Stapeln und einen Stapel mit zwei Warteschlangen und erklären Sie die amortisierten Kosten jedes Ansatzes.
Gegenseitige Simulation von Stapel und Warteschlange ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum das eine mit dem anderen simulieren?
Die Implementierung einer Warteschlange mit zwei Stacks und eines Stacks mit zwei Warteschlangen sind klassische Designfragen in Vorstellungsgesprächen. Sie testen Ihr Verständnis der Invarianten beider Datenstrukturen und Ihre Fähigkeit, die Garantie einer Struktur aufrechtzuerhalten, während Sie die Grundoperationen einer anderen verwenden. Interviewer nutzen diese Aufgaben außerdem häufig als Einstieg in die Diskussion der amortisierten Komplexität.
Die zentrale Erkenntnis: Stacks arbeiten nach dem LIFO- und Warteschlangen nach dem FIFO-Prinzip. Um zwischen ihnen umzuwandeln, müssen Sie die Reihenfolge umkehren – und das Umkehren eines Stacks in einen anderen Stack ergibt die ursprüngliche Einfügereihenfolge, also FIFO.
Warteschlange mit zwei Stacks (verzögerter Ansatz)
Der verzögerte Ansatz: Verwenden Sie einen inbox-Stack für push-Operationen und einen outbox-Stack für pop-Operationen. Wenn dequeue aufgerufen wird und outbox leer ist, übertragen Sie alle Elemente von inbox nach outbox – durch diese Umkehrung wird die FIFO-Reihenfolge wiederhergestellt. Wenn outbox nicht leer ist, entfernen Sie das oberste Element direkt daraus. Die Übertragungen erfolgen verzögert, sodass sich die Übertragungskosten von O(n) auf viele Operationen verteilen.
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()) # 3Amortisierte O(1)-Analyse für eine Warteschlange aus Stacks
Jedes Element wird höchstens einmal von inbox nach outbox übertragen. Wenn pop auf outbox O(1) kostet und Übertragungen nur stattfinden, wenn outbox leer ist, beträgt der Gesamtaufwand für n push- und n pop-Operationen höchstens 2n Stack-Operationen – insgesamt O(n), amortisiert O(1) pro Operation. Das bedeutet, dass einzelne Operationen im schlimmsten Fall O(n) dauern können, der Durchschnitt aber O(1) beträgt.
# 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 mit zwei Warteschlangen (verzögertes Entfernen)
Die Implementierung eines Stacks mit zwei Warteschlangen ist weniger naheliegend, weil Warteschlangen nach dem FIFO-Prinzip arbeiten. Beim verzögerten pop-Ansatz wird eine Hauptwarteschlange und eine temporäre Warteschlange verwendet. Bei push reihen Sie das neue Element in die Hauptwarteschlange ein (O(1)). Bei pop oder peek entfernen Sie alle Elemente bis auf das letzte und reihen sie in die temporäre Warteschlange ein, speichern das letzte Element und tauschen anschließend die Warteschlangen. Das kostet O(n) pro pop, aber O(1) pro 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 mit einer Warteschlange (Rotation bei push)
Eine elegante Implementierung mit einer Warteschlange: Bei push reihen Sie das neue Element ein und rotieren anschließend die Warteschlange, sodass das neue Element vorne liegt. Rotation bedeutet, alle Elemente, die bereits vor dem push vorhanden waren, zu entfernen und wieder einzureihen. pop und peek kosten dann O(1) (lediglich das vorderste Element wird entfernt bzw. betrachtet). push kostet O(n) – das ist die entgegengesetzte Abwägung im Vergleich zur Variante mit zwei Warteschlangen.
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()) # 2Zusammenfassung der Abwägungen: Welche Variante wählen?
Für eine Warteschlange aus zwei Stacks: push O(1), pop/peek amortisiert O(1) – bevorzugen Sie diese Variante, wenn pop-Operationen häufig sind. Für einen Stack aus zwei Warteschlangen: push O(1), pop O(n) – bevorzugen Sie diese Variante, wenn push-Operationen deutlich häufiger als pop-Operationen sind. Für einen Stack aus einer Warteschlange: push O(n), pop O(1) – bevorzugen Sie diese Variante, wenn pop-Operationen überwiegen. Nennen Sie diese Abwägungen im Vorstellungsgespräch ausdrücklich, um zu zeigen, dass Sie über „es funktioniert“ hinausdenken.
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)')Warum stellt das Umdrehen FIFO wieder her?
Wenn die Elemente 1, 2, 3 auf einen Stack (inbox) gelegt werden, liegen sie von unten nach oben in der Reihenfolge 1, 2, 3. Werden alle Elemente auf einen zweiten Stack (outbox) gelegt, wird die Reihenfolge umgekehrt: In outbox liegen 3 unten und 1 oben. Das Ausführen von pop auf outbox ergibt 1, dann 2, dann 3 – genau die FIFO-Einfügereihenfolge. Deshalb stellt genau zweimaliges Umkehren (zwei Stacks) FIFO wieder her, während ein einzelner Stack LIFO ergeben würde.
# 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: Warteschlange mit Stacks implementieren
LeetCode 232 ist die direkte Aufgabe „Warteschlange aus zwei Stacks“. Die erwartete Lösung ist die verzögerte Übertragung in outbox. Im Vorstellungsgespräch: Erklären Sie, dass jedes Element höchstens einmal von inbox nach outbox verschoben wird und dadurch alle Operationen amortisiert O(1) sind. Erwähnen Sie, dass einzelne pop-Aufrufe im schlimmsten Fall O(n) dauern können (wenn outbox leer ist), der Durchschnitt über n Operationen jedoch O(1) beträgt.
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: Stack mit Warteschlangen implementieren
LeetCode 225 ist die Aufgabe „Stack aus Warteschlangen“. Die Lösung mit einer Warteschlange und Rotation bei push ist die klarste. Nachdem Sie das Element x eingefügt haben, rotieren Sie die Warteschlange, indem Sie alle bereits vorhandenen Elemente hinter x verschieben. Das kostet O(n) pro push, macht aber top und pop zu O(1). Nennen Sie die Abwägung und bestätigen Sie, dass sie zu den Einschränkungen passt (z. B. eine Arbeitslast mit wenigen push- bzw. vielen pop-Operationen).
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()) # FalseErweiterung auf drei Stacks in einem Array
Eine verwandte Design-Herausforderung besteht darin, drei Stacks mithilfe eines einzigen Arrays zu implementieren. Ein Ansatz teilt das Array in drei gleich große, feste Bereiche auf. Ein flexiblerer Ansatz verwendet eine verschachtelte Speicherung mit Zeigern: Jeder Stack wächst in seinem Bereich, und wenn Bereiche kollidieren, werden die Elemente kopiert. Damit werden das dynamische Array-Management und der Umgang mit Speichergrenzen geprüft; diese Aufgabe wird in Interviews auf Senior-Level gestellt. Der Ansatz mit festen Bereichen ist einfacher, verschwendet jedoch Platz, wenn die Stacks unterschiedlich stark wachsen.
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 30Wichtigste Erkenntnisse: Simulationsmuster
Die Probleme zur gegenseitigen Simulation vermitteln ein allgemeineres Prinzip: Jede Datenstruktur kann aus einer anderen aufgebaut werden, sofern genügend Zwischenpuffer und Umkehrungen zur Verfügung stehen. Die Kosten der Simulation hängen davon ab, welche Operationen Sie optimieren – push oder pop können Sie immer mit O(1) realisieren, aber für O(1) bei beiden Operationen benötigen Sie Amortisierung oder mehrere Hilfsstrukturen.
Fragen Sie im Interview immer: „Welche Operationen kommen häufiger vor?“ Das hilft bei der Wahl der Implementierungsvariante und zeigt, dass Sie Anforderungen an die Nutzung auf Senior-Niveau analysieren.
Kurztest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Eine Queue aus zwei Stacks erzielt durch die verzögerte Übertragung von Elementen aus inbox nach outbox ein amortisiertes pop mit O(1), ein Stack aus einer Queue erzielt durch das Rotieren der Queue bei jedem push ein pop mit O(1) (push mit O(n)) und welche Operation Sie mit O(1) realisieren, hängt vom Nutzungsmuster ab. Als Nächstes untersuchen wir die Interna von Hash-Maps und den Umgang mit Kollisionen.
Häufig gestellte Fragen
Ist die Lektion „Gegenseitige Simulation von Stapel und Warteschlange“ kostenlos?
Ja — der vollständige Text von „Gegenseitige Simulation von Stapel und Warteschlange“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Gegenseitige Simulation von Stapel und Warteschlange“?
Implementieren Sie eine Warteschlange mit zwei Stapeln und einen Stapel mit zwei Warteschlangen und erklären Sie die amortisierten Kosten jedes Ansatzes. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Gegenseitige Simulation von Stapel und Warteschlange“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Stapelimplementierung und Anwendungen
- Warteschlangenimplementierung und Deque
- Muster des monotonen Stapels
- Gegenseitige Simulation von Stapel und Warteschlange