Cum se poate construi o structură de date stivă folosind o listă legată?

Stiva poate fi implementată pe baza unei liste înlănțuite, unde fiecare element (nod) conține date și o referință la elementul următor. Elementul superior al stivei este capul listei. Operațiile principale sunt:

• push — adăugarea unui nou nod la începutul listei;
• pop — eliminarea nodului de la începutul listei și returnarea valorii sale;
• peek — vizualizarea valorii capului fără a-l elimina.

Exemplu în 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
}

Această abordare asigură operații de stivă în O(1) timp și extindere dinamică fără a fi nevoie de alocarea unui array mare.