Data Structures Fundamentals: Stack, Queue, Heap, Array, Tree, Graph

Data structures are fundamental concepts in computer science that organize and manage data. The choice of the right data structure significantly influences the efficiency of algorithms.

What are Data Structures?

Data structures define how data is stored, organized, and accessed. They determine the complexity of operations like insertion, deletion, and searching.

Classification of Data Structures

1. Linear Structures: Array, Stack, Queue, Linked List
2. Hierarchical Structures: Tree, Heap
3. Network Structures: Graph
4. Hash-based Structures: Hash Table, Hash Set

Array (Field)

Fundamentals

Arrays are the simplest data structure with direct index access.

public class ArrayDemo {
    public static void main(String[] args) {
        // Static array
        int[] numbers = new int[5];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        // Dynamic array (ArrayList)
        List<Integer> dynamicArray = new ArrayList<>();
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        
        // Array operations
        System.out.println("Element at index 2: " + numbers[2]); // O(1)
        
        // Linear search
        int index = linearSearch(numbers, 30); // O(n)
        System.out.println("30 found at index: " + index);
        
        // Sort with Binary Search
        Arrays.sort(numbers); // O(n log n)
        int sortedIndex = Arrays.binarySearch(numbers, 30); // O(log n)
        System.out.println("30 (sorted) at index: " + sortedIndex);
    }
    
    // Linear search in array
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // Not found
    }
}

Dynamic Array Implementation

public class DynamicArray<T> {
    private Object[] array;
    private int size;
    private int capacity;
    
    public DynamicArray() {
        capacity = 10;
        array = new Object[capacity];
        size = 0;
    }
    
    public void add(T element) {
        if (size >= capacity) {
            resize();
        }
        array[size++] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (T) array[index];
    }
    
    private void resize() {
        capacity *= 2;
        Object[] newArray = new Object[capacity];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
    }
}

Array Complexity

Operation	Time Complexity	Space Complexity
Access by index	O(1)	-
Linear search	O(n)	-
Binary search (sorted)	O(log n)	-
Insertion at end	O(1)	-
Insertion at beginning	O(n)	-
Deletion	O(n)	-

Stack (LIFO - Last In, First Out)

Fundamentals

A stack is a linear data structure that follows the LIFO principle.

public class StackDemo {
    public static void main(String[] args) {
        // Using Java's built-in Stack
        Stack<Integer> stack = new Stack<>();
        
        // Push operations
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Top element: " + stack.peek()); // 30
        System.out.println("Stack size: " + stack.size()); // 3
        
        // Pop operations
        while (!stack.isEmpty()) {
            System.out.println("Popped: " + stack.pop());
        }
        
        // Custom stack implementation test
        CustomStack<String> customStack = new CustomStack<>();
        customStack.push("First");
        customStack.push("Second");
        customStack.push("Third");
        
        System.out.println("Custom stack:");
        while (!customStack.isEmpty()) {
            System.out.println("Popped: " + customStack.pop());
        }
    }
}

class CustomStack<T> {
    private Node<T> top;
    private int size;
    
    private static class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }
    
    public boolean isEmpty() {
        return top == null;
    }
    
    public int size() {
        return size;
    }
}

Stack Applications

1. Function call stack: Manages function calls and local variables
2. Expression evaluation: Evaluates mathematical expressions
3. Undo operations: Stores previous states
4. Backtracking algorithms: Depth-first search in graphs

Stack Complexity

Operation	Time Complexity	Space Complexity
Push	O(1)	-
Pop	O(1)	-
Peek	O(1)	-
Search	O(n)	-

Queue (FIFO - First In, First Out)

Fundamentals

A queue is a linear data structure that follows the FIFO principle.

public class QueueDemo {
    public static void main(String[] args) {
        // Using Java's built-in Queue
        Queue<Integer> queue = new LinkedList<>();
        
        // Enqueue operations
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        System.out.println("Front element: " + queue.peek()); // 10
        System.out.println("Queue size: " + queue.size()); // 3
        
        // Dequeue operations
        while (!queue.isEmpty()) {
            System.out.println("Dequeued: " + queue.poll());
        }
        
        // Custom queue implementation test
        CustomQueue<String> customQueue = new CustomQueue<>();
        customQueue.enqueue("First");
        customQueue.enqueue("Second");
        customQueue.enqueue("Third");
        
        System.out.println("Custom queue:");
        while (!customQueue.isEmpty()) {
            System.out.println("Dequeued: " + customQueue.dequeue());
        }
    }
}

class CustomQueue<T> {
    private Node<T> front;
    private Node<T> rear;
    private int size;
    
    private static class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int size() {
        return size;
    }
}

Queue Applications

1. Task scheduling: Manages tasks in operating systems
2. Print queue: Manages print jobs
3. Breadth-first search: Level-order traversal in trees
4. Buffer management: Manages data streams

Queue Complexity

Operation	Time Complexity	Space Complexity
Enqueue	O(1)	-
Dequeue	O(1)	-
Peek	O(1)	-
Search	O(n)	-

Heap

Fundamentals

A heap is a specialized tree-based data structure that satisfies the heap property.

public class HeapDemo {
    public static void main(String[] args) {
        // Max Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(10);
        maxHeap.offer(30);
        maxHeap.offer(20);
        maxHeap.offer(40);
        
        System.out.println("Max Heap:");
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // 40 30 20 10
        }
        
        // Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(10);
        minHeap.offer(30);
        minHeap.offer(20);
        minHeap.offer(40);
        
        System.out.println("\nMin Heap:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 10 20 30 40
        }
        
        // Custom heap implementation test
        MaxHeap customHeap = new MaxHeap();
        customHeap.insert(10);
        customHeap.insert(30);
        customHeap.insert(20);
        customHeap.insert(40);
        
        System.out.println("\nCustom Max Heap:");
        while (!customHeap.isEmpty()) {
            System.out.print(customHeap.extractMax() + " ");
        }
    }
}

class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;
    
    public MaxHeap() {
        capacity = 10;
        heap = new int[capacity];
        size = 0;
    }
    
    public void insert(int value) {
        if (size >= capacity) {
            resize();
        }
        heap[size] = value;
        heapifyUp(size);
        size++;
    }
    
    public int extractMax() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    }
    
    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }
    
    private void heapifyDown(int index) {
        int largest = index;
        int left = leftChild(index);
        int right = rightChild(index);
        
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }
    
    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    
    private void resize() {
        capacity *= 2;
        int[] newHeap = new int[capacity];
        System.arraycopy(heap, 0, newHeap, 0, size);
        heap = newHeap;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

Heap Applications

1. Priority queues: Manages tasks with priorities
2. Heap sort: Efficient sorting algorithm
3. Finding k-th largest element: Quick selection
4. Dijkstra’s algorithm: Shortest path in graphs

Heap Complexity

Operation	Time Complexity	Space Complexity
Insert	O(log n)	-
Extract Max/Min	O(log n)	-
Peek	O(1)	-
Search	O(n)	-

Tree

Binary Search Tree

public class BinarySearchTreeDemo {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        System.out.println("In-order traversal:");
        bst.inOrderTraversal(); // 20 30 40 50 60 70 80
        
        System.out.println("\nSearch for 40: " + bst.search(40)); // true
        System.out.println("Search for 90: " + bst.search(90)); // false
        
        bst.delete(30);
        System.out.println("\nAfter deleting 30:");
        bst.inOrderTraversal(); // 20 40 50 60 70 80
    }
}

class BST {
    class Node {
        int value;
        Node left, right;
        
        Node(int value) {
            this.value = value;
        }
    }
    
    private Node root;
    
    public void insert(int value) {
        root = insertRec(root, value);
    }
    
    private Node insertRec(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }
        
        if (value < node.value) {
            node.left = insertRec(node.left, value);
        } else if (value > node.value) {
            node.right = insertRec(node.right, value);
        }
        
        return node;
    }
    
    public boolean search(int value) {
        return searchRec(root, value);
    }
    
    private boolean searchRec(Node node, int value) {
        if (node == null) {
            return false;
        }
        
        if (value == node.value) {
            return true;
        }
        
        return value < node.value 
            ? searchRec(node.left, value) 
            : searchRec(node.right, value);
    }
    
    public void delete(int value) {
        root = deleteRec(root, value);
    }
    
    private Node deleteRec(Node node, int value) {
        if (node == null) {
            return null;
        }
        
        if (value < node.value) {
            node.left = deleteRec(node.left, value);
        } else if (value > node.value) {
            node.right = deleteRec(node.right, value);
        } else {
            // Node with only one child or no child
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            
            // Node with two children
            node.value = minValue(node.right);
            node.right = deleteRec(node.right, node.value);
        }
        
        return node;
    }
    
    private int minValue(Node node) {
        int minv = node.value;
        while (node.left != null) {
            minv = node.left.value;
            node = node.left;
        }
        return minv;
    }
    
    public void inOrderTraversal() {
        inOrderRec(root);
    }
    
    private void inOrderRec(Node node) {
        if (node != null) {
            inOrderRec(node.left);
            System.out.print(node.value + " ");
            inOrderRec(node.right);
        }
    }
}

Tree Applications

1. File systems: Hierarchical file organization
2. Database indexing: B-trees for efficient data retrieval
3. Expression trees: Mathematical expression evaluation
4. Decision trees: Machine learning algorithms

Tree Complexity

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Graph

Graph Representation

public class GraphDemo {
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        
        // Add edges
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);
        
        System.out.println("BFS traversal:");
        graph.BFS(0); // 0 1 2 3 4 5
        
        System.out.println("\nDFS traversal:");
        graph.DFS(0); // 0 1 3 5 4 2
    }
}

class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjList;
    
    @SuppressWarnings("unchecked")
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }
    
    public void addEdge(int src, int dest) {
        adjList[src].add(dest);
        adjList[dest].add(src); // For undirected graph
    }
    
    public void BFS(int startVertex) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[startVertex] = true;
        queue.add(startVertex);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (Integer neighbor : adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
    
    public void DFS(int startVertex) {
        boolean[] visited = new boolean[vertices];
        DFSRec(startVertex, visited);
    }
    
    private void DFSRec(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");
        
        for (Integer neighbor : adjList[vertex]) {
            if (!visited[neighbor]) {
                DFSRec(neighbor, visited);
            }
        }
    }
}

Graph Applications

1. Social networks: Friend relationships
2. Navigation systems: Shortest path algorithms
3. Network routing: Data packet routing
4. Dependency resolution: Task scheduling

Graph Complexity

Operation	Adjacency List	Adjacency Matrix
Add vertex	O(1)	O(V²)
Add edge	O(1)	O(1)
Remove edge	O(E)	O(1)
Search	O(V + E)	O(V²)

Algorithm Analysis

Big O Notation Summary

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)
Heap	O(n)	O(n)	O(log n)	O(log n)
BST	O(log n)	O(log n)	O(log n)	O(log n)
Graph	-	O(V + E)	O(1)	O(E)

Choosing the Right Data Structure

1. Array: When you need fast random access
2. Stack: When you need LIFO order (function calls, undo)
3. Queue: When you need FIFO order (task scheduling)
4. Heap: When you need priority-based access
5. Tree: When you need hierarchical organization
6. Graph: When you need network relationships

Best Practices

1. Choose the right structure: Consider your use case requirements
2. Understand complexity: Know the time and space complexity
3. Use built-in implementations: Leverage standard library implementations
4. Consider memory usage: Balance time and space efficiency
5. Test thoroughly: Verify correctness with various inputs