The stack data structure is used in many important algorithms such as depth-first search and recursive methods.
A stack also uses the LIFO (Last-in Last-out) strategy which means that the last element in will be the last out. This data structure can be easily represented in a real-world stack of plates. Let’s see the following diagram to understand better the stack data structure:
Note that in the above diagram, the last plate placed on the top of the stack will be the first one to be removed. We would do the same with a real-world stack of plates. Removing the first plate of the stack would likely knock over the plates.
Inserting and Removing Elements from a Stack with Java
As mentioned above, a Stack follows the LIFO (Last-in-first-out) strategy. It’s the same as the real-world situation of stacking plates. We will use the most common methods of a stack.
The first is the push method which will insert elements into the stack in order. We can see clearly that when showing the elements from the stack without removing them.
Then, we will use the pop method that will return and remove the last element from the stack as we can see in the following code:
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4); // Last-in & First-out
System.out.println(stack);
showAndRemoveStackElements(stack);
}
private static void showAndRemoveStackElements(Stack<Integer> stack) {
int size = stack.size();
for (int i = 0; i < size; i++) {
System.out.print(stack.pop() + " ");
}
}
}
Output:
[1, 2, 3, 4]
4 3 2 1
Code analysis:
Notice in the code above that when inserting elements with the push method the elements are not being stacked up, the order is the same as they are being inserted. This is not the expected behavior for a Stack.
The expected behavior from the Stack data structure would be to print the elements from top to bottom as the following [4, 3, 2, 1].
Stack inherits Vector
Since Stack inherits a Vector, it’s a thread-safe way to use stack operations:
public class Stack<E> extends Vector<E> { ... }
It also has the possibility to retrieve elements by an index that is not in the contract of a Stack:
import java.util.Stack;
public class StackVector {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack);
System.out.println(stack.get(0)); // Gets the first element
System.out.println(stack.peek()); // Shows the last element
}
}
Output:
[1, 2]
1
2
Code analisis:
The first thing to notice is that the push method from the Stack actually doesn’t push the element to the first position. Instead, it will only add it to the Stack by the insertion order.
The other interesting point is that it’s possible to access an element by index from the Stack. This is behavior from an array and not necessarily from a Stack.
The peek method will retrieve the last element on the Stack.
As you could see, the Stack class has some faults when implementing the Stack data structure. It’s also not the recommended class to use Stack.
Instead of using the Stack class, it’s better to use the Deque interface for Stack operations. Let’s explore the use of Deque to use Stack operations in the next section…
Using Stack with Deque and ArrayDeque
The Java docs of the Stack class has the following comment:
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque stack = new ArrayDeque();
Therefore, it’s more effective to use Deque stack = new ArrayDeque(); for dealing with Stack operations in Java.
The Deque interface has operations of a Stack and Queue. It’s also the short name for a double-ended queue. It’s recommended to use Deque when there is no need for thread-safe operations.
With Deque, we can do the same as the Stack class and the elements are inserted from top to bottom which is what is expected from the Stack data structure:
import java.util.ArrayDeque;
import java.util.Deque;
public class StackDeque {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // Inserts element at the first position
stack.push(2);
System.out.println(stack); // LIFO insertion
System.out.println(stack.peek()); // Shows first element
System.out.println(stack.pop()); // Remove and return first element
}
}
Output:
[2, 1]
2
2
In the Deque interface, there are methods that do the same as push and pop.
The push method is equivalent to the addLast method and the removeLast method is equivalent to the pop method as we can see in the following code:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAlternativeMethods {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.addLast(1);
stack.addLast(2);
System.out.println(stack.getLast());
stack.removeLast();
System.out.println(stack);
}
}
Output:
2
[1]
Time Complexity from Stack
The time complexity of a Stack will depend on the used implementation. If we choose LinkedList we will work with a graph data structure. If we choose ArrayDeque then it’s an array data structure.
Let’s explore the differences in time complexity between LinkedList and ArrayDeque:
push (addFirst)
LinkedList: the push method will have the time complexity of O(1) no matter what. That’s because a LinkedList links objects (Nodes) from one to another. It’s not an array. The first element is always added into a separate variable which enables quick access.
ArrayDeque: the push method with ArrayDeque might be O(1) if it’s not necessary to resize the array. If the array is full and it is occasionally, the time complexity will be O(n) because it will be necessary to traverse the array, make a copy of the values and create a new resized array with the new element.
pop (removeLast)
LinkedList: the pop method will always have the time complexity of O(1). That’s because the elements are linked to each other and the first element will be stored in a variable to that we have direct access. Therefore, we only need to delete the object reference of this first element.
ArrayDeque: the pop method will for ArrayDeque be always O(1). That’s because the first element of the array will be set to null and the head index will be updated to not consider the element that was deleted.
Find an element
LinkedList: to find an element in a graph we need to traverse through all elements in the worst-case scenario until the wished element is found. Therefore, the time complexity is O(n).
ArrayDeque: to find an element by value, it’s also necessary to go through all elements in the worst-case scenario until the element is found. Similarly to LinkedList, the time complexity is O(n).
To learn more about Deque, take a look at the article in which we go through the operations from the queue and double-ended queue.
Summary
The stack data structure is used with recursion and in the famous depth-first search algorithm and it’s also useful for other operations!
Let’s see the key points of the stack data structure:
- It’s similar to the real-world situation of stacking up plates and removing them from the stack.
- It uses the LIFO (Last-in-first-out) strategy. This means that the last element that is added will be the first one to be out
- We can use the Stack class but as we’ve seen before it’s not the optimal choice.
- The Stack class is thread-safe. This means that it can be safely used in a multi-thread environment.
- The Stack class doesn’t insert the elements in the LIFO structure. The elements are added in the insertion order.
- The Stack class extends Vector, therefore, we can access elements by index.
- The Deque with the ArrayDeque implementation is preferable rather than using the Stack class.
- Deque is a double-ended-queue which means that we can use queue and stack operations.
- ArrayDeque uses an array behind the scenes.
- LinkedList uses the graph data structure, in other words, linked reference objects.
