What a stack is
A stack is a collection with one open end. You add elements to that end, and you remove elements from that same end, so the element you added last is the first one to come out. This rule is called last in, first out, or LIFO. A pile of plates works the same way: you put a plate on top and you take a plate from the top.
A stack supports a handful of operations, and each one takes constant time:
- push adds an element on top;
- pop removes the top element and returns it;
- top (sometimes called peek) returns the top element without removing it;
- isEmpty tells you whether anything is left.
A stack hands elements back in the reverse of the order they went in. That reversal is what makes it the right tool for problems where the latest unfinished item is the next one to deal with, such as matching brackets or finding the next larger number to the right. The lessons that follow in this chapter use it for both.
The mutable Stack in Scala
Scala's standard library has the class scala.collection.mutable.Stack. You create an empty one for a given element type, then push and pop:
import scala.collection.mutable
val stack = mutable.Stack[Int]()
stack.push(1)
stack.push(2)
stack.push(3)
println(stack) // Stack(3, 2, 1)
println(stack.top) // 3
println(stack.pop()) // 3
println(stack) // Stack(2, 1)
println(stack.size) // 2
The printed form lists the top of the stack first, so the last element pushed appears on the left. Some details are worth remembering:
valdoesn't make the stack constant. Thevalonly means the name always refers to the same stack object. The contents change with everypushandpop().pop()removes and returns.toponly returns. Both are written differently:pop()with parentheses andtopwithout.- Checking for emptiness.
isEmptyandnonEmptytake no parentheses, andsizegives the number of elements.headOptionreturnsSome(top)orNone, which avoids an exception when the stack might be empty. - Several pushes at once.
stack.push("a", "b")pushes"a"and then"b", so"b"ends up on top.pushAlltakes a whole collection and pushes its elements one after another in the same way. - All operations are amortized constant time. The stack is stored in a growable array, so an occasional push has to resize it, but the average cost is constant.
Creating a stack with initial elements
Calling mutable.Stack(1, 2, 3) builds a stack from those elements, and the first argument is on top:
val s = mutable.Stack(1, 2, 3)
println(s.top) // 1
println(s) // Stack(1, 2, 3)
That is the opposite of pushing 1, then 2, then 3, which puts 3 on top. When the order matters, create an empty stack and push in the order you want.
Popping an empty stack
Calling pop() or top on an empty stack throws a NoSuchElementException. Always guard these calls:
val empty = mutable.Stack[Char]()
println(empty.headOption) // None
// empty.pop() // throws NoSuchElementException
if (empty.nonEmpty) println(empty.top)
In stack problems this guard is usually the main edge case: a closing bracket that arrives when nothing is open, or a loop that must stop when the stack runs out.
A first example: reversing a string
Because a stack gives elements back in reverse order, pushing every character of a word and then popping them all reverses the word:
val word = "stack"
val chars = mutable.Stack[Char]()
for (c <- word) chars.push(c)
val reversed = new StringBuilder
while (chars.nonEmpty) {
reversed.append(chars.pop())
}
println(reversed.toString) // kcats
The first loop visits each character of the string. The second keeps popping until the stack is empty, and every pop() returns the most recently pushed character that is still there.
A List as an immutable stack
You can also use a List as a stack. It is immutable, so each operation gives you a new list instead of changing the old one. Adding to the front is a push, and head and tail give the top and the rest:
var l = List(1, 2)
l = 3 :: l // push 3
println(l) // List(3, 1, 2)
println(l.head) // 3, the top
l = l.tail // pop
println(l) // List(1, 2)
Here the variable is a var because the name must be pointed at each new list. The pattern is common in functional Scala code. Calling head on an empty list also throws NoSuchElementException. The lessons in this chapter use mutable.Stack, which is more direct for loops that push and pop repeatedly.
Where stacks show up in this chapter
- Valid Parentheses. Push each opening bracket. When a closing bracket arrives, pop the most recent opening bracket and check that the two match. Any bracket left on the stack at the end was never closed.
- Next Greater Element. Keep the indices of elements still waiting for a larger value to their right. A new element resolves the waiting indices it beats, from the top down.
Key takeaways
- A stack is last in, first out: the newest element leaves first.
- In Scala, use
scala.collection.mutable.Stackwithpush,pop(),top,isEmptyandnonEmpty. - Pushing 1, 2, 3 puts 3 on top, while
mutable.Stack(1, 2, 3)puts 1 on top. - Check
nonEmptybeforepop()ortop, or an exception is thrown. - All stack operations cost constant time, so a loop that pushes and pops each element once runs in
O(n).
