Stapelimplementierung und Anwendungen
Implementieren Sie einen Stapel mit push/pop/peek und lösen Sie anschließend valid-parentheses, min-stack und die Auswertung der umgekehrt polnischen Notation.
Stapelimplementierung und Anwendungen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Stack-Datenstruktur
Ein Stack ist eine Datenstruktur nach dem Prinzip „last in, first out“ (LIFO). Das zuletzt auf den Stack gelegte Element wird als Erstes wieder entfernt. Stellen Sie sich einen Tellerstapel vor: Sie können nur oben etwas hinzufügen oder entfernen. Die grundlegenden Operationen sind push (oben hinzufügen), pop (oben entfernen) und peek (das oberste Element lesen, ohne es zu entfernen). Bei einer gut implementierten Stack-Datenstruktur sind alle drei Operationen O(1).
In Python eignet sich eine Liste perfekt als Stack: append entspricht push, pop() entspricht pop und [-1] entspricht peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Stack-Klasse mit Push, Pop, Peek und isEmpty
Wenn Sie die Liste in eine Klasse kapseln, erhalten Sie eine übersichtlichere Schnittstelle und verhindern versehentliche Stack-fremde Operationen wie insert oder den Zugriff auf andere Positionen als das oberste Element. Diese Implementierung erwarten Interviewer, wenn sie Sie auffordern, „einen Stack von Grund auf zu implementieren“.
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Gültige Klammern (LeetCode 20)
LeetCode 20 'Valid Parentheses': Bestimmen Sie, ob eine Zeichenkette mit Klammern ausgeglichen ist. Legen Sie für jede öffnende Klammer diese auf den Stack. Prüfen Sie bei jeder schließenden Klammer, ob das oberste Stack-Element die passende öffnende Klammer ist. Falls nicht oder falls der Stack leer ist, geben Sie False zurück. Ist der Stack am Ende leer, ist die Zeichenkette gültig. Dies ist die klassische erste Anwendung eines Stacks in Programmierinterviews.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalseMin-Stack (LeetCode 155)
LeetCode 155 'Min Stack': Entwerfen Sie einen Stack, der push, pop, peek und getMin jeweils in O(1) unterstützt. Der Trick: Verwalten Sie einen zweiten Stack, der das Minimum an jeder Stelle verfolgt. Legen Sie beim Hinzufügen außerdem einen Wert auf den Min-Stack, wenn der neue Wert <= dem aktuellen Minimum ist (oder wenn der Min-Stack leer ist). Entfernen Sie beim Löschen außerdem das oberste Element des Min-Stacks, wenn der entfernte Wert dem aktuellen Minimum entspricht.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Umgekehrte polnische Notation auswerten
LeetCode 150 'Evaluate Reverse Polish Notation' (Postfixnotation): Operanden werden auf den Stack gelegt. Beim Auftreten eines Operators werden zwei Operanden entfernt, die Operation angewendet und das Ergebnis auf den Stack gelegt. Bei Subtraktion und Division ist die Reihenfolge wichtig: Der zuerst entfernte Operand ist der rechte, der zweite der linke Operand.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Zeichenkette dekodieren (LeetCode 394)
LeetCode 394 'Decode String': Erweitern Sie eine kodierte Zeichenkette wie 3[a2[c]] zu accaccacc. Verwenden Sie zwei Stacks: einen für Wiederholungszahlen und einen für bereits zusammengesetzte Zeichenketten. Bauen Sie beim Auftreten einer Ziffer die vollständige Zahl auf. Legen Sie bei [ die aktuelle Zeichenkette und die Anzahl auf den Stack. Entfernen Sie bei ] beide Werte und wiederholen Sie das aktuelle Segment. Hängen Sie bei einem Buchstaben diesen an die aktuelle Zeichenkette an.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Tägliche Temperaturen (Vorschau auf den monotonen Stack)
LeetCode 739 'Daily Temperatures': Finden Sie für jeden Tag heraus, wie viele Tage bis zu einer wärmeren Temperatur vergehen. Ein Brute-Force-Ansatz benötigt O(n²). Verwenden Sie einen Stack: Durchlaufen Sie die Temperaturen und entfernen Sie für jeden Tag alle Stack-Einträge (Tagesindizes), deren Temperatur niedriger als die heutige ist. Die Antwort für die entfernten Tage lautet (heute - entfernter_Tag). Legen Sie anschließend den aktuellen Tag auf den Stack. Für die verbleibenden Stack-Einträge wurde nie ein wärmerer Tag gefunden – ihre Antwort ist 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Stack für die DFS-Traversierung
Der Aufruf-Stack einer rekursiven DFS kann durch einen expliziten Stack ersetzt werden, wodurch der Algorithmus iterativ wird. Legen Sie die Wurzel auf den Stack. Solange der Stack nicht leer ist, entfernen Sie einen Knoten, verarbeiten ihn und legen seine Kinder auf den Stack (für eine Verarbeitung von links nach rechts zuerst rechts, dann links). Diese iterative DFS verhält sich genauso wie eine rekursive DFS, umgeht aber bei tiefen Bäumen das Rekursionslimit von Python.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Zeit- und Speicherkomplexität
Alle Stack-Operationen (push, pop, peek, isEmpty) sind amortisiert O(1). Das Erstellen eines Stacks mit n Elementen benötigt O(n). Der Speicherbedarf beträgt im schlechtesten Fall O(n), wenn alle Elemente gespeichert sind. Bei Problemen mit einem monotonen Stack wird jedes Element höchstens einmal auf den Stack gelegt und einmal entfernt. Über alle Iterationen hinweg ergibt sich daher eine Gesamtzeit von O(n) – nicht O(n²), wie eine naive Betrachtung der äußeren Schleife vermuten lassen könnte.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Größtes Rechteck im Histogramm (Vorschau)
LeetCode 84 'Largest Rectangle in Histogram' ist das schwierigste klassische Stack-Problem. Für jeden Balken erstreckt sich das Rechteck, das an seiner Höhe ansetzt, nach links bis zum ersten kürzeren Balken und nach rechts ebenfalls bis zum ersten kürzeren Balken. Ein monotoner Stack verfolgt die Indizes der Balken in aufsteigender Höhenreihenfolge. Wird ein kürzerer Balken gefunden, entfernen Sie Elemente vom Stack und berechnen das Rechteck mit der Höhe des entfernten Balkens. Der Stack liefert die linken und rechten Grenzen in O(1) pro Entfernung.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Interviewstrategie für Stack-Probleme
Stack-Probleme tarnen sich oft als „von innen nach außen verarbeiten“ oder „das nächste größere beziehungsweise kleinere Element finden“. Hinweise darauf, dass ein Stack hilfreich sein könnte: Sie benötigen das zuletzt gesehene Element, gleichen Paare ab (Klammern, Tags) oder möchten bei einem Problem O(n) erreichen, das naiv O(n²) verschachtelte Schleifen erfordern würde. Monotone Stacks verwandeln insbesondere die Suche nach dem „nächstgelegenen größeren oder kleineren Element für jedes Element“ von O(n²) in O(n).
Formulieren Sie in einem Interview die Invariante Ihres Stacks klar: „Ich verwalte einen Stack mit Indizes in absteigender Höhenreihenfolge.“
Kurzer Test
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: Python-Listen implementieren push, pop und peek in O(1) und sind daher ideale Stacks, gültige Klammern und der Min-Stack sind die beiden klassischen Stack-Probleme in Programmierinterviews und monotone Stacks lösen Probleme mit dem jeweils nächsten größeren Element in O(n), indem jedes Element höchstens einmal auf den Stack gelegt und entfernt wird. Als Nächstes erstellen wir Queues mit Pythons deque und lösen das Problem des Maximums im gleitenden Fenster.
Häufig gestellte Fragen
Ist die Lektion „Stapelimplementierung und Anwendungen“ kostenlos?
Ja — der vollständige Text von „Stapelimplementierung und Anwendungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Stapelimplementierung und Anwendungen“?
Implementieren Sie einen Stapel mit push/pop/peek und lösen Sie anschließend valid-parentheses, min-stack und die Auswertung der umgekehrt polnischen Notation. Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 1 von 4.
Wie lange dauert die Lektion „Stapelimplementierung und Anwendungen“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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