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

This article is a glossary entry covering essential data structures, including exam questions and reference tags.

In a Nutshell

Core data structures—Array, Stack, Queue, Heap, Tree, and Graph—form the foundation of efficient algorithms. Each excels at different tasks: managing order, controlling access, prioritizing elements, representing hierarchies, or modeling networks. Choosing the right structure for the problem at hand determines both runtime and memory efficiency.

Concise Technical Overview

Arrays store elements in contiguous memory, offering O(1) index access and serving as the basis for many higher-level structures. Stack follows LIFO semantics; push and pop are O(1), making it ideal for backtracking, call stacks, and parsing. Queue adheres to FIFO; enqueue and dequeue are O(1), useful for BFS and buffering. Heap here refers to a priority-based Priority Queue with heap ordering; insert and extract (min or max) are O(log n), while peek is O(1). Trees organize hierarchical data; in balanced variants, search, insertion, and deletion are O(log n). Graphs model nodes and edges, represented via adjacency list or adjacency matrix depending on density.

Exam-Relevant Highlights

• 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)
• Understand ordering: LIFO for Stack, FIFO for Queue, priority for Heap
• Master traversals: BFS with Queue, DFS with Stack, both recursive and iterative variants
• Recognize practical use cases: scheduling with Priority Queue, undo functionality with Stack, message passing with Queue, pathfinding in graphs
• Graph representation: adjacency list versus adjacency matrix, sparse versus dense graphs
• Security considerations: bounds checking on Arrays, guarding against empty pop/dequeue operations, validating priorities
• Economic efficiency: selecting the right structure reduces runtime and memory overhead
• 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 node: parent, child, height, depth
6. Balancing: AVL, red-black, B-tree for paged memory
7. Graph node: edge, degree, weight, direction
8. Representation: adjacency list, adjacency matrix
9. Traversal: BFS, DFS, inorder, preorder, postorder
10. Invariants and testing: heap ordering, search tree ordering, acyclicity for trees

Practical Example

// 1. BFS over a graph using adjacency list, leverages 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-by-level traversal; Dijkstra uses a Priority Queue to always select the lowest-cost node.

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

• Preserves order, decouples producers and consumers

• No direct random access

Heap

• Fast priority retrieval

• No efficient full iteration, only peak operations are efficient

Tree

• Ordered data with logarithmic operations

• Balancing adds complexity

Graph

• Highly flexible, models networks elegantly

• Higher implementation and algorithmic complexity

Common 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. Stack and Queue order? Stack is LIFO (last in, first out); Queue is FIFO (first in, first out).

3. Heap property? In a min-heap, every node is smaller than or equal to its children, placing the smallest priority 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 are balanced search trees O(log n)? Height remains proportional to log n, keeping path lengths logarithmic for search, insert, and delete.

6. How does BFS work and when use it? Processes nodes level by level using a Queue; yields shortest paths in unweighted graphs and identifies reachability.

7. How do you represent a tree in memory? Linked nodes with references to children, or implicitly in an array for heaps, using index arithmetic (2i, 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, and potential security vulnerabilities.

10. When is DFS the better traversal approach? For topological sorting, cycle detection, finding connected components, and deliberately exploring deep paths.

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/