Stackimplementatie en toepassingen
Implementeer een stack met push/pop/peek en los vervolgens valid-parentheses, min-stack en evaluate reverse-polish notation op.
Stackimplementatie en toepassingen is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
De stackgegevensstructuur
Een stack is een laatst-erin-eerst-eruit- (LIFO-)gegevensstructuur. Het laatste element dat je op de stack zet, is het eerste element dat je eraf haalt. Denk aan een stapel borden: je kunt alleen bovenaan iets toevoegen of verwijderen. De belangrijkste bewerkingen zijn push (bovenaan toevoegen), pop (bovenaan verwijderen) en peek (het bovenste element lezen zonder het te verwijderen). Op een goed geïmplementeerde stack kosten alle drie O(1).
In Python is een list een perfecte stack: append is push, pop() is pop en [-1] is 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]Stackklasse met Push, Pop, Peek, isEmpty
Door de list in een klasse te verpakken, krijg je een schonere interface en voorkom je dat je per ongeluk niet-stackbewerkingen gebruikt, zoals insert of indexering op andere posities dan de top. Dit is de implementatie die interviewers verwachten wanneer ze vragen om 'een stack vanaf nul te implementeren'.
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)) # 2Geldige haakjes (LeetCode 20)
LeetCode 20 'Geldige haakjes': bepaal of een tekenreeks met haakjes in balans is. Voor elk openend haakje voer je een push uit. Voor elk sluitend haakje controleer je of het bovenste element van de stack het bijbehorende openende haakje is; zo niet, of als de stack leeg is, geef je False terug. Als de stack aan het einde leeg is, is de tekenreeks geldig. Dit is de klassieke eerste toepassing van een stack in programmeerinterviews.
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(']')) # FalseMinimumstack (LeetCode 155)
LeetCode 155 'Minimumstack': ontwerp een stack die push, pop, peek en getMin allemaal in O(1) ondersteunt. De truc: houd een tweede stack bij die op elk moment de minimumwaarde bevat. Voeg bij een push de waarde ook toe aan de minimumstack als de nieuwe waarde <= de huidige minimumwaarde is (of als de minimumstack leeg is). Voer bij een pop ook een pop op de minimumstack uit als de verwijderde waarde gelijk is aan de huidige minimumwaarde.
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()) # -2Omgekeerde Poolse notatie evalueren
LeetCode 150 'Omgekeerde Poolse notatie evalueren' (postfixnotatie): operanden worden op de stack gezet; wanneer je een operator tegenkomt, haal je twee operanden van de stack, pas je de operator toe en zet je het resultaat op de stack. De volgorde is belangrijk bij aftrekken en delen: de eerst verwijderde operand is de rechteroperand, de tweede is de linkeroperand.
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','+'])) # 22Tekenreeks decoderen (LeetCode 394)
LeetCode 394 'Tekenreeks decoderen': gegeven een gecodeerde tekenreeks zoals 3[a2[c]], vouw je die uit tot accaccacc. Gebruik twee stacks: één voor herhalingsaantallen en één voor opgebouwde tekenreeksen. Bouw bij het tegenkomen van een cijfer het volledige getal op. Voer bij [ de huidige tekenreeks en het aantal op de stack uit. Haal ze bij ] weer van de stack en herhaal het huidige segment. Voeg bij een letter die letter aan de huidige tekenreeks toe.
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'Dagelijkse temperaturen (voorproefje van de monotone stack)
LeetCode 739 'Dagelijkse temperaturen': vind voor elke dag hoeveel dagen het duurt voordat er een warmere temperatuur komt. Een bruteforcebenadering kost O(n²). Met een stack doorloop je de temperaturen; voor elke dag verwijder je alle stackelementen (dagindexen) waarvan de temperatuur lager is dan die van vandaag. Het antwoord voor die verwijderde dagen is (today - popped_day). Zet de huidige dag op de stack. De overgebleven stackelementen hebben nooit een warmere dag gevonden — hun antwoord is 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 voor DFS-doorloop
De aanroepstack in recursieve DFS kan worden vervangen door een expliciete stack, waardoor het algoritme iteratief wordt. Zet de wortel op de stack; zolang de stack niet leeg is, haal je een knooppunt van de stack, verwerk je het en zet je de kinderen op de stack (rechts vóór links voor verwerking van links naar rechts). Deze iteratieve DFS gedraagt zich hetzelfde als recursieve DFS, maar omzeilt de recursielimiet van Python voor diepe bomen.
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]Tijds- en ruimtecomplexiteit
Alle stackbewerkingen (push, pop, peek, isEmpty) kosten O(1)O(n) oplevert — niet O(n²), zoals een naïeve lezing van de buitenste lus zou kunnen doen vermoeden.
# 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}') # <= 2000Grootste rechthoek in histogram (voorproefje)
LeetCode 84 'Grootste rechthoek in histogram' is het moeilijkste klassieke stackprobleem. Voor elke staaf strekt de rechthoek die met de hoogte van die staaf kan worden verankerd zich naar links uit totdat er een kortere staaf wordt gevonden, en naar rechts totdat er een kortere staaf wordt gevonden. Een monotone stack houdt de indexen bij van staven in oplopende volgorde van hoogte. Wanneer je een kortere staaf tegenkomt, haal je elementen van de stack en bereken je de rechthoek met de hoogte van de verwijderde staaf. De stack levert voor elke verwijdering in O(1) de linker- en rechtergrenzen.
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 voor stackproblemen
Stackproblemen verbergen zich vaak achter formuleringen als 'van binnen naar buiten verwerken' of 'het eerstvolgende grotere of kleinere element vinden'. Signalen dat een stack kan helpen: je hebt het meest recent geziene element nodig, je koppelt paren aan elkaar (haakjes, tags) of je wilt O(n) bereiken bij een probleem waarvoor je naïef geneste lussen van O(n²) nodig hebt. Monotone stacks veranderen vooral 'vind voor elk element het dichtstbijzijnde grotere of kleinere element' van O(n²) in O(n).
Benoem in een interview je stackinvariant duidelijk: 'Ik houd een stack bij met indexen in aflopende volgorde van hoogte.'
Korte toets
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: Python-lijsten implementeren push, pop en peek in O(1), waardoor ze ideale stacks zijn, geldige haakjes en de minimumstack zijn de twee klassieke stackproblemen in interviews, en monotone stacks lossen problemen met het eerstvolgende grotere element op in O(n) door elk element hoogstens één keer op de stack te zetten en eraf te halen. Hierna bouwen we queues met Python's deque en lossen we het maximum in een schuivend venster op.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Stackimplementatie en toepassingen” gratis?
Ja — de volledige tekst van “Stackimplementatie en toepassingen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Stackimplementatie en toepassingen”?
Implementeer een stack met push/pop/peek en los vervolgens valid-parentheses, min-stack en evaluate reverse-polish notation op. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Stackimplementatie en toepassingen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Stackimplementatie en toepassingen
- Queue-implementatie en deque
- Patroon van de monotone stack
- Stack en queue wederzijds simuleren