Data Structures Queue, Stack, Heap, Array, Tree, Graph – BFS, DFS, Complexity

This article is a concept explanation of important data structures – including exam questions and tags.

In a Nutshell

The core data structures Array, Stack, Queue, Heap, Tree and Graph form the foundation of efficient algorithms. They differ in access, memory and runtime behavior and are deployed strategically depending on the problem, order, priorities, hierarchies, networks.

Compact Technical Description

Arrays store elements in contiguous memory, offer O(1) access per index and are the basis for many higher-level structures. Stack works according to LIFO, push and pop are O(1) and are suitable for backtracking, call stacks, parsers. Queue follows FIFO, enqueue and dequeue are O(1), useful for BFS or buffers. Heap here refers to the priority-based Priority Queue with heap property, insert, extract min, max are O(log n), peek O(1). Trees structure hierarchical data; in balanced variants, search, insert and delete are O(log n). Graphs model nodes and edges; representation via adjacency list or adjacency matrix depending on density.

Exam-Relevant Key Points

• Know complexities, Array index access O(1), Stack push pop O(1), Queue enqueue dequeue O(1), Heap insert extract O(log n), balanced search tree operations O(log n)
• Orderings, LIFO in Stack, FIFO in Queue, priority in Heap
• Traversals, BFS with Queue, DFS with Stack, recursive or iterative
• IHK relevant, representation of graphs, adjacency list vs adjacency matrix, dense vs sparse graphs
• Practical relevance, scheduling with Priority Queue, undo stack, messaging queue, router path search
• Security aspect, bounds checks for arrays, prevent empty pop dequeue, priority validation
• Cost-effectiveness, correct structure reduces runtime and memory
• Documentation requirement, data structure choice, invariants, complexity contracts

Core Components

1. Array, capacity, index access, contiguity
2. Stack, push, pop, top, LIFO invariant
3. Queue, enqueue, dequeue, front, rear, FIFO invariant
4. Priority Queue, heap property, min, max heap
5. Tree node, parent, child, height, depth
6. Balancing, AVL, Red-Black, B-Tree for memory pages
7. Graph node, edge, degree, weight, direction
8. Representation, adjacency list, adjacency matrix
9. Traversal, BFS, DFS, inorder, preorder, postorder
10. Invariants and tests, heap order, search tree order, acyclicity for trees

Practical Example

// 1. BFS over a graph with adjacency list, uses Queue
Queue<Node> q = new LinkedList<>()
Set<Node> seen = new HashSet<>()
q.add(start), seen.add(start)
while (!q.isEmpty()) {
Node u = q.remove()
visit(u)
for (Node v : adj[u]) {
if (!seen.contains(v)) { seen.add(v), q.add(v) }
}
}

// 2. Min heap usage for Dijkstra node selection
PriorityQueue<State> pq = new PriorityQueue<>(byDistance)
pq.add(source)
while (!pq.isEmpty()) {
State s = pq.remove()
if (s.dist > best[s.node]) continue
relaxEdgesAndPushBetterStates(s, pq)
}

Explanation: BFS uses a Queue for level-wise traversal, Dijkstra selects the cheapest node with Priority Queue.

Advantages and Disadvantages

Array

• Very fast index access, compact

• Fixed size, expensive insertions in the middle

Stack

• Simple O(1) operations, ideal for backtracking

• Access only to the top

Queue

• Stable ordering, decouples producers and consumers

• No direct access

Heap

• Fast priority selection

• No ordered full iteration, only top is efficient

Tree

• Ordered data with logarithmic operations

• Balancing complexity

Graph

• Very flexible, models networks

• Higher implementation and algorithm complexity

Typical Exam Questions (with Short Answer)

1. Adjacency list vs. adjacency matrix? For sparse graphs with few edges, memory O(n + m) instead of O(n²) and faster iteration over neighbors.

2. Ordering of Stack and Queue? Stack LIFO (last in, first out), Queue FIFO (first in, first out).

3. Heap property? In a min heap, each node is less than or equal to its children, the smallest priority is at the root.

4. Complexity of insert/delete in min heap? O(log n) through sift up and sift down, peek is O(1).

5. Balanced search trees O(log n)? The height remains proportional to log n, making path lengths for search, insert, delete logarithmic.

6. How BFS works and what is it for? Level by level over Queue, provides shortest paths in unweighted graphs and is suitable for reachability analysis.

7. Represent tree in memory? Linked nodes with references to children, or implicitly in an array for heaps, indexing via 2i, 2i+1.

8. Priority Queue vs. sorted list? insert and extract are O(log n) instead of O(n), peek remains O(1).

9. Risks with array access? Out of bounds, off by one errors, missing bounds checks, potential security vulnerability.

10. DFS better traversal approach? For topological sorting, cycle detection, component finding, and when deep paths should be explored deliberately.

Most Important Sources

1. https://en.wikipedia.org/wiki/Data_structure
2. https://en.cppreference.com/w/cpp/container
3. https://docs.oracle.com/javase/tutorial/collections/