Jak zbudować strukturę danych stosu, używając listy powiązanej?

Stos można zaimplementować na podstawie listy powiązanej, gdzie każdy element (węzeł) zawiera dane i odwołanie do następnego elementu. Górny element stosu to głowa listy. Główne operacje:

• push — dodanie nowego węzła na początku listy;
• pop — usunięcie węzła z początku listy i zwrócenie jego wartości;
• peek — podglądanie wartości głowy bez usuwania.

Przykład w 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
}

Takie podejście zapewnia operacje stosu w czasie O(1) i dynamiczne rozszerzanie bez konieczności przydzielania dużej tablicy.