Kaip sukurti duomenų struktūrą staką, naudojant susietą sąrašą?

Eilė gali būti įgyvendinta remiantis susietu sąrašu, kur kiekvienas elementas (mazgas) turi duomenis ir nuorodą į kitą elementą. Viršutinis eilės elementas yra sąrašo galva. Pagrindinės operacijos:

• push — pridėti naują mazgą į sąrašo pradžią;
• pop — pašalinti mazgą iš sąrašo pradžios ir grąžinti jo reikšmę;
• peek — peržiūrėti galvos reikšmę be pašalinimo.

Pavyzdys Kotlin kalba:

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
}

Šis požiūris užtikrina steko operacijas O(1) laiko ir leidžia dinamiškai plėstis, nereikalaujant didelio masyvo paskirstymo.