/*
 * LinkedStack.kt
 * 
 * Based on Dave Musicant's LinkedStack.kt from Fall 2024.
 * Modified by Tanya Amert for Spring 2025.
 * 
 * Illustrates an implementation of the Stack ADT using
 * a linked list.
 */

/*
 * Stack interface: implements a stack
 */
interface Stack<T> {
    fun push(item: T)
    fun pop(): T
    fun peek(): T
    fun isEmpty(): Boolean
}

class LinkedStack<T> : Stack<T> {

    // This "private" "data class" is visible only within the SinglyLinkedList
    // class, and contains only data with no additional functions (besides a
    // few that Kotlin provides, like for printing it)
    private data class Node<T>(
        var item: T,
        var next: Node<T>?)

    // We'll maintain just a reference to the head of the linked list
    // (which may be null, in the case the list is empty)
    private var head: Node<T>? = null

    override fun isEmpty(): Boolean {
        return head == null
    }

    override fun push(item: T) {
        // The current head will be the next node after this new node
        val newNode = Node(item, head)

        // Put this new node at the head, inserting it
        head = newNode
    }

    override fun peek(): T {
        if (isEmpty()) {
            throw RuntimeException("The stack is empty!")
        }

        // Return the item stored at the head
        return head!!.item // not null because otherwise it's empty
    }

    override fun pop(): T {
        // Let peek() do the work
        val item: T = peek()

        // Clear out the old top (make its next the head)
        val current: Node<T>? = head // peek() failed if null
        head = current!!.next        // so current isn't null
        return item 
    }

    override fun toString(): String {        
        var s: String = ""
        s += "  top:"

        var current: Node<T>? = head
        while (current != null) {
            s += "\t${current.item.toString()}\n" // the element on a line of its own
            current = current.next
        }

        return s
    }
}

fun main() {
    val s = LinkedStack<Int>()
    s.push(2025)
    s.push(4)
    s.push(16)
    
    println("Elements present in stack: ")
    println(s)
    
    println("" + s.pop() + " popped from stack")
    println("Top element is: " + s.peek())

    println("Elements present in stack: ")
    println(s)
}