Python-stack: LIFO-datastructuren implementeren

Elke keer dat je Ctrl+Z indrukt om een fout ongedaan te maken, op de terugknop in je browser klikt, of een recursieve functie zijn resultaten ziet afwikkelen, vertrouw je op een stack. Omdat ze zo diep verweven zijn met de software die je dagelijks gebruikt, kom je stacks vaak tegen zonder dat je het doorhebt.

In dit artikel kijken we naar wat een stack is, de kernlogica erachter, vergelijken we verschillende implementatiestrategieën met de ingebouwde libraries van Python en passen we ze toe om algoritmische problemen op te lossen.

Ik raad je aan onze cursus op Writing Efficient Python Code te volgen om je kennis van datastructuren te koppelen aan best practices voor performance, en houd het Python Basics Cheat Sheet bij de hand als snel naslagwerk. 

Wat is een stack in Python?

Voordat we naar code kijken, is het belangrijk de conceptuele basis te begrijpen die de Python-stack zo krachtig maakt. Laten we het kernprincipe achter stacks bekijken en zien hoe ze verschillen van andere gangbare datastructuren.

De LIFO-datastructuur

Een stack is een lineaire datastructuur die het Last-In-First-Out (LIFO)-principe volgt. Dit betekent dat het meest recent toegevoegde element altijd als eerste wordt verwijderd. Denk aan een stapel borden in een kantine. Je legt nieuwe borden bovenop en pakt altijd het bovenste bord eerst. Je haalt nooit een bord uit het midden of van de onderkant. Toegang is volledig beperkt tot de top.

Die ene beperking, alleen-toegang via de top, geeft stacks hun voorspelbaarheid en efficiëntie. Elk element gaat erin en eruit via dezelfde kant, wat de operaties eenvoudig en snel houdt.

Belangrijk om vroeg te noemen: Python wordt niet geleverd met een dedicated, primitief stacktype zoals sommige andere talen dat hebben. Er is geen stack-keyword of ingebouwde class. In plaats daarvan biedt Python robuuste ingebouwde alternatieven zoals lists, collections.deque en queue.LifoQueue die zich allemaal als een stack kunnen gedragen. We bekijken elk van deze implementaties later in het artikel in detail.

Stack vs. andere datastructuren

Begrijpen wat een stack is, wordt veel duidelijker als je ziet wat het niet is. De twee structuren die het vaakst met stacks worden vergeleken, zijn queues en standaard Python-lijsten.

Stack vs. queue

Een queue volgt het First-In-First-Out (FIFO)-principe, het tegenovergestelde van een stack. In een queue worden elementen achteraan toegevoegd en vooraan verwijderd, zoals een rij mensen bij een loket. Stacks en queues zijn allebei lineair en beperken allebei hoe je elementen benadert, maar ze doen dat in tegenovergestelde richting. 

De verkeerde kiezen kan stilletjes de logica van een algoritme breken. Vervang je bijvoorbeeld een stack door een queue in een depth-first search, dan verandert die in een breadth-first search, met totaal andere resultaten.

Stack vs. list

Een standaard Python-lijst biedt daarentegen willekeurige toegang. Je kunt elementen op elke index lezen, invoegen of verwijderen met operaties zoals my_list[3] of my_list.insert(2, value). Die flexibiliteit is vaak handig, maar betekent ook dat niets je tegenhoudt om per ongeluk elementen in het midden van de structuur te benaderen of te wijzigen. 

Als je een algoritme implementeert dat afhankelijk is van strikte LIFO-volgorde, zoals backtracking, syntaxisparsing of undo-functionaliteit, kan de onbegrensde aard van een lijst subtiele bugs introduceren.

Precies daarom is het beperkte toegangsprincipe van een stack een feature, geen beperking. Door alleen interactie met het top-element toe te staan, dwingt een Python-stack correctheid af by design. Je kunt niet per ongeluk van de verkeerde kant dequeuen of een element overschrijven dat diep in de structuur zit. 

In algoritmeontwerp zijn dit soort beperkingen juist wat je logica schoon en je code voorspelbaar houdt.

Kernoperaties van een stack en tijdcomplexiteit

Nu we weten wat een Python-stack is en hoe die verschilt van andere structuren, kijken we naar de basisoperaties die elke stack ondersteunt en analyseren we hoe efficiënt ze zijn.

Standaard stackoperaties

Elke stackimplementatie is gebaseerd op een kleine set standaardoperaties, ongeacht de programmeertaal. Dit zijn de bouwstenen die je telkens gebruikt als je met een stack werkt.

Push voegt een element toe aan de top van de stack. Als de stack [A, B] bevat en je pusht C, wordt de stack [A, B, C], met C bovenaan.

Pop verwijdert en retourneert het element dat nu bovenaan staat. In het voorbeeld hierboven retourneert poppen van [A, B, C] C en blijft [A, B] over.

Peek (ook wel top genoemd) laat je het bovenste element bekijken zonder het te verwijderen. Dit is handig als je logica het huidige top-waarde moet inspecteren voordat je besluit te poppen, een patroon dat vaak voorkomt bij expressieparsing en problemen met gebalanceerde haakjes.

Naast die drie kernoperaties zijn twee hulpmethoden belangrijk voor veilige, foutvrije stackcode:

• is_empty() controleert of de stack elementen bevat. Pop of peek aanroepen op een lege stack is een veelvoorkomende bron van runtimefouten, dus eerst op leegte controleren is een defensieve programmeergewoonte die je vroeg moet aanleren.

• size() retourneert het huidige aantal elementen in de stack. Dit helpt wanneer je wilt bijhouden hoe diep een recursie is gegaan of hoeveel items nog verwerkt moeten worden.

Tot slot is het de moeite waard een term te definiëren die je in studieboeken en sollicitaties tegenkomt: Stack Underflow. Dit is de fouttoestand die optreedt wanneer je probeert te poppen of peeken van een lege stack. Er is niets te verwijderen of te bekijken, dus de operatie is ongeldig. 

De exacte uitzondering of het gedrag hangt af van de implementatie. We zien hoe Python dit concreet afhandelt als we zo list, deque en LifoQueue bekijken.

Complexiteit analyseren

Een van de grootste redenen dat stacks zo veel worden gebruikt in algoritmes, is hun efficiëntie. Laten we de tijd- en ruimtecomplexiteit van elke operatie uitsplitsen.

Push is O(1). In een efficiënte stackimplementatie is het toevoegen van een element aan de top een operatie in constante tijd. De stack hoeft geen bestaande elementen te verschuiven of te herordenen. Het plaatst het nieuwe item simpelweg aan het einde. Dit geldt voor zowel collections.deque als, in het geamortiseerde geval, de ingebouwde list van Python.

Pop is O(1). Het bovenste element verwijderen is even snel. De stack benadert direct de laatste positie, retourneert de waarde en vermindert zijn interne teller. Ook hier is geen verschuiving van andere elementen nodig.

Peek is O(1). Het bovenste element bekijken zonder het te verwijderen is een directe indexopzoeking en dus eveneens constante tijd.

Zoeken is O(n). Hier zie je de bewuste trade-off van stacks. Als je wilt weten of een specifieke waarde ergens in de stack voorkomt, zit er niets anders op dan alle n elementen van boven naar beneden te doorzoeken. 

Stacks zijn niet ontworpen voor willekeurige lookups. Ze leveren zoekmogelijkheden in voor snelle, voorspelbare push en pop. Als je usecase vaak zoeken vereist, past een andere datastructuur, zoals een set of dictionary, beter.

Ruimtecomplexiteit is O(n). Een stack met n elementen vereist geheugen evenredig aan n. Er is geen verborgen overhead naast wat nodig is om de elementen zelf op te slaan, plus een kleine constante voor het interne beheer van de structuur.

Hier is een korte samenvatting:

De kernboodschap is dat een Python-stack is geoptimaliseerd voor snelle invoeging en verwijdering aan één kant. Zolang je hem gebruikt waarvoor hij bedoeld is, zoals het beheren van geordende, LIFO-toegang, levert hij uitstekende performance. Als je merkt dat je regelmatig door een stack zoekt, is dat een signaal om je keuze van datastructuur te heroverwegen.

Python-stackimplementaties

Met de theorie en complexiteitsanalyse achter de rug is het tijd om echte code te schrijven. Python biedt drie primaire manieren om een stack te implementeren, elk met eigen sterke punten en trade-offs. Laten we ze alle drie doorlopen en zien welke het beste past bij onze usecase.

Python-stack met de ingebouwde list

De meest rechttoe rechtaan manier om een Python-stack te maken, is met de ingebouwde list. Omdat lijsten dynamische arrays zijn die toevoegen en verwijderen aan het einde ondersteunen, sluiten ze natuurlijk aan bij het gedrag van een stack. 

De methode .append() fungeert als push, en .pop() zonder argument verwijdert en retourneert het laatste element. Hieronder een codevoorbeeld:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

Dit werkt prima, maar je moet wel zorgvuldig omgaan met de lege-stack-situatie. In Python gooien zowel .pop() als stack[-1] een IndexError als de lijst leeg is. Zo geeft Python de eerder gedefinieerde Stack Underflow-toestand door. 

Best practice is om deze aanroepen in een try/except-blok te wikkelen of op leegte te controleren voordat je de top benadert, zoals in het volgende voorbeeld:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

Er is één prestatie-nuance die het begrijpen waard is. Python-lijsten zijn gebaseerd op dynamische arrays. Als je .append() aanroept, is die operatie meestal direct O(1). Maar als de interne array geen vooraf gereserveerde ruimte meer heeft, moet Python een nieuw, groter geheugenblok reserveren en alle bestaande elementen daarheen kopiëren. 

Deze incidentele reallocatie maakt .append() een geamortiseerde O(1)-operatie in plaats van strikt O(1). In de praktijk is de vertraging zeldzaam en kort, maar in latency-gevoelige of realtime-toepassingen kan die onvoorspelbaarheid ertoe doen.

Ondanks deze kanttekening zijn .append() en .pop() op een lijst de voorkeursaanpak voor de meeste eenvoudige stacktaken. Geen imports, vertrouwde syntaxis en brede ontwikkelaarsbekendheid maken het een goede standaardkeuze, vooral voor scripten, prototyping en interviewproblemen waar eenvoud telt.

Python-stack met collections.deque

Als je consistente O(1)-prestaties nodig hebt zonder de incidentele reallocatie-lag, is collections.deque de aanbevolen upgrade. De naam staat voor "double-ended queue", maar het werkt perfect als een high-performance Python-stack. Ons eerdere voorbeeld ziet er met de deque-syntaxis zo uit:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

Let op dat de interface identiek is aan de list-gebaseerde aanpak. .append(), .pop() en [-1] werken hetzelfde. Het IndexError-gedrag bij lege toegang is ook ongewijzigd, dus je foutafhandeling hoeft niet aangepast te worden:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

Het cruciale verschil zit onder de motorkap. Een deque is geïmplementeerd als een dubbel gekoppelde lijst van blokken met vaste grootte in plaats van één array. Dit betekent dat hij nooit de hele structuur hoeft te heralloceren en kopiëren wanneer deze groeit. 

Elke .append() en .pop() is een echte, gegarandeerde O(1)-operatie: niet geamortiseerd, maar consistent. Voor algoritmisch werk waarbij je duizenden of miljoenen keren pusht en popt, telt die consistentie op.

Python-stack met queue.LifoQueue

De standaardbibliotheek van Python bevat ook queue.LifoQueue, een stackimplementatie die specifiek is ontworpen voor multithreaded programma's. De "LIFO" in de naam bevestigt dat hij Last-In-First-Out volgt, maar de interface en het gedrag verschillen flink van de vorige twee benaderingen. Zie het in dit voorbeeld:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

Het eerste dat opvalt, is de syntaxiswijziging. Push wordt .put() en pop wordt .get(). Deze benaming komt uit het producer-consumer-patroon van de queue-module, waarin één thread items "put" en een andere ze "get".

Er zijn twee belangrijke gedragsverschillen om op te letten. 

Ten eerste heeft LifoQueue geen veilige peek-methode. Er is geen ingebouwde manier om het top-element te bekijken zonder het te verwijderen. Je zou interne attributen kunnen benaderen, maar dat ondermijnt in een multithreaded context het doel van een thread-safe class en riskeert race conditions.

Ten tweede gooit LifoQueue geen IndexError als je probeert te getten van een lege stack. Standaard blokkeert .get(). Het pauzeert de aanroepende thread en wacht onbeperkt tot een andere thread een item op de stack zet. Wil je niet-blokkerend gedrag, geef dan block=False mee; dan wordt een queue.Empty-exceptie gegooid. Zie het voorbeeld:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

Door het interne lockmechanisme dat LifoQueue thread-safe maakt, hebben de operaties meer overhead dan bij list of deque. Daardoor is het een slechte keuze voor singlethreaded code. Gebruik LifoQueue uitsluitend wanneer je een natuurlijke multithreaded situatie met gelijktijdige toegang hebt, en kies in alle andere gevallen voor deque of list.

De juiste stackimplementatie in Python kiezen

Met drie opties beschikbaar, hier een vergelijking naast elkaar om je keuze te helpen:

Hier is mijn besliskader om de beste implementatie te kiezen:

• Gebruik list wanneer je snel een stack nodig hebt zonder imports, zoals in scripts, notebooks en whiteboard-interviews. 

• Gebruik collections.deque wanneer je algoritmische code schrijft, grote datasets verwerkt of iets bouwt waarbij performance telt. 

• Gebruik queue.LifoQueue alleen wanneer je een natuurlijke multithreaded situatie met gelijktijdige toegang hebt.

Je komt misschien ook tutorials tegen die een Python-stack from scratch implementeren met een aangepaste linked-listclass, waarbij elke node een waarde en een pointer naar de node eronder heeft. Naar mijn mening is dat zeker een waardevolle oefening om je begrip te verdiepen van hoe stacks intern werken en hoe geheugenreferenties aaneengeschakeld zijn. 

In productiecode in Python is een linked-list-stack echter bijna altijd trager dan een deque vanwege de overhead van het creëren van afzonderlijke node-objecten. Voor echt Python-werk geeft collections.deque je de beste combinatie van snelheid, duidelijkheid en betrouwbaarheid.

Toepassingen van Python-stacks

Weten hoe je een Python-stack implementeert is maar de helft van het verhaal. De echte waarde van stacks wordt duidelijk wanneer je ziet hoe ze problemen oplossen die zonder LIFO-volgorde veel complexer zouden zijn. Laten we kijken naar drie klassieke toepassingen die voortdurend opduiken in coding-interviews, softwaresystemen en algoritmeontwerp.

Gebalanceerde haakjes controleren

Het probleem van gebalanceerde haakjes is een van de meest gestelde stackvragen in technische interviews. Gegeven een string met haakjes, zoals (), [] en {}, moet je bepalen of elk openingshaakje een corresponderend sluitingshaakje in de juiste volgorde heeft.

De logica past perfect bij een stack. Terwijl je de string van links naar rechts scant, push je elk openingshaakje op de stack. Wanneer je een sluitingshaakje tegenkomt, pop je de top van de stack en controleer je of die overeenkomt.

Als de stack leeg is wanneer je probeert te poppen, of als het gepopte haakje niet overeenkomt, is de string ongebalanceerd. Na het verwerken van de hele string zou de stack leeg moeten zijn. Overgebleven openingshaakjes betekenen dat er iets nooit is gesloten. Laten we dit in actie zien:

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

Laten we "{[()]}" stap voor stap nalopen om de stack in actie te zien:

De stack is aan het einde leeg, dus de expressie is gebalanceerd.

Dezelfde logica gaat veel verder dan interviewproblemen. Compilers en interpreters gebruiken dit om syntaxis te valideren en te garanderen dat elk openingstag, haakje of scheidingsteken in broncode een juiste match heeft. 

Als je ooit de melding SyntaxError: unexpected EOF in Python hebt gezien, dan heb je een vorm van deze controle in actie gezien. HTML-validators, JSON-parsers en zelfs linters voor configuratiebestanden vertrouwen allemaal op variaties van deze stackbenadering.

Depth-first search (DFS) implementeren

Depth-first search is een van de fundamentele algoritmes voor graaftraversal, en een stack is de datastructuur die het aandrijft. Het idee is simpel. Begin bij een node, verken zo ver mogelijk langs één tak voordat je terugspoort om de volgende te proberen. De LIFO-aard van een Python-stack zorgt ervoor dat dit "eerst de diepte in"-gedrag vanzelf ontstaat.

Inleidende cursussen leren DFS meestal met recursie, waarbij de call stack impliciet de traversale volgorde beheert. De recursieve aanpak heeft echter een praktische beperking. De standaard recursielimiet van Python is 1.000 frames. 

Voor grote of diep geneste grafen leidt dit tot een RecursionError. De iteratieve versie, die een expliciete stack gebruikt, voorkomt dit probleem en geeft je volledige controle over de traversal.

Laten we een codevoorbeeld bekijken. We doen een DFS door de volgende graaf:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

Laten we de uitvoering nalopen om te zien hoe de stack de traversal stuurt:

Let op hoe de LIFO-volgorde het algoritme dwingt om de takken A → B → D en A → B → E → F volledig te verkennen voordat er wordt teruggespoord om C te bezoeken. Dit onderscheidt depth-first search van breadth-first search, die een queue gebruikt en eerst alle buren op de huidige diepte verkent voordat er dieper wordt gegaan. 

Het iteratieve DFS-patroon dat je hier ziet, werkt voor bomen, gerichte grafen en ongerichte grafen. Het vormt ook de basis voor geavanceerdere algoritmes zoals topologische sortering, cycledetectie en het oplossen van doolhof- en puzzelproblemen.

Undo/redo-operaties beheren

Als je ooit een teksteditor, tekenprogramma of spreadsheet hebt gebruikt, heb je ongemerkt vertrouwd op undo en redo. Het mechanisme is elegant en draait precies op twee stacks.

Een undo-stack slaat elke actie of staat op terwijl de gebruiker wijzigingen aanbrengt. Wanneer de gebruiker undo triggert, wordt de huidige staat van de undo-stack gepopt en op een redo-stack gepusht.

Als de gebruiker vervolgens redo triggert, wordt de staat van de redo-stack gepopt en weer op de undo-stack gepusht. Maakt de gebruiker na een undo een gloednieuwe wijziging, dan wordt de redo-stack geleegd. Je kunt niets opnieuw doen dat is overschreven door een nieuwe actie. Zie dit voorbeeld:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

De stroom van staten tussen de twee stacks volgt een duidelijk patroon:

Dit tweestackpatroon is niet beperkt tot teksteditors. Het komt overal voor waar gebruikers achteruit en vooruit moeten kunnen stappen door een reeks wijzigingen (wat vrijwel overal is):

• Software voor beeldbewerking
• Rollbacken van databasetransacties
• Beheer van spelstatus

Het onderliggende principe is steeds hetzelfde. De ene Python-stack volgt de geschiedenis, de andere de toekomst, en LIFO zorgt ervoor dat je altijd eerst terugkeert naar de meest recente staat.

Geavanceerde concepten rond Python-stacks

Stacks spelen ook een belangrijke rol onder de motorkap van elk Python-programma dat je draait, en ze voeden optimalisatietechnieken die de tijdcomplexiteit van bepaalde problemen drastisch kunnen verlagen. Laten we beide geavanceerde dimensies bekijken.

De call stack begrijpen

Elke keer dat je in Python een functie aanroept, gebeurt er achter de schermen iets dat je niet direct beheert. Python pusht een nieuw frame op een interne datastructuur die de call stack heet. Dit frame bevat de lokale variabelen van de functie, de parameters en een pointer terug naar de coderegel die de aanroep initieerde. 

Wanneer de functie klaar is met uitvoeren, wordt het frame van de call stack gepopt en keert de controle terug naar de aanroeper.

Je kunt dit gedrag inspecteren met een eenvoudig voorbeeld:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

Wanneer function_c draait, heeft de call stack vier frames die op elkaar gestapeld zijn. Als elke functie voltooit, wordt zijn frame in LIFO-volgorde gepopt. function_c eindigt eerst, dan function_b, dan function_a en tot slot de main-modulescope.

Dit is precies het mechanisme dat recursie laat werken. Elke recursieve aanroep pusht een nieuw frame met eigen lokale variabelen, en de resultaten rollen af wanneer frames worden gepopt. Laten we dit zien met een voorbeeld:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

Het probleem ontstaat wanneer recursie te diep gaat. Python stelt standaard een recursielimiet van 1.000 frames in om te voorkomen dat de call stack al het beschikbare geheugen opslokt. Als je recursieve functie deze limiet overschrijdt, gooit Python een RecursionError. Zie dit voorbeeld:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

Je kunt deze limiet controleren en aanpassen met de sys-module, al moet je verhogen met voorzichtigheid doen:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

Belangrijk om te onthouden is dat de call stack een systeemniveau-structuur is die door de Python-interpreter zelf wordt beheerd. Je kunt er niet direct naartoe pushen of van poppen. De list-, deque- en LifoQueue-stacks die we eerder bouwden, zijn door de gebruiker gedefinieerde datastructuren die in het heapgeheugen van je programma leven. Ze dienen verschillende doelen, maar volgen hetzelfde LIFO-principe.

Monotone stacks gebruiken

Een monotone stack is een gespecialiseerde variant waarbij de elementen in niet-afnemende of niet-toenemende volgorde worden bijgehouden (of soms strikt stijgend/dalend, afhankelijk van het probleem). Telkens wanneer je een nieuw element pusht, pop je eerst alle elementen die de ordeningsbeperking zouden schenden. Het is de sleutel tot het oplossen van een hele klasse optimalisatieproblemen in lineaire tijd.

Het klassieke voorbeeld is het Next Greater Element-probleem: Gegeven een array met integers, vind voor elk element het eerste element rechts dat groter is. Een brute-forcebenadering met geneste lussen draait in O(n²). Voor elk element scan je alles rechts ervan. Een monotone stack lost dit op in O(n).

Het inzicht is dat je de array van rechts naar links doorloopt, met een dalende stack. Voor elk element pop je alles van de stack dat kleiner dan of gelijk aan het element is. Die waarden kunnen nooit het "volgende grotere element" zijn voor een toekomstig element links. 

Wat na het poppen bovenop de stack blijft liggen, is het antwoord voor het huidige element. Vervolgens push je het huidige element op de stack. Zie dit codevoorbeeld. Merk op dat -1 in dit geval betekent dat er rechts van dat getal geen groter element is:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

Laten we de uitvoering nalopen om te zien hoe de monotone eigenschap behouden blijft:

Merk op dat elk element precies één keer op de stack wordt gepusht en hoogstens één keer wordt gepopt tijdens de hele traversal. Daarom is de totale tijdcomplexiteit O(n), ondanks de binnenste while-lus. Het cumulatieve aantal push- en popoperaties over alle iteraties overschrijdt nooit 2n.

Zoals ik eerder zei, zijn er veel soortgelijke problemen die het monotone-stackpatroon versnelt van O(n²) naar O(n). Daaronder:

• Stock span-probleem: Voor de prijs van elke dag: vind hoeveel opeenvolgende voorafgaande dagen een lagere of gelijke prijs hadden.
• Grootste rechthoek in een histogram: Vind de maximale rechthoekige oppervlakte die onder een staafdiagram past (een klassieke moeilijke interviewvraag).
• Dagelijkse temperaturen: Gegeven een array met dagelijkse temperaturen, vind hoeveel dagen je moet wachten op een warmere dag.
• Regenwater opvangen: Bereken hoeveel regenwater er wordt opgevangen tussen staven van verschillende hoogte.

In elk geval is het kernidee hetzelfde: de monotone beperking laat je elementen weggooien die de toekomstige resultaten niet meer kunnen beïnvloeden, waardoor de zoekruimte effectief wordt teruggebracht van kwadratisch naar lineair.

Conclusie

De stack is een van de eerste datastructuren die elke programmeur leert en een van de laatste waarvoor je nieuwe toepassingen blijft vinden, wat ironisch genoeg het tegenovergestelde is van zijn Last-In-First-Out-aard. 

In dit artikel hebben we gezien hoe deze LIFO-beperking nuttig kan zijn in veel verschillende scenario's, van het valideren van geneste haakjes en het aansturen van depth-first traversals tot het beheren van undo/redo-staat en het optimaliseren van arrayproblemen met monotone stacks. 

Als er één aanbeveling is om mee te nemen, is het deze: gebruik collections.deque als je standaard Python-stackimplementatie, tenzij je een specifieke reden hebt om dat niet te doen. 

Als volgende stap raad ik je aan onze cursus over Data Structures and Algorithms in Python te volgen.