Choosing Stack Data structure in Java

May 04, 2020

Stack data structure

Stack is a LIFO data structure used to store a collection of objects. Individual items can be added and stored in a stack using a push operation. Objects can be retrieved using a pop operation, which removes an item from the top of the stack. Since it is LIFO(Last in First Out) Item added last is the first to come out of the stack. Java comes with multiple options when choosing a Stack. The first one is the old java.util.Stack and the second one is interface Deque and its implementations like ArrayDeque, Linkedlist etc.
Common operations on stack data structure are as follows,
  • push : Add data to top of the stack.
  • peek : Look what is on the top of the stack without removing it.
  • pop: Remove the object at the top of this stack.
  • size.: Size of the stack, which is number of items on the stack.

Different options for Stack

Java provides mainly 
java.util.Stack and java.util. Deque Implementation classes (ArrayDeque, Linkedlist) as stack data structures . Choosing the implementation of choice depends on the use case we are dealing with. Following sections shows using java.util.Stack and java.util.ArrayDeque as Stack data structure.

java.util.Stack as stack data structure

java.util.Stack class extends java.util.Vector and represents a LIFO data structure. It is one of the oldest class that ships with Java 1 onwards. 
Following example show how to initialize a Stack() object, some common operations on stack, like push items to the stack, check size of the stack, peek the top of the stack and iterate over the stack etc.
Stack stack = new Stack();

//push items to stack
stack.push("Transformers (2007)");
stack.push("Transformers: Revenge of the Fallen (2009)");
stack.push("Transformers: Dark of the Moon (2011)");
stack.push("Transformers: Age of Extinction (2014)"); 
stack.push("Transformers: The Last Knight (2017)"); 
stack.push("Bumblebee (2018)"); 

//Size of the stack
System.out.println("Size of the stack = " + stack.size());

//Peek the top of the stack
System.out.println("Peek top of the stack = " + stack.peek());
//Pop the top of the stack
System.out.println("Peek top of the stack = " + stack.pop()); 

//Print entries of the Stack
System.out.println("Entries in the Stack");
stack.forEach(a-> System.out.println(a));

//Print entries of the Stack Using Iterator
System.out.println("Entries in the Stack Using Iterator");
Iterator it = stack.iterator();
while(it.hasNext()) {
  String item = it.next();
  System.out.println(item);
}
java.util.Deque as Stack data structure
java.util.Deque is also known as double ended queue is an interface that extends java.util.Queue.
The Deque interface adds some interesting methods like pop() addFirst(), addLast() etc, which allows us to add and remove the data from both end of the queue,  deque implementations can be used both as a Stack (LIFO) or Queue (FIFO) data structure. 

Following diagram shows the Object hierarchy for Deque.


Java provides two implementation of java.util.Deque, ArrayDeque and LinkedList.
Following example shows how to use Deque as Stack. Here we are using ArrayDeque as an Deque instance. And we are doing exactly the same things that we did with Stack in the above example.
Deque stack2 = new ArrayDeque();

//push items to stack
stack2.push("Transformers (2007)");
stack2.push("Transformers: Revenge of the Fallen (2009)");
stack2.push("Transformers: Dark of the Moon (2011)");
stack2.push("Transformers: Age of Extinction (2014)"); 
stack2.push("Transformers: The Last Knight (2017)"); 
stack2.addFirst("Bumblebee (2018)");  // same as push()

//Size of the stack
System.out.println("Size of the stack = " + stack2.size());

//Peek the top of the stack
//Prints Bumblebee (2018)
System.out.println("Peek top of the stack = " + stack2.peekFirst()); 

//Pop the top of the stack
//Prints Bumblebee (2018)
System.out.println("Peek top of the stack = " + stack2.pop()); 

//Print entries of the Stack
System.out.println("Entries in the Stack");
stack2.forEach(a-> System.out.println(a));

//Print entries of the Stack Using Iterator
System.out.println("Entries in the Stack Using Iterator");
Iterator it2 = stack2.iterator();
while(it2.hasNext()) {
  String item = it2.next();
  System.out.println(item);
}
Summary
  • java.util.Stack is synchronized data structure.
  • java.util.Stack extends Vector internally.
  • Deque is an interface, and it has multiple implementations like ArrayDeque, LinkedList etc.
  • Deque is newer compared to java.util.Stack is more preferable as a Stack implementation.
  • Deque can be used both as a Stack or Queue data structure, depending on which methods we are using to add or remove item from the Deque. 

References

Java Stack Docs
Read More