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

This article provides a conceptual overview of key data structures, including exam questions and study points.

In a Nutshell

The core data structures—Array, Stack, Queue, Heap, Tree, and Graph—form the foundation of efficient algorithms. They differ in access patterns, memory usage, and runtime behavior, and are chosen strategically depending on whether you need sequence order, priority handling, hierarchies, or network representation.

Core Technical Overview

Arrays store elements in contiguous memory, offer O(1) index access, and underpin many higher-level structures. Stack operates on LIFO principles; push and pop are O(1) and work well for backtracking, call stacks, and parsing. Queue follows FIFO; enqueue and dequeue are O(1), making it ideal for breadth-first search or buffering. Heap refers here to a priority-based structure with the heap property; insert, extract-min, and extract-max are O(log n), while peek is O(1). Trees structure hierarchical data; in balanced variants, search, insertion, and deletion are O(log n). Graphs model nodes and edges, represented as either adjacency lists or adjacency matrices depending on sparsity.

Exam-Relevant Key Points

• Know the 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)
• Understand ordering: LIFO for Stack, FIFO for Queue, priority for Heap
• Traversals: BFS with Queue, DFS with Stack, either recursive or iterative
• Graph representation: adjacency list versus adjacency matrix, sparse versus dense graphs
• Practical use cases: scheduling with Priority Queue, undo stacks, message queues, router pathfinding
• Safety considerations: bounds checking on arrays, preventing empty pops/dequeues, validating priorities
• Cost–benefit analysis: choosing the right structure reduces both runtime and memory usage
• Documentation: record data structure choice, invariants, and 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-heap, max-heap
5. Tree nodes: parent, children, height, depth
6. Balancing: AVL, red-black, B-trees for memory pages
7. Graph nodes: edges, degree, weight, direction
8. Representation: adjacency list, adjacency matrix
9. Traversal: BFS, DFS, inorder, preorder, postorder
10. Invariants and testing: heap ordering, binary search tree ordering, acyclicity in 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 uses a Priority Queue to select the lowest-cost node at each step.

Strengths and Weaknesses

Array

• Very fast index access, memory-efficient

• Fixed size; expensive insertions in the middle

Stack

• Simple O(1) operations; ideal for backtracking

• Access only to the top element

Queue

• Stable order; decouples producers from consumers

• No direct random access

Heap

• Fast priority-based selection

• No efficient full iteration; only the root is efficiently accessible

Tree

• Ordered data with logarithmic operations

• Balancing adds implementation complexity

Graph

• Highly flexible; models networks

• Higher implementation and algorithmic complexity

Typical Exam Questions (with Brief Answers)

1. Adjacency list versus adjacency matrix? For sparse graphs with few edges, adjacency lists use O(n + m) space instead of O(n²) and allow faster neighbor iteration.

2. Ordering in Stack and Queue? Stack is LIFO (last in, first out); Queue is 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 sits at the root.

4. Complexity of insert/delete in a min-heap? O(log n) via sift-up and sift-down operations; peek is O(1).

5. Why O(log n) for balanced search trees? Height stays proportional to log n, keeping path lengths for search, insert, and delete logarithmic.

6. How does BFS work and when is it useful? Level by level via a Queue; it finds shortest paths in unweighted graphs and is useful for reachability analysis.

7. How do you represent a tree in memory? Linked nodes with references to children, or implicitly in an array for heaps, where children of index i are at 2i and 2i+1.

8. Priority Queue versus 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 errors, off-by-one mistakes, missing bounds checks, potential security vulnerabilities.

10. When is DFS a better traversal approach? For topological sorting, cycle detection, finding connected components, and when you need to explore deep paths deliberately.

Key References

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