Stack in Java

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the last element added to the stack is the first one to be removed.

Key Characteristics

1. LIFO Ordering: Elements are added and removed from the same end (called the “top”)
2. Restricted Access: You can only access the top element directly
3. Dynamic Size: Can grow and shrink during runtime

Stack Operations

The main operations performed on a stack are:

• Push: Add an element to the top of the stack
• Pop: Remove and return the top element
• Peek/Top: View the top element without removing it
• isEmpty: Check if the stack is empty
• Size: Get the number of elements in the stack

Stack Implementation in Java

Java provides multiple ways to implement a Stack:

1. Using java.util.Stack Class

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

// Push elements
stack.push(10);
stack.push(20);
stack.push(30);

// Pop element
int topElement = stack.pop(); // Returns 30

// Peek at top element
int peekElement = stack.peek(); // Returns 20 (doesn't remove)

// Check if empty
boolean isEmpty = stack.isEmpty();

// Get size
int size = stack.size();

2. Using ArrayDeque (Recommended)

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>();

// Push elements
stack.push(10);
stack.push(20);
stack.push(30);

// Pop element
int topElement = stack.pop();

// Peek at top element
int peekElement = stack.peek();

3. Using ArrayList

import java.util.ArrayList;

ArrayList<Integer> stack = new ArrayList<>();

// Push
stack.add(10);
stack.add(20);

// Pop
int lastIndex = stack.size() - 1;
int topElement = stack.remove(lastIndex);

// Peek
int peekElement = stack.get(stack.size() - 1);

Time and Space Complexity

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• Space: O(n) where n is the number of elements

Get Saumya14’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Best Practices

1. Always check if stack is empty before calling pop() or peek()
2. Handle stack overflow and underflow conditions
3. Use generics for type safety
4. Consider thread safety if using in multi-threaded environments

Common Applications

• Undo/Redo functionality in editors
• Backtracking algorithms (e.g., maze solving, parsing)
• Expression evaluation (postfix, prefix)
• Syntax parsing (compilers, interpreters)
• Browser history navigation

Performance

• ArrayDeque is generally faster than Stack for push/pop operations.
• Avoid using LinkedList as a stack; it’s less efficient.

Monotonic Stack

A monotonic stack is a special kind of stack data structure that always keeps its elements in a specific order — either always increasing or always decreasing. The word “monotonic” means “always going in one direction” (either up or down).

Types

• Monotonically Increasing Stack: Each new element is greater than or equal to the previous (from bottom to top).
• Monotonically Decreasing Stack: Each new element is less than or equal to the previous (from bottom to top).

Template

Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        // Do something with stack.pop()
        stack.pop();
    }
    stack.push(i);
}

How It Works

• As you iterate through an array, you use the stack to keep track of indices or values.
• When you encounter a new element, you compare it with the top of the stack:
• If the new element breaks the monotonic property, you pop elements from the stack until the property is restored.
• This process helps you efficiently find the next/previous greater/smaller elements.

Example: Next Greater Element (Java)

int[] nums = {2, 1, 2, 4, 3};
int[] res = new int[nums.length];
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int idx = stack.pop();
        res[idx] = nums[i];
    }
    stack.push(i);
}
while (!stack.isEmpty()) {
    res[stack.pop()] = -1; // No greater element
}

Why Use a Monotonic Stack?

• Efficiency: Each element is pushed and popped at most once, so the time complexity is O(n).
• Simplicity: It provides a clean and elegant way to solve problems that would otherwise require nested loops (O(n²)).