Stack in Python: definitie, implementaties en voorbeelden

Home » Python » Stack in Python: definitie, implementaties en voorbeelden

Stacks in Python zijn een van die kernconcepten die steeds weer opduiken zodra je de interne werking van echte programma's begint te bekijken. – van functieaanroepen tot de ongedaanmaakfunctie in editors en hoe browsers je navigatiegeschiedenis verwerken. Zelfs als je voornamelijk applicatiecode op hoog niveau schrijft, geeft inzicht in hoe stacks werken (en hoe je ze correct implementeert in Python) je een aanzienlijk voordeel bij het debuggen van lastige problemen of het ontwerpen van efficiënte algoritmen.

In deze handleiding leggen we uit wat een stack is, wat "Last In, First Out" in de praktijk betekent, welke bewerkingen elke stack zou moeten ondersteunen en hoe je stacks in Python implementeert met behulp van verschillende tools zoals lijsten, collections.deque, queue.LifoQueue en enkelvoudig gekoppelde lijsten.We bespreken ook de prestaties, het geheugengedrag, de threadveiligheid en praktijkvoorbeelden waarin een stack precies de juiste datastructuur is.

Wat is een stack in Python?

Een stack is een lineaire datastructuur die de Last-In, First-Out (LIFO)-regel volgt: het laatste element dat je op de stack plaatst, is het eerste element dat er weer uitgehaald wordt.Je kunt het conceptueel vergelijken met een stapel borden, een stapel boeken of een stapel kleren: je kunt alleen spullen van de bovenkant toevoegen of verwijderen, niet van het midden of de onderkant.

Dit LIFO-gedrag betekent dat wanneer je elementen invoegt (push), elk nieuw element bovenop de vorige komt te liggen, en wanneer je elementen verwijdert (pop), je altijd het laatst toegevoegde element neemt.Je slaat nooit een stap over naar het derde of vierde element zonder eerst de elementen daarboven te verwijderen.

In Python is een stack geen op zichzelf staand, ingebouwd type; in plaats daarvan implementeren we stacks bovenop bestaande datastructuren zoals lijsten, deques, LIFO-wachtrijen of aangepaste gekoppelde lijsten.Elke optie heeft zijn eigen voor- en nadelen wat betreft prestaties, geheugengebruik en threadveiligheid.

De twee fundamentele bewerkingen op elke stack zijn push en pop, maar praktische implementaties bieden vaak een paar extra hulpmiddelen zoals peek (of top), groottecontrole en controle op lege stacks.Deze extra bewerkingen maken het gebruik van stacks in daadwerkelijke toepassingen veel handiger.

Voordat je aan de slag gaat met de code, is het belangrijk om een ​​cruciale eigenschap in gedachten te houden: een goed geïmplementeerde stack voert push- en pop-bewerkingen uit in constante tijd, oftewel O(1), ongeacht hoeveel elementen erin opgeslagen zijn.Die voorspelbare prestaties zijn een van de belangrijkste redenen waarom stacks zo veelvuldig worden gebruikt in algoritmen en systemen op laag niveau.

Kernbewerkingen en -gedrag van de stack

Elke bruikbare stack in Python, ongeacht de onderliggende implementatie, draait om een ​​handvol gemeenschappelijke bewerkingen die het gedrag ervan bepalen.Het begrijpen hiervan is veel belangrijker dan het onthouden van specifieke methodenamen in elke bibliotheek.

De klassieke bewerking om een ​​element in te voegen heet 'push': je neemt een waarde en plaatst deze bovenop de bestaande stapel.Na een push wordt het nieuwe element het element dat als eerste wordt teruggegeven door de volgende pop-bewerking.

Om elementen te verwijderen gebruiken we `pop`, waarmee het bovenste element van de stapel wordt gehaald en teruggegeven.Als de stapel leeg is, moet een robuuste implementatie ofwel een foutmelding geven, ofwel een specifieke waarde retourneren die duidelijk aangeeft dat er geen elementen aanwezig zijn.

De meeste stack-implementaties bieden ook een peek- of top-bewerking, waarmee je het element dat zich momenteel bovenaan bevindt kunt bekijken zonder het van de stack te verwijderen.Dit is vooral handig in algoritmes die de volgende waarde moeten controleren, maar deze ook willen bewaren voor later gebruik.

Twee extra hulpfuncties die je vaak tegenkomt, zijn `isempty` (of `isEmpty`) en `size`. Deze controleren of de stack elementen bevat en hoeveel elementen dat zijn.In Python kunnen zowel de ingebouwde functie `len()` als booleaanse controles intern hergebruikt worden om deze hulpfuncties met minimale code te implementeren.

Wat betreft de tijdscomplexiteit garandeert een goed ontworpen stack dat push, pop, peek en isEmpty allemaal in constante tijd O(1) worden uitgevoerd, en dat size O(1) of O(n) kan zijn, afhankelijk van of de implementatie de lengte als een apart veld opslaat.Cruciaal is dat stacks geen efficiënte willekeurige toegang tot willekeurige posities ondersteunen, zoals arrays dat wel doen.

Wanneer en waarom een ​​stapel gebruiken?

Stacks komen goed van pas wanneer je te maken hebt met processen die je later in de exacte omgekeerde volgorde van de uitgevoerde stappen moet doorlopen.Elke situatie waarin je vanzelfsprekend denkt: "Ik moet dit van achter naar voren ongedaan maken", is een goede kandidaat voor een stapel.

Een klassieke analogie uit de praktijk is het demonteren van een machine: je verwijdert schroeven en onderdelen in een bepaalde volgorde, en als je de machine correct wilt terugplaatsen, moet je ze in precies de tegenovergestelde volgorde terugplaatsen.Het opstapelen van deze onderdelen sluit perfect aan op die workflow.

In software is een van de meest fundamentele toepassingen van stacks de functieaanroepstack: elke keer dat een functie een andere functie aanroept, worden parameters, lokale variabelen en retouradressen op een stack in het geheugen geplaatst.Wanneer een functie terugkeert, wordt het frame ervan verwijderd, waardoor de status van de aanroeper wordt hersteld.

Mechanismen voor ongedaan maken en opnieuw uitvoeren in tekstverwerkers, tekenprogramma's, IDE's en vele andere toepassingen zijn doorgaans gebaseerd op stapels acties of toestanden.Elke gebruikersactie wordt toegevoegd aan een 'ongedaan maken'-stapel; wanneer je op Ctrl+Z drukt, verwijdert de applicatie de meest recente actie en maakt deze ongedaan.

Stacks worden ook veel gebruikt in algoritmen zoals dieptezoekalgoritmen (DFS) in grafieken, expressie-evaluatie (het ontleden van haakjes, operatoren en operanden), backtracking en voor het implementeren van de browsergeschiedenis, waarbij elke bezochte pagina wordt toegevoegd en de "Terug"-toets de laatst bezochte pagina verwijdert.Deze scenario's profiteren van de natuurlijke LIFO-discipline die stacks afdwingen en die verband houden met de kern. programmeerlogica.

Een stack implementeren met Python-lijsten.

De eenvoudigste manier om een ​​stack in Python te bouwen is door gebruik te maken van het ingebouwde lijsttype, waarbij je de `append()`-methode gebruikt om elementen toe te voegen en `pop()` om het laatste element te verwijderen.Lijsten zijn in feite dynamische arrays en bieden alle basisfunctionaliteit die een stack nodig heeft.

Een minimale stack gebaseerd op lijsten zou hulpfuncties kunnen bieden zoals `create_stack`, `push`, `pop`, `isempty` en `show` (of `top`, `size`, enz.), die intern allemaal een eenvoudige Python-lijstinstantie manipuleren.Bijvoorbeeld, create_stack kan gewoon een lege lijst retourneren, en isempty kan worden gedefinieerd als len(stack) == 0.

Een veelvoorkomend patroon is om het einde van de lijst als de bovenkant van de stapel te beschouwen, waardoor `stack.append(item)` een push uitvoert en `stack.pop()` een pop uitvoert.Hierdoor blijven beide bewerkingen gemiddeld in constante tijd uitgevoerd, en blijft de code zeer leesbaar en kort.

Als je de voorkeur geeft aan meer gestructureerde code, kun je dit gedrag verpakken in een aangepaste Stack-klasse die de lijst inkapselt en duidelijke methoden zoals push(), pop(), peek(), is_empty() en size() beschikbaar stelt.Door inkapseling is het later gemakkelijker om de stack uit te breiden met extra controles of logboekregistratie.

Lijsten zijn relatief geheugenefficiënt omdat elk element zijn waarde direct opslaat zonder de overhead van een verwijzing naar het volgende knooppunt, zoals je die bijvoorbeeld in een gekoppelde lijst ziet.Bovendien zijn veel Python-ontwikkelaars al zeer vertrouwd met lijstsemantiek, waardoor deze aanpak gemakkelijk aan te leren en te onderhouden is.

Er is echter een belangrijke kanttekening: lijsten worden ondersteund door aaneengesloten geheugen, dus wanneer ze groter worden dan de gereserveerde ruimte, moet Python een nieuw, groter blok toewijzen en de elementen kopiëren.Meestal wordt deze herallocatie afgeschreven en is deze onzichtbaar, maar soms kan een enkele append()-aanroep merkbaar trager zijn dan andere.

Een ander nadeel is dat Python-lijsten niet thread-safe zijn voor gelijktijdige wijzigingen door meerdere threads, wat een probleem kan worden als je een stack wilt gebruiken in multithreaded programma's.Voor dergelijke situaties kunt u alternatieven zoals queue.LifoQueue overwegen in plaats van gewone lijsten.

collections.deque gebruiken als stack

De `collections`-module van Python biedt een `deque` (een wachtrij met twee uiteinden), die vaak beter geschikt is dan lijsten wanneer je frequent elementen moet toevoegen en verwijderen.Een deque is geoptimaliseerd voor snelle toevoegingen en verwijderingen van elementen aan beide uiteinden.

Bij het gebruik van een deque als stack voeg je doorgaans items toe met de `append()`-methode en verwijder je ze met `pop()`, waarbij je de rechterkant als de bovenkant van de stack beschouwt.Internally is deque geïmplementeerd als een dubbelgelinkte lijst van blokken, waardoor de grote herallocaties die lijsten soms nodig hebben, worden vermeden.

Het maken van een stack met behulp van deque is eenvoudig: roep deque() aan om een ​​lege container te verkrijgen, definieer vervolgens bewerkingen zoals push(stack, item) die stack.append(item) aanroepen en pop(stack) die controleert of de stack niet leeg is en vervolgens stack.pop() aanroept.Extra hulpmiddelen zoals show(stack) kunnen eenvoudig de huidige inhoud afdrukken.

Omdat deque specifiek is afgestemd op efficiënte invoeging en verwijdering aan beide uiteinden, behouden push- en pop-bewerkingen een consistente O(1)-prestatie, zelfs wanneer de structuur groeit.Dit kan ervoor zorgen dat deques de voorkeur verdienen boven lijsten voor grote of veelgebruikte stacks.

In code met één thread is `deque` meestal een van de beste standaardkeuzes voor het implementeren van stacks in Python, omdat het goede prestaties, een overzichtelijke API en geen verrassingen met betrekking tot capaciteitslimieten combineert.Het gedraagt ​​zich ook voorspelbaarder qua timing wanneer de stapel erg groot wordt.

Stacks implementeren met queue.LifoQueue

Wanneer threadveiligheid belangrijk wordt, is de LifoQueue-klasse van de queue-module de aangewezen optie voor het implementeren van een stack in Python.Een LifoQueue is in essentie een thread-veilige stack met ingebouwde vergrendelingsmechanismen.

Om een ​​nieuwe LifoQueue-gebaseerde stack te creëren, instantieert u LifoQueue met een optionele parameter maxsize, die het maximale aantal elementen aangeeft dat de stack kan bevatten.Internaal regelt de wachtrij het wachten, blokkeren en signaleren tussen threads, ongeacht of de stack vol of leeg is.

Een element op een LifoQueue-stack plaatsen gebeurt met `put(item)`, wat kan blokkeren als de stack al vol is.Het verwijderen van elementen van de stack gebeurt met get(), wat ook kan blokkeren als de stack leeg is, totdat er een nieuw item beschikbaar is.

Extra hulpmethoden zoals qsize(), full() en empty() stellen je in staat om de huidige status van de stack op een threadveilige manier te inspecteren.Bijvoorbeeld, full() geeft aan of er geen elementen meer toegevoegd kunnen worden, terwijl empty() aangeeft of er nog iets verwijderd kan worden.

Het belangrijkste compromis bij het gebruik van LifoQueue is de prestatie: alle synchronisatie die nodig is om het thread-safe te maken, introduceert overhead, waardoor bewerkingen trager zijn dan die op lijsten of deques.In CPU-intensieve, prestatiegerichte scenario's kan die overhead van belang zijn, maar voor veel multithreaded applicaties zijn de veiligheid en correctheid veel belangrijker.

Het is belangrijk om te weten dat threading in Python niet automatisch betekent dat threads op verschillende CPU-cores worden uitgevoerd vanwege de Global Interpreter Lock (GIL), maar LifoQueue beschermt je gedeelde stack wel tegen raceomstandigheden en inconsistente toestanden.Voor echte parallelle verwerking over meerdere cores heb je multiprocessing of andere benaderingen nodig, maar het concept van thread-safe stacks blijft relevant voor I/O-intensieve of coöperatieve workloads.

Stackimplementatie met behulp van een enkelvoudig gekoppelde lijst

Een meer "klassieke" informaticamanier om een ​​stack in Python te bouwen, is door gebruik te maken van een enkelvoudig gekoppelde lijst, waarbij elk knooppunt een waarde en een pointer (referentie) naar het volgende knooppunt opslaat.Deze aanpak levert een dynamisch formaat stack op die niet afhankelijk is van aaneengesloten geheugen.

Je definieert doorgaans een Node-klasse met attributen voor de waarde en de volgende referentie, en implementeert vervolgens een Stack-klasse die een hoofdknooppunt en een grootteteller bijhoudt.Vaak wordt een dummy-hoofdknooppunt gebruikt om randgevallen te vereenvoudigen wanneer de stapel leeg is.

In dit ontwerp wordt de bovenkant van de stapel weergegeven door het knooppunt direct na de kop.Om een ​​waarde toe te voegen, maak je een nieuw knooppunt aan, stel je de volgende verwijzing ervan in op de huidige head.next en werk je vervolgens head.next bij zodat deze naar het nieuwe knooppunt wijst, waarbij je de grootte gaandeweg verhoogt.

Het verwijderen van een element van de stack houdt in dat eerst wordt gecontroleerd of de stack leeg is, vervolgens het knooppunt wordt genomen waarnaar `head.next` wijst, `head.next` naar het volgende knooppunt wordt verplaatst, de grootte wordt verlaagd en de verwijderde waarde wordt geretourneerd.Deze bewerking heeft een constante tijdscomplexiteit omdat er slechts een paar pointerupdates nodig zijn.

Extra methoden zoals getSize(), isEmpty() en peek() zijn eenvoudig te implementeren met deze structuur: size wordt bijgehouden als een integer, isEmpty kan controleren of size nul is, en peek retourneert head.next.value als de stack niet leeg is.Je kunt ook een __str__-methode definiëren om een ​​leesbare tekenreeks te genereren met alle elementen van de stack.

De voordelen van een op gekoppelde lijsten gebaseerde stack zijn onder andere dynamische groei zonder herallocatie en voorspelbare O(1)-prestaties voor push en pop, zelfs wanneer de structuur groot wordt.Geheugen wordt knooppunt voor knooppunt toegewezen, wat voordelig kan zijn in systemen met gefragmenteerd geheugen.

De nadelen zijn de extra geheugenoverhead voor pointers (elk knooppunt slaat minstens één referentie op) en de omslachtigere, complexere code in vergelijking met lijsten of deques.Voor veel alledaagse Python-programma's wegen die kosten niet op tegen de voordelen, maar de techniek blijft waardevol om te begrijpen en kan ideaal zijn voor specifieke, eenvoudige of educatieve scenario's.

Eigenschappen, efficiëntie en beperkingen van stacks

Conceptueel gezien gedraagt ​​een stack zich als een stapel objecten waarvan alleen de bovenste toegankelijk is: je interacteert altijd eerst met het laatst toegevoegde element.Deze beperking geeft stacks zowel hun kracht als hun beperkingen.

Bij een correcte implementatie zijn het lezen van het bovenste element, het invoegen van een nieuw element en het verwijderen van het bovenste element allemaal bewerkingen met een constante tijdscomplexiteit van O(1).Die consistente prestaties zijn uiterst nuttig bij het ontwerpen van algoritmes die duizenden of miljoenen keren gegevens moeten toevoegen en verwijderen.

Een belangrijke beperking is dat je niet efficiënt toegang hebt tot willekeurige elementen in het midden van een stapel zonder eerst alles erboven te verwijderen.Als je constant willekeurige toegang tot gegevens nodig hebt, is een andere datastructuur (zoals een lijst die op een array-achtige manier wordt gebruikt) wellicht geschikter.

Het geheugengebruik en de toewijzingspatronen zijn sterk afhankelijk van de gekozen implementatie: arrays (lijsten) gebruiken aaneengesloten geheugen en moeten soms opnieuw worden toegewezen, deques beheren geheugenblokken om grote kopieën te vermijden, en gekoppelde lijsten verspreiden knooppunten over de beschikbare geheugenlocaties.Elke aanpak brengt de afweging tussen overhead, locatie en capaciteit op een andere manier in kaart.

Vanuit een ontwerpperspectief zijn stapels opzettelijk eenvoudig: alleen de bovenkant is zichtbaar en er is geen sprake van indexering of invoeging in het midden.Deze eenvoud verkleint de kans op onbedoeld misbruik en stimuleert code die expliciet LIFO-workflows modelleert.

Overwegingen met betrekking tot Python-stacks en threading.

Als je Python-programma single-threaded is, kun je op basis van prestaties en gebruiksgemak gerust kiezen tussen lijsten en deques voor het implementeren van stacks.Beide bieden push- en pop-functionaliteit en zijn eenvoudig te integreren in reguliere code.

Zodra je meerdere threads introduceert die een stack delen, wordt het complexer: bewerkingen die op Python-niveau atomair lijken, kunnen op onverwachte manieren door elkaar lopen en de interne toestand verstoren.Gewone lijsten en deques zijn niet ontworpen om volledig thread-safe te zijn wanneer ze als gedeelde, veranderlijke stacks worden gebruikt.

Deques zijn relatief veilig als je uiterst gedisciplineerd bent en je beperkt tot het gebruik van alleen append() en pop() vanaf één uiteinde op een zorgvuldig gecontroleerde manier.Zelfs dan kunnen er echter subtiele problemen en raceomstandigheden optreden als meerdere threads tegelijkertijd lezen en schrijven zonder externe synchronisatie.

Voor robuuste multithreaded scenario's waarbij meerdere threads gelijktijdig elementen kunnen toevoegen en verwijderen, is queue.LifoQueue de aanbevolen stackimplementatie.De ingebouwde vergrendelingen en blokkeringsmechanismen zorgen ervoor dat gelijktijdige toegang de stack niet beschadigt.

Het nadeel is natuurlijk dat LifoQueue-bewerkingen (put en get) trager zijn dan methoden met een gewone lijst of deque vanwege de extra coördinatie tussen threads.Of die overhead ertoe doet, hangt af van de prestatie-eisen van uw applicatie en hoe vaak de stack wordt benaderd.

Het is ook belangrijk om te onthouden dat het threadingmodel van Python nog steeds onder de Global Interpreter Lock werkt. Zelfs met een threadveilige stack krijg je dus niet automatisch perfecte CPU-parallellisatie voor CPU-intensieve taken.Toch is een threadveilige stack een essentieel bouwblok voor I/O-intensieve programma's of ontwerpen die afhankelijk zijn van gelijktijdigheid in plaats van pure parallelle verwerking.

De juiste Python-stackimplementatie kiezen

Gezien al deze opties hangt de "beste" stack-implementatie in Python sterk af van je context: single-threaded versus multi-threaded, prestatiegevoeligheid, geheugengedrag en codehelderheid spelen allemaal een rol.Er bestaat geen enkele oplossing die perfect is voor elke situatie.

In eenvoudige scripts zonder multithreading of in leeromgevingen is het gebruik van een lijst als stack vaak meer dan voldoende: `append()` en `pop()` zijn intuïtief, snel voor de meeste workloads en vereisen vrijwel geen boilerplate-code.Lijsten zijn ook handig voor educatieve doeleinden, omdat ze gemakkelijk af te drukken en de inhoud te controleren zijn.

Wanneer je stack intensief gebruikt wordt, mogelijk veel elementen opslaat, en je consistent snelle push/pop-bewerkingen wilt met minder verrassingen met betrekking tot geheugenherallocaties, is `collections.deque` doorgaans de meest praktische keuze.De API komt grotendeels overeen met lijsten, waardoor migratie doorgaans probleemloos verloopt.

Als je van tevoren weet dat de stack door meerdere threads benaderd zal worden, vooral als er tegelijkertijd elementen worden toegevoegd en verwijderd, is `queue.LifoQueue` de veiligste optie.Het is misschien trager, maar het bespaart je de moeite om je eigen vergrendelingsprotocol te implementeren en helpt lastige raceomstandigheden te voorkomen.

De aanpak met enkelvoudig gekoppelde lijsten is ideaal wanneer je de interne werking van datastructuren wilt onderzoeken of uitleggen, of wanneer specifieke beperkingen het gebruik van aaneengesloten arrays of deques minder aantrekkelijk maken.Het geeft je ook volledige controle over de lay-out en het gedrag van knooppunten, ten koste van meer code en een beetje extra denkwerk.

Welke implementatie je ook kiest, het onderliggende idee blijft hetzelfde: je modelleert een Last-In, First-Out-structuur die elementen boven elkaar opslaat en je snelle, voorspelbare toegang geeft tot het laatst toegevoegde item.Als je eenmaal vertrouwd bent met dit model, wordt het veel gemakkelijker om na te denken over algoritmen en systeemgedrag waarbij stacks de meest voor de hand liggende oplossing zijn.

Door te begrijpen hoe stacks werken, welke bewerkingen ze ondersteunen, welke gangbare Python-implementaties ze hebben en welke afwegingen er zijn op het gebied van prestaties en threading, kunt u vol vertrouwen de versie kiezen en implementeren die het beste aansluit bij de behoeften van uw project. Tegelijkertijd schrijft u code die efficiënt en begrijpelijk blijft, ook na verloop van tijd..