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

Real-world analogy

What is it?

Stack, Queue, LinkedList, binary search, and heap are intermediate data structures that underpin common interview patterns — undo systems, BFS, sorted data search, and top-K selection — all of which have direct parallels in mobile app development.

Real-world relevance

Tixio's message editor uses a stack for undo history. The offline sync queue in FieldBuzz is a FIFO queue processed in order. Binary search finds a message by timestamp in the local SQLite cache sorted by createdAt. A priority queue ranks notifications by urgency in the notification triage system.

Key points

• Stack fundamentals — Stack: LIFO (Last In, First Out). Dart: use List as a stack — add() pushes, removeLast() pops, last peeks. O(1) for all operations. Applications: undo/redo history, expression evaluation, bracket matching, DFS traversal, call stack simulation. In Flutter: Navigator uses a stack internally.
• Stack pattern: bracket matching — Classic interview problem. Iterate string: if opening bracket push to stack; if closing bracket, check if stack is empty (invalid) or top doesn't match (invalid), else pop. After iteration: stack must be empty. O(n) time, O(n) space. Extends to: valid HTML tag matching, arithmetic expression validation.
• Monotonic stack pattern — A stack that maintains elements in increasing or decreasing order. As you push, pop elements that violate the order. Used for: next greater element, largest rectangle in histogram, daily temperatures. Pattern: for each element, while stack not empty and top violates order, pop and process. Push current element.
• Queue fundamentals — Queue: FIFO (First In, First Out). Dart: use Queue from dart:collection — addLast() enqueues, removeFirst() dequeues, both O(1). List-as-queue (removeAt(0)) is O(n) — avoid for performance. Applications: BFS traversal, task scheduling, rate limiting, message processing.
• Binary search pattern — Binary search requires a sorted collection (or a monotonic condition). Template: int left=0, right=n-1; while(left<=right){ int mid=left+(right-left)~/2; if(arr[mid]==target) return mid; if(arr[mid]<target) left=mid+1; else right=mid-1; } return -1. O(log n). Common mistake: integer overflow in mid = (left+right)~/2 — use left+(right-left)~/2.
• Binary search variations — Find first occurrence: when match found, don't return — set right=mid-1 and continue. Find last occurrence: set left=mid+1 and continue. Search in rotated sorted array: determine which half is sorted, check if target falls in that half. Binary search on answer: use binary search on the answer range when the check function is monotonic.
• Heap and priority queue — Heap is a complete binary tree satisfying the heap property. Min-heap: parent ≤ children (root is minimum). Max-heap: parent ≥ children. Dart: no built-in heap — use package:collection PriorityQueue or implement manually. PriorityQueue operations: O(log n) add, O(log n) removeFirst, O(1) first. Used for: top-K problems, Dijkstra's algorithm, merge K sorted lists.
• Top-K pattern with heap — Find K largest elements. Approach 1: sort descending, take first K — O(n log n). Approach 2: min-heap of size K — iterate array, add to heap, if size>K remove minimum. Result is K largest in O(n log K). Better when K << n. In mobile context: 'show top 5 most active channels' — heap beats sorting full list.
• Linked list concepts for interviews — Linked list: nodes with value + next pointer. No random access (O(n) to reach index i). O(1) insert/delete at known node. Dart has no built-in LinkedList for interviews — represent as a class: class ListNode { int val; ListNode? next; }. Common problems: reverse linked list, detect cycle (Floyd's), find middle (slow/fast pointers), merge two sorted lists.
• Fast and slow pointers (Floyd's algorithm) — Two pointers at different speeds detect cycles in O(n) time O(1) space. Slow pointer moves 1 step, fast moves 2 steps. If they meet: cycle exists. To find cycle start: reset slow to head, advance both by 1 until they meet — meeting point is cycle start. Find middle of list: when fast reaches end, slow is at middle.
• Mobile-relevant applications — Stack: undo history in Tixio text editor (push state on change, pop on Ctrl+Z). Queue: message send queue (FIFO ensures order). Priority queue: notification triage (urgent alerts before regular). Binary search: find message by timestamp in sorted message history. These aren't theoretical — they're patterns you've implemented.
• Complexity summary for this lesson — Stack ops: O(1) push/pop/peek. Queue ops: O(1) enqueue/dequeue with Queue class. Binary search: O(log n) time O(1) space. Heap insert: O(log n). Heap peek: O(1). Linked list access: O(n). Linked list insert at head: O(1). Know these cold — interviewers ask follow-up complexity questions after every solution.

Code example

// Stack: bracket/parenthesis validation
bool isValid(String s) {
  final stack = <String>[];
  const pairs = {'(': ')', '[': ']', '{': '}'};
  for (final c in s.split('')) {
    if (pairs.containsKey(c)) {
      stack.add(c);
    } else {
      if (stack.isEmpty || pairs[stack.last] != c) return false;
      stack.removeLast();
    }
  }
  return stack.isEmpty;
}

// Binary search: find message by timestamp in sorted list
int findByTimestamp(List<int> timestamps, int target) {
  int left = 0, right = timestamps.length - 1;
  while (left <= right) {
    final mid = left + (right - left) ~/ 2;
    if (timestamps[mid] == target) return mid;
    if (timestamps[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // not found
}

// Heap pattern: top-K most active channels
// Using sorted list as simple min-heap simulation
List<String> topKChannels(Map<String, int> activity, int k) {
  final entries = activity.entries.toList()
    ..sort((a, b) => b.value.compareTo(a.value));
  return entries.take(k).map((e) => e.key).toList();
}

// Linked list: reverse (iterative)
class ListNode {
  int val;
  ListNode? next;
  ListNode(this.val, [this.next]);
}

ListNode? reverseList(ListNode? head) {
  ListNode? prev, curr = head;
  while (curr != null) {
    final next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Fast/slow pointers: find middle of linked list
ListNode? findMiddle(ListNode? head) {
  ListNode? slow = head, fast = head;
  while (fast?.next != null) {
    slow = slow?.next;
    fast = fast?.next?.next;
  }
  return slow;
}

Line-by-line walkthrough

1. 1. isValid iterates each character of the string once — O(n)
2. 2. Opening brackets push to stack; closing brackets must match the top
3. 3. pairs map connects each opener to its expected closer
4. 4. If stack is empty when a closer arrives — no matching opener — return false
5. 5. If stack top doesn't match the closer — mismatched pair — return false
6. 6. At the end, empty stack confirms all openers were closed
7. 7. findByTimestamp implements standard binary search on sorted timestamps
8. 8. mid = left + (right-left)~/2 avoids integer overflow vs (left+right)~/2
9. 9. reverseList iterates once, reversing next pointers in-place — O(n) O(1) space
10. 10. prev starts null (new tail), curr walks forward, next saves the link before overwriting
11. 11. findMiddle advances fast 2x speed — when fast hits the end, slow is at middle
12. 12. This is O(n) time O(1) space — optimal for finding list midpoint

Spot the bug

// Binary search implementation
int binarySearch(List<int> arr, int target) {
  int left = 0, right = arr.length;
  while (left < right) {
    int mid = (left + right) ~/ 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) left = mid;
    else right = mid - 1;
  }
  return -1;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Dart Queue class — dart:collection (api.dart.dev)
• package:collection PriorityQueue (pub.dev)
• NeetCode — Stack patterns (neetcode.io)
• Binary Search variations — LeetCode Explore (leetcode.com)