Ի՞նչ գործընթացներ են տեղի ունենում, երբ կապակցված ցանկով իրականացված բարձի մեջ ավելացվում է նոր տարր։

Երբ նոր տարր եք ավելացնում stack-ին, որը իրականացվում է կապակցված ցանկի միջոցով, տեղի է ունենում հետևյալը:

1. Ստեղծվում է նոր հանգույց (ցանկի տարր), որը պարունակում է ավելացվող արժեքը:
2. Նոր հանգույցի ցուցիչը սահմանվում է ներկայիս վերևի տարրին (այսինքն՝ կապակցված ցանկի գլխին):
3. Կապակցված ցանկի գլուխը թարմացվում է և այժմ ցույց է տալիս նոր հանգույցը — այն դառնում է նոր վերևի տարր stack-ում:

Այսպիսով, push գործողությունը կատարվում է հաստատուն ժամանակում O(1), քանի որ ցանկը անցնելու կարիք չկա:

Kotlin օրինակ՝

class Node<T>(val value: T, var next: Node<T>? = null)

class Stack<T> {
    private var head: Node<T>? = null

    fun push(value: T) {
        val newNode = Node(value)
        newNode.next = head
        head = newNode
    }

    fun pop(): T? {
        val value = head?.value
        head = head?.next
        return value
    }
}