STACKS, QUEUES,
HEAPS & HASH.

Stack (LIFO)

Stack Implementation (Java)

import java.util.*;

// Using Stack class
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop();
int peek = stack.peek();

// Using Deque (recommended)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // addFirst
stack.push(2);
int top = stack.pop();  // removeFirst
int peek = stack.peek(); // getFirst

Stack Patterns

• Balanced Parentheses – push opening, pop on closing
• Next Greater Element – monotonic decreasing stack
• Next Smaller Element – monotonic increasing stack
• Histogram Area – monotonic stack for largest rectangle
• Evaluate Expression – postfix/infix conversion
• DFS Iterative – replace recursion with stack

Common Stack Problems

---

Queue (FIFO)

Queue Implementation (Java)

import java.util.*;

// Using LinkedList (Queue)
Queue<Integer> q = new LinkedList<>();
q.offer(1);      // add
q.offer(2);
int front = q.poll();  // remove
int peek = q.peek();   // view front

// Using Deque as Queue
Deque<Integer> q = new ArrayDeque<>();
q.offer(1);
q.offer(2);
int front = q.poll();

Queue Patterns

• BFS – level‑order traversal
• Sliding Window – maintain window with deque
• Producer‑Consumer – thread‑safe queue
• Round Robin – scheduling
• Deque – sliding window max/min

Common Queue Problems

---

Heap (Priority Queue)

Heap Implementation (Java)

import java.util.*;

// Min‑Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
int min = minHeap.poll();  // 1

// Max‑Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
int max = maxHeap.poll();  // 5

// Custom comparator
PriorityQueue<int[]> heap = new PriorityQueue<>(
    (a, b) -> a[0] - b[0]
);

Heap Sort

void heapSort(int[] arr) {
    // Build max‑heap
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, arr.length, i);
    }
    // Extract elements one by one
    for (int i = arr.length - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

Heap Patterns

• K largest/smallest – maintain heap of size k
• Median of stream – two heaps (min + max)
• Merge K sorted lists – heap of heads
• Dijkstra – priority queue for shortest path
• Top K frequent – heap with frequency
• Find K closest points – distance based heap

Common Heap Problems

---

Hash Table

Hash Table Implementation (Java)

import java.util.*;

// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);
int age = map.get("Alice");
map.remove("Bob");
boolean hasKey = map.containsKey("Alice");

// Iterate
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
boolean contains = set.contains(1);

// LinkedHashMap (preserves insertion order)
Map<String, Integer> linkedMap = new LinkedHashMap<>();

// TreeMap (sorted keys)
Map<String, Integer> treeMap = new TreeMap<>();

// ConcurrentHashMap (thread‑safe)
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

Hash Table Patterns

• Frequency Counter – count occurrences
• Two Sum / Pair Sum – complement lookup
• Anagrams – char frequency maps
• Subarray Sum Equals K – prefix sum with map
• Cache (LRU) – LinkedHashMap or custom
• Intervals – merge/overlap with key
• Union‑Find – parent mapping
• Graph Adjacency – adjacency list

Common Hash Table Problems

Complexities Summary

Structure	Access	Search	Insert	Delete
Stack	O(1)	O(n)	O(1)	O(1)
Queue	O(1)	O(n)	O(1)	O(1)
Heap (Min/Max)	O(1)	O(n)	O(log n)	O(log n)
Hash Table (avg)	O(1)	O(1)	O(1)	O(1)
Hash Table (worst)	O(n)	O(n)	O(n)	O(n)