What a stack is
A stack is a collection where you add and remove items at one end only, called the top. The item added last is the first one to come out, a rule known as LIFO (last in, first out). A pile of plates works the same way: you put a plate on top and you take the top plate off.
A stack supports three basic operations:
- push: put an item on the top;
- pop: remove the item on the top and return it;
- peek: look at the top item without removing it.
Each one takes constant time, O(1). You can't reach an item in the middle without popping everything above it, and that restriction is the whole point: the stack remembers the order in which things happened and hands them back in reverse.
Where stacks help
- Matching pairs. Brackets must be closed in the reverse order they were opened. The most recent open bracket is the only one a closing bracket may close, and that is the top of a stack.
- Undoing. Each action goes on a stack, and undo pops the latest one.
- Nested work. Function calls behave like a stack: the function called last finishes first. Recursion uses exactly this idea.
- "Waiting" items. Problems like the next greater element keep items that still wait for an answer on a stack and settle them in reverse order of arrival.
Stacks in Kotlin
Kotlin's standard library has no class called Stack. The recommended tool is ArrayDeque, a double-ended queue that is available without an import. You use only one of its ends, the last one, as the top:
fun main() {
val stack = ArrayDeque<Int>()
stack.addLast(1) // push
stack.addLast(2)
stack.addLast(3)
println(stack.last()) // peek: 3
println(stack.removeLast()) // pop: 3
println(stack) // [1, 2]
println(stack.isEmpty()) // false
println(stack.size) // 2
}
The program prints:
3
3
[1, 2]
false
2
The names to remember:
| Operation | Call |
|---|---|
| push | addLast(x) |
| pop | removeLast() |
| peek | last() |
| is it empty? | isEmpty() or isNotEmpty() |
| how many items? | size |
Empty stacks
Popping or peeking at an empty ArrayDeque is an error: removeLast() and last() both throw a NoSuchElementException. Check isEmpty() first, or use the variants that return null instead:
fun main() {
val empty = ArrayDeque<Int>()
println(empty.lastOrNull()) // null
println(empty.removeLastOrNull()) // null
}
The output is two lines, each null. In a loop condition, put the emptiness check first and use &&, as in stack.isNotEmpty() && stack.last() < x. When the left side is false, Kotlin doesn't evaluate the right side, so last() never runs on an empty stack.
Other options
java.util.Stackexists on the JVM and haspush,popandpeek. It is an old class, synchronized and based onVector, so new Kotlin code prefersArrayDeque.- A
MutableListcan act as a stack too, withaddto push andremoveAt(list.size - 1)to pop.ArrayDequereads more clearly, because its method names say what they do.
A first example: reversing a word
Pushing characters and popping them reverses their order:
fun main() {
val letters = ArrayDeque<Char>()
for (c in "stack") {
letters.addLast(c)
}
val reversed = StringBuilder()
while (letters.isNotEmpty()) {
reversed.append(letters.removeLast())
}
println(reversed)
}
It prints kcats.
Common mistakes
- Mixing the ends. If you push with
addLastand pop withremoveFirst, you get a queue (first in, first out), not a stack. Always use the same end for both. - Popping an empty stack. This throws an exception. Guard every pop and peek with an emptiness check.
- Forgetting the final check. After you process all the input, items left on the stack often mean something: an unclosed bracket, or an element that never found its answer.
- Storing values when you need positions. When a problem asks for indices, push the index, not the value. You can always look the value up from the index.
Key takeaways
- A stack is last in, first out. All its operations work on the top and take O(1) time.
- In Kotlin, use
ArrayDequewithaddLast,removeLastandlast. - Check for emptiness before every pop or peek.
- Stacks suit anything with nesting or "most recent first" order: matching brackets, undo and items waiting for a later answer.