Stack

This one's as straightforward as it gets. List i.e. an immutable linked list is precisely a stack

Algorithm

Operation	Complexity
Push	$O(1)$
Pop	$O(1)$

Implementation

object Stack {

  def push[A](as: List[A], a: A): List[A] =
    a :: as

  def pop[A](as: List[A]): (Option[A], List[A]) =
    as.headOption -> as.tail

}