LinkedListStack impl

object Main extends App {
  case class Node(item: String, next: Option[Node])

  class FixedCapacityStack(capacity: Int = 0){
    val s = Array.fill[String](capacity){""}
    var n = 0
    def isEmpty: Boolean = n == 0
    def push(item: String): Unit = {
      s(n) = item
      n = n + 1
    }
    def pop(): String = {
      n = n - 1
      val item = s(n)
      s(n) = null
      item
    }
  }
  
  
  class ResizingArrayStack(capacity: Int = 0){
    var s: Array[String] = Array.fill[String](capacity){""}
    var n = 0
    def isEmpty: Boolean = n == 0
    def push(item: String): Unit = {
      if (n == s.length) resize(2 * s.length)
      s(n) = item
      n = n + 1
    }
    def pop(): String = {
      n = n - 1
      val item = s(n)
      s(n) = null
      if (n > 0 && n == s.length/4) resize(s.length/2)
      item
    }
    def resize(capacity: Int): Unit = {
      val copy = Array.fill[String](capacity){""}
      for (i <- 0 until n){
        copy(i) = s(i)
      }
      s = copy
    }
  }
  
  class LinkedListCustom {
    var first:Option[Node] = None

    def isEmpty(): Boolean = first.isEmpty

    def push(item: String)= {
      val formerFirst = first
      first = Some(Node(item, formerFirst))
    }

    def pop(): String = {
      val res = first.map(_.item)
      first = first.flatMap(_.next)
      res.getOrElse("")
    }
  }

  val l = new ResizingArrayStack(20)
  for (n <- 0 until 100) {
    l.push(n.toString)
  }

  for (n <- 0 until 100) {
    println(l.pop())
  }
}