Hoe bouw je een stack datastructuur met behulp van een gekoppelde lijst?

De stack kan worden geïmplementeerd op basis van een gekoppelde lijst, waarbij elk element (knoop) gegevens bevat en een verwijzing naar het volgende element. Het bovenste element van de stack is de kop van de lijst. Belangrijkste operaties:

• push — voeg een nieuwe knoop toe aan het begin van de lijst;
• pop — verwijder de knoop aan het begin van de lijst en geef de waarde terug;
• peek — bekijk de waarde van de kop zonder te verwijderen.

Voorbeeld in Kotlin:

class Node<T>(val data: T, var next: Node<T>? = null)

class Stack<T> {
    private var head: Node<T>? = null

    fun push(value: T) {
        val newNode = Node(value, head)
        head = newNode
    }

    fun pop(): T? {
        val value = head?.data
        head = head?.next
        return value
    }

    fun peek(): T? = head?.data

    fun isEmpty() = head == null
}

Deze aanpak garandeert stack-operaties in O(1) tijd en dynamische uitbreiding zonder de noodzaak van het reserveren van een grote array.