Cum funcționează stiva în contextul programării?

Stiva este un tip de dată abstractă care funcționează după principiul LIFO (Last-In, First-Out).

Operațiuni principale cu stiva:

• Push: Adăugarea unui element în vârful stivei.
• Pop: Eliminarea și returnarea elementului din vârful stivei.
• Peek (sau Top): Returnarea elementului din vârf fără a-l elimina.
• isEmpty: Verificarea dacă stiva este goală.
• size: Returnarea numărului de elemente din stivă.

Exemplu de implementare a unei stive în Kotlin folosind MutableList:

class Stack<T> {

    private val elements = mutableListOf<T>()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        return if (!isEmpty()) {
            elements.removeAt(elements.size - 1)
        } else {
            null // Sau aruncarea unei excepții
        }
    }

    fun peek(): T? {
        return if (!isEmpty()) {
            elements.last()
        } else {
            null
        }
    }

    fun isEmpty(): Boolean {
        return elements.isEmpty()
    }

    fun size(): Int {
        return elements.size
    }
}

Utilizarea stivelor în programare este frecventă în:

• Calculul expresiilor: Conversia notării infixe în postfix sau prefix, calculul expresiilor postfix.
• Gestionarea apelurilor de funcții/methods: Stiva de apeluri păstrează informații despre funcțiile active.
• Anulare/repetare acțiuni: Editoare de cod și editoare grafice folosesc stive pentru istoricul acțiunilor.
• Parcurgerea grafurilor și arborilor: Se folosește pentru implementarea algoritmului de căutare în adâncime (DFS).
• Analiza sintactică: Parserele folosesc stive pentru verificarea corectitudinii sintaxei.

Stiva este o structură de date fundamentală și are o importanță majoră pentru înțelegerea principiilor de funcționare ale multor algoritmi și mecanisme de nivel scăzut în sistemele de operare și mașinile virtuale.