Стэк можно реализовать на основе связанного списка, где каждый элемент (узел) содержит данные и ссылку на следующий элемент. Верхний элемент стэка — это голова списка. Основные операции:

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) по времени и динамическое расширение без необходимости выделения большого массива.

Каким образом можно построить структуру данных стэк, использую связанный список?