Stapelmethoden

Stapelmethoden verwijzen naar methoden en algoritmen die gebruikmaken van een stapel (stack) datastructuur. Een stapel is een abstract datatype met LIFO-volgorde: het laatst toegevoegde element is het eerste dat eruit komt. Belangrijke operaties zijn push (een element toevoegen aan de bovenkant), pop (het bovenste element verwijderen en retourneren), peek of top (het bovenste element bekijken zonder te verwijderen) en isEmpty of size. Een stapel wordt vaak gebruikt om tijdelijk gegevens op te bergen tijdens berekeningen of om oproepframes bij programmeerprocessen te beheren.

Stapelimplementaties kunnen variëren. Een array-gebaseerde stapel biedt snelle push en pop maar kan beperkt zijn door de capaciteit, terwijl een dynamische array kan groeien na verloop van tijd. Een gekoppelde lijst-implementatie vereist geen vooraf bepaalde capaciteit maar introduceert extra geheugen- en pointer-overhead. In beide gevallen werken de basisoperaties doorgaans in O(1) tijd; de ruimtecomplexiteit is O(n) voor n elementen. Een vaste capaciteit kan leiden tot overflow bij een poging tot push op een volle stapel.

Toepassingen omvatten onder meer de evaluatie van wiskundige expressies (postfix-notatie en conversie van infix naar postfix), het beheren van oproepframes in programmeertalen (de call stack), en grafenalgoritmen zoals depth-first search, backtracking en undo-functionaliteit in software. Varianten bestaan uit meerdere stapels (bijvoorbeeld aparte stapels voor verschillende soorten informatie), thread-safe implementaties met synchronisatie, en persistente stapels die eerdere toestanden bewaren. De keuze voor implementatie hangt af van geheugenbehoefte, performance-eisen en de context waarin de stapel wordt toegepast.