How to use a Stack in Scala (Stack class examples)

This is an excerpt from the Scala Cookbook (partially modified for the internet). This is Recipe 11.30, “How to Use a Stack in Scala”

Problem

You want to use a stack data structure in a Scala application.

Solution

A stack is a last-in, first-out (LIFO) data structure. In most programming languages you add elements to a stack using a push method, and take elements off the stack with pop, and Scala is no different.

Scala has both immutable and mutable versions of a stack, as well as an ArrayStack (discussed shortly). The following examples demonstrate how to use the mutable Scala Stack class.

Create an empty, mutable stack of any data type:

import scala.collection.mutable.Stack

var ints = Stack[Int]()
var fruits = Stack[String]()
case class Person(var name: String)
var people = Stack[Person]()

You can also populate a stack with initial elements when you create it:

val ints = Stack(1, 2, 3)

Once you have a mutable stack, push elements onto the stack with push:

// create a stack
scala> var fruits = Stack[String]()
fruits: scala.collection.mutable.Stack[String] = Stack()

// add one element at a time
scala> fruits.push("apple")
res0: scala.collection.mutable.Stack[String] = Stack(apple)

scala> fruits.push("banana")
res1: scala.collection.mutable.Stack[String] = Stack(banana, apple)

// add multiple elements
scala> fruits.push("coconut", "orange", "pineapple")
res2: scala.collection.mutable.Stack[String] = Stack(pineapple, orange, coconut, banana, apple)

To take elements off the stack, pop them off the top of the stack with pop:

scala> val next = fruits.pop
next: String = pineapple

scala> fruits
res3: scala.collection.mutable.Stack[String] = Stack(orange, coconut, banana, apple)

You can peek at the next element on the stack without removing it, using top:

scala> fruits.top
res4: String = orange
// 'orange' is still on the top

scala> fruits
res5: scala.collection.mutable.Stack[String] = Stack(orange, coconut, banana, apple)

Stack extends from Seq, so you can inspect it with the usual methods:

scala> fruits.size
res6: Int = 4

scala> fruits.isEmpty
res7: Boolean = false

You can empty a mutable stack with clear:

scala> fruits.clear

scala> fruits
res8: scala.collection.mutable.Stack[String] = Stack()

Discussion

There’s also an ArrayStack class, and according to the Scala documentation, “It provides fast indexing and is generally slightly more efficient for most operations than a normal mutable stack.”

Although I haven’t used an immutable Stack, I’ve seen several people recommend using a List instead of an immutable Stack for this use case. A List has at least one less layer of code, and you can push elements onto the List with :: and access the first element with the head method.

See Also

• The mutable Stack class
• The immutable Stack class
• The ArrayStack class