DSA II: Stack, Queue, Linked List, Binary Search & Heap

Real-world analogy

What is it?

Stack, Queue, LinkedList, Binary Search, and Heap are the second tier of DSA patterns. They appear in ~40% of medium interview problems. Stacks and queues are often implemented on ArrayDeque in Kotlin. Binary search extends far beyond sorted arrays to any monotonic decision function. Heaps provide an efficient way to maintain a sorted subset of data for streaming and top-K problems.

Real-world relevance

In the Tixio real-time task management platform, notification delivery priority was implemented using a PriorityQueue — critical alerts (deadline missed, blocker added) were assigned higher priority and processed first even when multiple notifications were queued simultaneously. This is the heap pattern applied directly: always serve the highest-priority item next in O(log n) time.

Key points

• Stack — LIFO and Its Interview Patterns — Stack operations: push (add to top), pop (remove from top), peek (see top without removing) — all O(1). In Kotlin, use ArrayDeque as a stack. Key patterns: bracket matching (push opens, pop and verify on close), undo/redo systems, DFS traversal, monotonic stack (maintain ascending/descending order for next-greater-element problems).
• Valid Parentheses — Stack Classic — Given a string of brackets, check if they are balanced. Push opening brackets. On closing bracket: if stack is empty or top does not match, return false. Pop if match. After iteration, stack must be empty. O(n) time, O(n) space. Extension: use a HashMap to map closing to opening brackets for clean code.
• Monotonic Stack — Next Greater Element — Maintain a stack of indices in decreasing order of values. When a new element is greater than the stack top, the stack top has found its 'next greater element' — pop and record. Push the new element. This processes each element at most twice (push + pop), so O(n) overall. Used for: stock span, daily temperatures, largest rectangle in histogram.
• Queue — FIFO and BFS — Queue: add to back (enqueue), remove from front (dequeue) — both O(1). In Kotlin, ArrayDeque supports both stack and queue operations (addFirst/removeLast for stack, addLast/removeFirst for queue). Primary use: BFS traversal. Enqueue the root, then repeatedly dequeue a node and enqueue its unvisited neighbors.
• Linked List Concepts — A node contains a value and a pointer to the next node. Head is the first node, tail points to null. Insertion at head: O(1). Insertion at arbitrary position: O(n) to find it. No random access — must traverse. Key operations: reverse (iterative with prev/curr/next pointers), detect cycle (Floyd's fast/slow pointers), find middle (fast/slow where fast moves 2 steps).
• Reverse a Linked List (Iterative) — Use three pointers: prev=null, curr=head, next=null. Each iteration: save curr.next to next, point curr.next backward to prev, advance prev to curr, advance curr to next. When curr is null, prev is the new head. O(n) time, O(1) space. Recursive version is elegant but uses O(n) stack space — prefer iterative in interviews.
• Floyd's Cycle Detection — Use slow (1 step) and fast (2 steps) pointers. If there is a cycle, fast will eventually catch up to slow within the cycle. If fast reaches null, no cycle. O(n) time, O(1) space. Finding cycle entry: after detection, reset one pointer to head and advance both 1 step at a time — they meet at the cycle entry.
• Binary Search — Universal Template — Use for: sorted array search, search space minimization (find the minimum valid value), matrix search. Template: left=0, right=n-1. mid = left + (right-left)/2. If condition(mid), right=mid. Else left=mid+1. Loop ends when left==right — that is the answer. Key: define the invariant precisely. Common mistake: wrong boundary update causing infinite loops.
• Binary Search Variants — Lower bound (first position where value >= target): right=mid when found, left=mid+1 when not. Upper bound (first position where value > target): similar adjustment. Search in rotated sorted array: determine which half is sorted (compare mid to left), then check if target is in the sorted half. Always draw the invariant before coding.
• Heap / Priority Queue — A heap is a complete binary tree where the parent is always smaller (min-heap) or larger (max-heap) than its children. insert and removeTop are O(log n). peek is O(1). In Kotlin, PriorityQueue is a min-heap by default. For max-heap: PriorityQueue(compareByDescending { it }). Primary use: K-th largest/smallest, merge K sorted lists, task scheduling.
• Top-K Pattern with Heap — Find K largest elements: use a min-heap of size K. For each element, add it to the heap. If heap size > K, remove the minimum. After processing all elements, the heap contains the K largest. O(n log k) time — much better than sorting (O(n log n)) when k is small. For K smallest, use a max-heap.
• Interview Strategy for These Structures — Stack: 'matching', 'undo', 'nested structure' keywords. Queue: 'level by level', 'BFS', 'process in order received'. LinkedList: rarely implemented from scratch — know reverse and cycle detection, as these are the two canonical problems. Binary search: any 'find in sorted' or 'minimize the maximum' phrasing. Heap: any 'top K', 'streaming median', or 'merge sorted' phrasing.

Code example

// ─── VALID PARENTHESES (Stack, O(n)) ───
fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    val matching = mapOf(')' to '(', ']' to '[', '}' to '{')
    for (ch in s) {
        if (ch in "([{") {
            stack.addLast(ch)
        } else {
            if (stack.isEmpty() || stack.last() != matching[ch]) return false
            stack.removeLast()
        }
    }
    return stack.isEmpty()
}

// ─── REVERSE LINKED LIST (Iterative, O(n), O(1) space) ───
class ListNode(var value: Int, var next: ListNode? = null)

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var curr = head
    while (curr != null) {
        val next = curr.next  // save
        curr.next = prev      // reverse pointer
        prev = curr           // advance prev
        curr = next           // advance curr
    }
    return prev // prev is the new head when curr is null
}

// ─── DETECT CYCLE — FLOYD'S (O(n), O(1) space) ───
fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow == fast) return true // fast caught slow inside cycle
    }
    return false
}

// ─── BINARY SEARCH — UNIVERSAL TEMPLATE ───
fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

// ─── TOP-K LARGEST ELEMENTS (Min-Heap, O(n log k)) ───
fun topKLargest(nums: IntArray, k: Int): List<Int> {
    val minHeap = PriorityQueue<Int>() // min-heap by default
    for (num in nums) {
        minHeap.offer(num)
        if (minHeap.size > k) minHeap.poll() // remove smallest, keep K largest
    }
    return minHeap.toList()
}

Line-by-line walkthrough

1. 1. isValid uses a HashMap to map each closing bracket to its expected opening bracket — this avoids three separate if-checks and scales to any bracket type.
2. 2. When a closing bracket is encountered, we check two conditions with OR: stack is empty (nothing to match against) OR the top does not match. Either means invalid.
3. 3. reverseList saves curr.next before overwriting it — curr.next = prev breaks the forward link, so without saving, the rest of the list is lost.
4. 4. After the while loop in reverseList, curr is null and prev points to the last original node — which is now the new head of the reversed list.
5. 5. hasCycle initializes both slow and fast at head. The loop condition checks fast and fast.next both non-null because fast moves two steps — if fast.next were null, fast.next.next would throw a NullPointerException.
6. 6. binarySearch uses left + (right - left) / 2 to avoid integer overflow. If left = 1_000_000_000 and right = 1_500_000_000, their sum overflows Int.MAX_VALUE.
7. 7. topKLargest adds every element to the min-heap, then immediately removes the minimum if size exceeds k. After processing all elements, the heap contains exactly the k largest.
8. 8. PriorityQueue.poll() is O(log n) because removing the root of a heap requires re-heapifying down the tree. This gives topKLargest O(n log k) total — O(log k) per element.

Spot the bug

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var curr = head
    while (curr != null) {
        curr.next = prev
        prev = curr
        curr = curr.next
    }
    return prev
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• LeetCode — Valid Parentheses (LeetCode)
• LeetCode — Reverse Linked List (LeetCode)
• LeetCode — Kth Largest Element in a Stream (LeetCode)
• Binary Search Template — LeetCode Discuss (LeetCode)
• Neetcode — Stack, Binary Search, Heap Patterns (Neetcode)