Collections for Data Structures: Stack, Queue, Graph, Tree in Java

Illustration for Collections for Data Structures: Stack, Queue, Graph, Tree in Java
By Last updated:

When implementing classic data structures like Stack, Queue, Graph, and Tree in Java, the Collections Framework offers powerful, reusable components that boost productivity and maintain performance.

This tutorial walks you through how to use Java Collections to build and manage these data structures effectively. Whether you're preparing for interviews, working on enterprise systems, or designing scalable applications—understanding these foundations is key.


Core Concepts

The Java Collections Framework provides standard interfaces (List, Deque, Map, etc.) that can model many classic data structures. With internal optimizations and support for concurrency and immutability, these implementations are production-ready.


Stack Using Java Collections

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2
  • Why Deque? ArrayDeque is faster and cleaner than the legacy Stack class.

Legacy Stack Class

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.pop();
  • ❌ Avoid in modern code unless working with legacy APIs.

Queue and PriorityQueue

Simple Queue with LinkedList

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.poll(); // Removes "A"

Priority Queue for Sorting

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(5);
System.out.println(pq.poll()); // 5 (min-heap)
  • Use Comparator.reverseOrder() for max-heap behavior.

Graph Implementation Using Maps

Adjacency List

Map<String, List<String>> graph = new HashMap<>();
graph.put("A", new ArrayList<>(List.of("B", "C")));
graph.put("B", new ArrayList<>(List.of("D")));
  • HashMap<String, List<String>> models directed or undirected edges.

Traversal Example – BFS

Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();

queue.add("A");
while (!queue.isEmpty()) {
    String node = queue.poll();
    if (visited.add(node)) {
        queue.addAll(graph.getOrDefault(node, List.of()));
    }
}

Tree Structures Using Collections

Binary Tree Node

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Tree Traversal Using Stack

Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

Performance and Complexity

Structure Add Remove Search Notes
Stack O(1) O(1) O(n) LIFO, use ArrayDeque
Queue O(1) O(1) O(n) FIFO, use LinkedList
PriorityQ O(log n) O(log n) O(n) Min/Max heap
Graph O(1)* O(1)* O(n) Adjacency list with HashMap
Tree O(log n) O(log n) O(log n) Use balanced trees (e.g., TreeMap)

Functional Programming in Data Structures

Filter Stack Elements

List<Integer> filtered = stack.stream()
    .filter(i -> i % 2 == 0)
    .collect(Collectors.toList());

Graph Flattening

Set<String> allNodes = graph.values().stream()
    .flatMap(List::stream)
    .collect(Collectors.toSet());

Real-World Applications

  • Stack: Syntax parsers, undo operations
  • Queue: Message brokers, thread pools
  • PriorityQueue: Task schedulers
  • Graph: Social networks, routing systems
  • Tree: Hierarchies (file systems, category trees)

Anti-patterns and Fixes

  • ❌ Using Stack over Deque
  • ❌ Forgetting null-checks in graph adjacency lists
  • ❌ Building trees with Map and losing structure

✅ Prefer Deque, use Map.getOrDefault(), encapsulate tree logic in classes.


📌 What's New in Java Versions?

  • Java 8
    • Lambdas, Streams, Collectors, Optional
  • Java 9
    • List.of(), Set.of(), Map.of()
  • Java 10
    • var type inference
  • Java 21
    • Collection performance boosts, memory optimizations

Conclusion and Key Takeaways

Java Collections Framework makes implementing data structures like stacks, queues, graphs, and trees straightforward, efficient, and maintainable. Leveraging Deque, PriorityQueue, and Map-based designs helps you write clean, scalable code backed by solid performance.


FAQ

1. Why is Deque better than Stack?

Deque is faster, modern, and more flexible.

2. Can I use ArrayList for a stack?

Yes, but prefer Deque for push/pop operations.

3. What’s the default order of PriorityQueue?

Min-heap (smallest element first).

4. Is Queue thread-safe?

Not by default. Use ConcurrentLinkedQueue for thread-safe use.

5. How to implement BFS in Java?

Use a Queue and a Set to track visited nodes.

6. Should I use TreeMap for trees?

Only for key-value trees. Use custom classes for binary trees.

7. Are these collections serializable?

Yes, but serialization behavior may vary.

8. Can I apply streams to graphs?

Yes, for processing node lists, flattening, or grouping.

9. Are there built-in tree data structures in Java?

Only TreeMap and TreeSet. Trees like binary or AVL must be custom-built.

10. Is recursion or iteration better for tree traversal?

Iteration using a stack is safer for deep trees (avoids StackOverflowError).