In this tutorial, you will get to know the abstract data type “stack”:
- How does a stack work?
- What are the applications of stacks?
- How to use the Java class “Stack”?
- How to implement your own stack in Java?
This article answers the first two questions; the linked follow-up parts answer the other two.
What Is a Stack?
A stack is a collection of elements in which the elements can be inserted into and removed from only one side (typically the top in graphical representations).
The best way to think of a stack is as a stack of plates:
We can only place new plates on top of the stack, and we can only remove them from the top.
Since this means that the last plate added is the first to be removed, we refer to this as the last-in-first-out (LIFO) principle.
LIFO Principle for Stack
The following image shows a stack containing five strings, with “cherry” on top. If you place “grape” on the stack (push), you also have to take “grape” out first (pop):
Stack Operations: Push, Pop, and Peek
A stack data structure typically provides the following operations:
- Push: places an element on top of the stack
- Pop: removes the top element
- Peek or Top: returns the top element without removing it
- A check whether the stack is empty
Applications for Stacks
For example, you can think of the web page history within a browser tab as a stack: Each time you click a link, the previous URL is placed on a stack. When you press the back button, the top URL of the stack is retrieved and displayed again.
Similarly, when a computer program runs, each method call places a stack frame with the return address and the local variables on the so-called “call stack”. Once the method has finished, its stack frame is removed, and the program jumps back to the call position. You may have encountered the StackOverflowError that excessively deep recursion triggers.
Inside the JVM, each stack frame even contains a second stack, the operand stack: A bytecode instruction like iadd takes two values from this stack and pushes their sum back onto it.
Compilers and parsers also use stacks, e.g., to check whether every opening bracket and every opening tag in a JSON or XML document is closed again, or to evaluate mathematical expressions.
Time Complexity of Stack Operations
You can find an introduction to the topic of time complexity in the article “Big O Notation and Time Complexity – Easily Explained”.
Usually, we implement a stack with an array or a linked list. With a linked list, the cost of inserting or removing an element is constant and does not depend on the number of elements present in the stack.
With an array, this holds for removing and – as long as the array has a fixed size – for inserting as well. If the array grows, inserting is amortized constant: When it is full, a push() costs O(n) once for copying the elements into a larger array; spread over all calls, the cost remains constant.
The time complexity is, therefore: O(1) – amortized when inserting into a growing array.
Stacks can also be implemented with queues – however, that’s more for practice: In this tutorial’s implementation, push() has to move all existing elements and costs O(n).
Stacks in Java
The class java.util.Stack has existed since Java 1.0. The next part shows you how to use it: Java Stack: Class, Methods, Alternatives, and Implementation.
However, I recommend using a Deque such as ArrayDeque instead of Stack – the documentation of the Stack class itself says so, too. You can read why in “Java Deque vs. Stack: Why Deque Is the Better Choice”.
If you enjoyed this article, I’d appreciate a review on my ProvenExpert profile.
