Kā uzbūvēt datu struktūru steku, izmantojot saistītu sarakstu?

Kārbai var būt realizēta, balstoties uz saistītu sarakstu, kur katrs elements (mezgls) satur datus un atsauci uz nākamo elementu. Augšējais kārbas elements ir saraksta galva. Galvenās operācijas:

• push — pievienot jaunu mezglu saraksta sākumā;
• pop — noņemt mezglu no saraksta sākuma un atgriezt tā vērtību;
• peek — apskatīt galvas vērtību bez noņemšanas.

Kotlin piemērs:

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
}

Šī pieeja nodrošina steka operācijas O(1) laikā un ļauj dinamiski paplašināties, bez nepieciešamības piešķirt lielu masīvu.