Как да изградим структура от данни стек, използвайки свързан списък?

Стекът може да бъде реализиран въз основа на свързан списък, където всеки елемент (възел) съдържа данни и препратка към следващия елемент. Горният елемент на стека е главата на списъка. Основните операции:

• push — добавяне на нов възел в началото на списъка;
• pop — премахване на възел от началото на списъка и връщане на неговата стойност;
• peek — преглед на стойността на главата без да се премахва.

Пример на 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
}

Този подход осигурява операции на стек с време O(1) и динамично разширяване без необходимост от заделяне на голям масив.