1. Overview
In this quick article, we’ll introduce the java.util.Stack class and start looking at how we can make use of it.
A stack is a generic data structure that represents a LIFO (last in, first out) collection of objects allowing for pushing/popping elements in constant time.
For the new implementations, we should favor the Deque interface and its implementations. Deque defines a more complete and consistent set of LIFO operations. However, we may still need to deal with the Stack class, especially in legacy code, so it’s important to understand it well.
2. Create a Stack
Let’s start by creating an empty instance of Stack, by using the default, no-argument constructor:
@Test
public void whenStackIsCreated_thenItHasSizeZero() {
Stack<Integer> intStack = new Stack<>();
assertEquals(0, intStack.size());
}
This will create a Stack with the default capacity of 10. If the number of added elements exceeds the total Stack size, it will be doubled automatically. However, its size will never shrink after removing elements.
3. Synchronization for Stack
Stack is a direct subclass of Vector; this means that similarly to its superclass, it’s a synchronized implementation.
However, synchronization isn’t always needed, in such cases, it’s advised to use ArrayDeque.
4. Add into a Stack
Let’s start by adding an element to the top of the Stack, with the push() method – which also returns the element that was added:
@Test
public void whenElementIsPushed_thenStackSizeIsIncreased() {
Stack<Integer> intStack = new Stack<>();
intStack.push(1);
assertEquals(1, intStack.size());
}
Using push() method has the same effect as using *addElement(). T*he only difference is that addElement() returns the result of the operation, instead of the element that was added.
We can also add multiple elements at once:
@Test
public void whenMultipleElementsArePushed_thenStackSizeIsIncreased() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
boolean result = intStack.addAll(intList);
assertTrue(result);
assertEquals(7, intList.size());
}
5. Retrieve from a Stack
Next, let’s have a look at how to get and remove the last element in a Stack:
@Test
public void whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
Integer element = intStack.pop();
assertEquals(Integer.valueOf(5), element);
assertTrue(intStack.isEmpty());
}
We can also get the last element of the Stack without removing it:
@Test
public void whenElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
Integer element = intStack.peek();
assertEquals(Integer.valueOf(5), element);
assertEquals(1, intStack.search(5));
assertEquals(1, intStack.size());
}
6. Search for an Element in a Stack
6.1. Search
Stack allows us to search for an element and get its distance from the top:
@Test
public void whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(8);
assertEquals(2, intStack.search(5));
}
The result is an index of a given object. If more than one element is present, the index of the one closest to the top is returned. The item that is on the top of the stack is considered to be at position 1.
If the object is not found, search() will return -1.
6.2. Getting Index of Element
To get an index of an element on the Stack, we can also use the indexOf() and lastIndexOf() methods:
@Test
public void whenElementIsOnStack_thenIndexOfReturnsItsIndex() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
int indexOf = intStack.indexOf(5);
assertEquals(0, indexOf);
}
The lastIndexOf() will always find the index of the element that’s closest to the top of the stack. This works very similarly to search() – with the important difference that it returns the index, instead of the distance from the top:
@Test
public void whenMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(5);
intStack.push(5);
int lastIndexOf = intStack.lastIndexOf(5);
assertEquals(2, lastIndexOf);
}
7. Remove Elements from a Stack
Apart from the pop() operation, used both for removing and retrieving elements, we can also use multiple operations inherited from the Vector class to remove elements.
7.1. Removing Specified Elements
We can use the removeElement() method to remove the first occurrence of the given element:
@Test
public void whenRemoveElementIsInvoked_thenElementIsRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(5);
intStack.removeElement(5);
assertEquals(1, intStack.size());
}
We can also use the removeElementAt() to delete elements under a specified index in the Stack:
@Test
public void whenRemoveElementAtIsInvoked_thenElementIsRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(7);
intStack.removeElementAt(1);
assertEquals(-1, intStack.search(7));
}
7.2. Removing Multiple Elements
Let’s have a quick look at how to remove multiple elements from a Stack using the removeAll() API – which will take a Collection as an argument and remove all matching elements from the Stack:
@Test
public void givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
intStack.add(500);
intStack.removeAll(intList);
assertEquals(1, intStack.size());
assertEquals(1, intStack.search(500));
}
It’s also possible to remove all elements from the Stack using the clear() or removeAllElements() methods; both of those methods work the same:
@Test
public void whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(7);
intStack.removeAllElements();
assertTrue(intStack.isEmpty());
}
7.3. Removing Elements Using Filter
We can also use a condition for removing elements from the Stack. Let’s see how to do this using the removeIf(), with a filter expression as an argument:
@Test
public void whenRemoveIfIsInvoked_thenAllElementsSatysfyingConditionAreRemoved() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
intStack.removeIf(element -> element < 6);
assertEquals(2, intStack.size());
}
8. Iterate Over a Stack
Stack allows us to use both an Iterator and a ListIterator. The main difference is that the first one allows us to traverse Stack in one direction and second allows us to do this in both directions:
@Test
public void whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
ListIterator<Integer> it = intStack.listIterator();
Stack<Integer> result = new Stack<>();
while(it.hasNext()) {
result.push(it.next());
}
assertThat(result, equalTo(intStack));
}
All Iterators returned by Stack are fail-fast.
9. Stream API for the Java Stack
Stack is a collection, which means we can use it with Java 8 Streams API. Using Stream with the Stack is similar to using it with any other Collection:
@Test
public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() {
Stack<Integer> intStack = new Stack<>();
List<Integer> inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10);
intStack.addAll(inputIntList);
List<Integer> filtered = intStack
.stream()
.filter(element -> element <= 3)
.collect(Collectors.toList());
assertEquals(3, filtered.size());
}
10. Summary
This tutorial is a quick and practical guide to understand this core class in Java – the Stack.
Of course, you can explore the full API in the Javadoc.
And, as always, all code samples can be found over on GitHub.