Leer over LIFO-principes, hoe je stacks in Python implementeert met lists, deque en LifoDeque, en pas ze toe voor undo/redo-systemen of graaftraversals.
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.
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:
Operatie
Tijdcomplexiteit
Notities
Push
O(1)
Constante tijd. Geamortiseerd O(1) voor Python-lijsten
Pop
O(1)
Constante tijd
Peek
O(1)
Directe toegang tot het top-element
Zoeken
O(n)
Alle elementen moeten worden gescand
Ruimte
O(n)
Lineair in het aantal opgeslagen elementen
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 elementprint(stack[-1])Mogelijk gemaakt door
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 accessingif stack:
top = stack.pop()else:print("Stack is empty")Mogelijk gemaakt door
Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is emptyMogelijk gemaakt door
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()
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.dequeenqueue.LifoQueuedie 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]ofmy_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 pushtC, wordt de stack[A, B, C], metCbovenaan.Pop verwijdert en retourneert het element dat nu bovenaan staat. In het voorbeeld hierboven retourneert poppen van
[A, B, C]Cen 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,dequeenLifoQueuebekijken.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.dequeals, in het geamortiseerde geval, de ingebouwdelistvan 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
nelementen 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
nelementen vereist geheugen evenredig aann. 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:
Operatie
Tijdcomplexiteit
Notities
Push
O(1)
Constante tijd. Geamortiseerd O(1) voor Python-lijsten
Pop
O(1)
Constante tijd
Peek
O(1)
Directe toegang tot het top-element
Zoeken
O(n)
Alle elementen moeten worden gescand
Ruimte
O(n)
Lineair in het aantal opgeslagen elementen
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:Dit werkt prima, maar je moet wel zorgvuldig omgaan met de lege-stack-situatie. In Python gooien zowel
.pop()alsstack[-1]eenIndexErrorals 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:
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.dequede 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 dedeque-syntaxis zo uit: