What is Stack Data Structure
First of all, let's take a quick look at what a stack data structure is. It's a linear data structure that is based on Last-in-First-out (LIFO) principle. It's kind of anti-queue. Imagine a deck of cards or a stack of books in a box. The book that you put in the stack first is at the bottom, and the first we will take out of the box is the book that was at the top - that is, the one that got into the box last. Here is a gif picture to demonstrate this principle.
What is the Stack data structure for?
One of the most important uses of the stack is to organize subroutine calls. The call point on the stack stores the return address from the subroutine after it terminates (and possibly the parameters passed). With each nested (including recursive) call of subroutines, new return addresses are added to the stack. With each return operation from the subroutine (return), the return address is removed from the stack and control is transferred to it. This application is so important to programming that in most processors the return stack is implemented in hardware in the instruction set. However, in other cases, the stack has to be modeled on more general data structures.Java Stack Class of Collection Framework
In Java Stack Class is a class from the Collection framework that implements List interface and extends Vector class. It also implements interfaces Collection, Iterable, Cloneable, Serializable. As you’ve probably already guessed this class represents the LIFO stack of objects. Here is the call to the constructor of the Stack class, that is, the creation of an object of this class.
Stack<E> stack = new Stack<E>();
Where E is the type of Object.
Java Stack Methods
This class has only one default constructor and all the methods of the Vector class. Plus, Stack has its own 5 methods:boolean empty() the method checks if the stack is empty or not. Returns true if stack is empty, false if not.
Object peek() the method returns the element that is at the top of the stack.
Object pop() the method returns the element that is at the top of the stack and removes it.
Object push(Object element) the method adds the specified element to the top of the stack.
int search(Object element) the method searches the stack for the specified element. If the required element is found, its “distance” from the top (serial number) is returned. If the element is not found, -1 is returned.
Stack code example
Let’s create a program example that works such as the gif picture above. We’ll put three “balls”, orange, purple and green, on the stack. Let's check the stack for emptiness. Then, we will extract balls from the stack until the stack is empty.
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Here is the output of this program:
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.add("Orange Ball");
myStack.add("Violet Ball");
myStack.add("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
The result of the program work, of course, will be exactly the same.
What about your own Stack implementation?
You can create your own stack data structure in Java using arrays or linked list classes. In the first case, a continuous array of cells is allocated to store values in memory, which are used as needed. In the second, for each element of the stack, a block of memory is ordered, sufficient to store the value and references to the previous and next elements of the stack. The array-based implementation is simpler, more efficient, and more memory efficient, but it requires a prior knowledge of the stack size limit and can lead to hard-to-find bugs. The list-based implementation is more robust but less efficient. Let's make a simple array-based implementation of the stack. It will include functions.push — a method that will ensure the addition of an element (in the top position)
pop — a method that will provide the removal of an element (from the top position)
readTop — a method that will return the value of the element that is in position top
sEmpty — a method that will check the stack for emptiness
isFull — a method that will check if our array in which we store the stack is not full
import java.util.Arrays;
public class MyStack {
private int maxSize;
private String[] stackArray;
private int top;
public MyStack(int size) {
this.maxSize = size;
stackArray = new String[maxSize];
top = -1;
}
public String push (String element) {
return stackArray[++top] = element;
}
public String pop (String element) {
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(-1);
}
System.out.println("Removing " + readTop());
return stackArray[top--];
}
public String readTop() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public void printStack(){
System.out.println(Arrays.toString(stackArray));
}
}
Now let's implement an example with three balls based on our stack:
public class myStackTest {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
System.out.println("Is my stack empty? " + myStack.isEmpty());
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
myStack.printStack();
System.out.println("Is my stack empty? " + myStack.isEmpty());
while (!myStack.isEmpty()) {
myStack.pop(myStack.readTop());
System.out.println("Is my stack empty? " + myStack.isEmpty());
}
}
}
The output is here:
Using Java's Stream API with Stack
The introduction of the Stream API in Java 8 brought functional programming features to Java, enabling developers to perform operations like filtering, mapping, and reducing on collections. While the Stack
class is primarily designed for stack-specific operations, it can integrate seamlessly with the Stream API.
Example: Filtering Elements in a Stack
import java.util.Stack;
import java.util.stream.Collectors;
public class StackStreamExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(15);
stack.push(20);
stack.push(25);
// Use Stream API to filter elements greater than 15
Stack<Integer> filteredStack = stack.stream()
.filter(element -> element > 15)
.collect(Collectors.toCollection(Stack::new));
System.out.println("Filtered Stack: " + filteredStack);
}
}
This example demonstrates how to create a new Stack
containing only elements that satisfy a specific condition using the Stream API.
Example: Transforming Elements in a Stack
Stack<Integer> transformedStack = stack.stream()
.map(element -> element * 2) // Multiply each element by 2
.collect(Collectors.toCollection(Stack::new));
System.out.println("Transformed Stack: " + transformedStack);
Synchronization and Thread Safety of the Java Stack Class
The Stack
class in Java is synchronized because it extends Vector
, which is inherently thread-safe. This synchronization ensures that operations on a Stack
object are safe for use in multi-threaded applications. However, this comes at a cost of reduced performance in single-threaded contexts due to synchronization overhead.
Example: Thread Safety of Stack
import java.util.Stack;
public class StackThreadSafetyExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
Runnable task = () -> {
for (int i = 0; i < 5; i++) {
stack.push(i);
}
};
Thread thread1 = new Thread(task);
Thread thread2 = new Thread(task);
thread1.start();
thread2.start();
try {
thread1.join();
thread2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Stack contents: " + stack);
}
}
In this example, multiple threads safely push elements to the same Stack
due to its synchronized methods.
Implications of Using a Synchronized Class in Multi-Threaded Applications
While synchronization ensures thread safety, it also introduces performance trade-offs. In multi-threaded environments, contention for the synchronized methods can lead to delays, especially when many threads access the Stack
simultaneously.
When to Use:
- When thread safety is a priority.
- When the
Stack
size and access frequency are manageable.
When to Avoid:
- In highly concurrent scenarios where alternative data structures like
ConcurrentLinkedDeque
may perform better. - In single-threaded applications where synchronization overhead is unnecessary.
Alternatives to Stack When Thread Safety is Not Required
For scenarios where thread safety is not a concern, more efficient alternatives to Stack
include:
ArrayDeque
ArrayDeque
is a highly efficient alternative to Stack
for non-thread-safe environments.
import java.util.ArrayDeque;
public class ArrayDequeExample {
public static void main(String[] args) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.push(10);
deque.push(20);
deque.push(30);
System.out.println("Deque contents: " + deque);
}
}
LinkedList
LinkedList
implements Deque
and provides similar functionality with additional features like efficient insertions and deletions.
GO TO FULL VERSION