in plaats van array te gebruiken, kunnen we ook linked list gebruiken om stack te implementeren. Linked list wijst het geheugen dynamisch toe. Echter, tijd complexiteit in beide scenario is hetzelfde voor alle operaties dwz push, pop en peek.
In de gelinkte lijst implementatie van stack, worden de nodes niet-contiguously onderhouden in het geheugen. Elke node bevat een pointer naar zijn directe opvolger node in de stack. Stack wordt gezegd te zijn overflown als de ruimte links in het geheugen heap is niet genoeg om een knooppunt te maken.
het bovenste knooppunt in de stack bevat altijd null in het adresveld. Laten we bespreken de manier waarop, elke operatie wordt uitgevoerd in linked list implementatie van stack.
een node toevoegen aan de stack (Push-operatie)
een node toevoegen aan de stack wordt aangeduid als push-operatie. Het pushen van een element naar een stack in linked list implementatie is anders dan die van een array implementatie. Om een element op de stapel te duwen, zijn de volgende stappen betrokken.
- maak eerst een knooppunt aan en wijs er geheugen aan toe.
- als de lijst leeg is, moet het item worden gepusht als het startknooppunt van de lijst. Dit omvat het toewijzen van waarde aan het gegevensgedeelte van het knooppunt en het toewijzen van null aan het adresgedeelte van het knooppunt.
- als er al enkele knopen in de lijst staan, dan moeten we het nieuwe element aan het begin van de lijst toevoegen (om de eigenschap van de stack niet te schenden). Wijs hiervoor het adres van het startelement toe aan het adresveld van het nieuwe knooppunt en maak het nieuwe knooppunt, het startknooppunt van de lijst.
- Controleer op de underflow voorwaarde: de underflow voorwaarde treedt op wanneer we proberen te pop van een reeds lege stack. De stack zal leeg zijn als de head pointer van de lijst naar null wijst.
- Pas de head pointer dienovereenkomstig aan: in stack worden de elementen slechts aan één kant uitgevouwen, daarom moet de waarde die in de head pointer is opgeslagen worden verwijderd en moet de node worden vrijgemaakt. Het volgende knooppunt van de head node wordt nu de head node.
- kopieer de head pointer naar een tijdelijke pointer.
- Verplaats de tijdelijke aanwijzer door alle knooppunten van de lijst en druk het waardeveld af dat aan elk knooppunt is gekoppeld.
tijdscomplexiteit: o(1)
C implementatie:
een knooppunt uit de stack verwijderen (POP-operatie)
een knooppunt verwijderen van de bovenkant van de stack wordt pop-operatie genoemd. Het verwijderen van een knooppunt uit de implementatie van de gekoppelde lijst van stack is anders dan in de implementatie van de matrix. Om een element uit de stack te popen, moeten we de volgende stappen volgen :
Tijdscomplexiteit : o(n)
C implementatie
Toon de knooppunten (doorkruisen)
Toon alle knooppunten van een stack moet doorlopen alle knooppunten van de gekoppelde lijst georganiseerd in de vorm van stack. Hiervoor moeten we de volgende stappen volgen.
Tijdscomplexiteit : o(n)