scala/ScalaBook/chapter-03/genStack3.scala

abstract class Stack[Q] {
  def push(x: Q):Stack[Q]
  def pop:Stack[Q]
  def top:Q
}

case object EmptyStack extends Stack[Any] {
  def push(x: Any) = new StackC[Any](x,this)
  def pop:Stack[Any] = 
    throw new NoSuchElementException("stack underflow")
  def top : Any = 
    throw new NoSuchElementException("top of empty stack") 
}

case class StackC[Q](e: Q, s: Stack[Q]) extends Stack[Q] {
  def this(e : Q) = this(e, EmptyStack.asInstanceOf[Stack[Q]])
  def push (x : Q) = new StackC[Q](x, this)
  def pop = s
  def top = e.asInstanceOf[Q] 
}

val q0 = new StackC[Int](5)
val q1 = StackC(3,StackC(4,q0))
println(q1)
val q2 = q1.pop
println(q2)
val q3 = q2.pop
println(q3)
val q4 = q3.push(9)
println(q4)
var x = 7 + q4.top
println("x = " + x)
val s1 = new StackC[String]("a")
val s2 = s1.push("b")
println(s2)