Stacks — The Complete Visual Reference

// ⚠ DON'T — java.util.Stack is legacy & synchronized val bad = java.util.Stack<Int>() bad.push(1) // synchronized — unnecessary overhead bad.pop() // Vector-based — allows random access // ✓ DO — Kotlin ArrayDeque val stack = ArrayDeque<Int>() stack.addLast(1) // push stack.removeLast() // pop stack.last() // peek

// ── Empty stack ── val stack = ArrayDeque<Int>() // ── From a list ── val stack = ArrayDeque(listOf(1, 2, 3)) // 3 is top // ── From a range ── val stack = ArrayDeque((1..5).toList()) // [1,2,3,4,5] // ── Typed wrapper class ── class Stack<T> { private val data = ArrayDeque<T>() fun push(item: T) = data.addLast(item) fun pop(): T = data.removeLast() fun peek(): T = data.last() fun isEmpty() = data.isEmpty() val size get() = data.size }

val stack = ArrayDeque<Int>() // ── Push ── stack.addLast(10) // [10] stack.addLast(20) // [10, 20] stack.addLast(30) // [10, 20, 30] // ── Peek (view top) ── stack.last() // 30 — throws if empty stack.lastOrNull() // 30 — null if empty (safe) // ── Pop (remove top) ── stack.removeLast() // 30 — throws if empty stack.removeLastOrNull() // 20 — null if empty (safe) // ── Safe patterns ── if (stack.isNotEmpty()) stack.removeLast() stack.removeLastOrNull() ?: defaultValue

// ── Drain (pop all elements) ── while (stack.isNotEmpty()) { val item = stack.removeLast() // process item (LIFO order) } // ── Iterate without modifying ── for (item in stack) { } // bottom → top order // ── Reversed iteration (top → bottom) ── for (item in stack.reversed()) { } // ── Convert to list ── stack.toList() // bottom → top stack.reversed() // top → bottom stack.joinToString() // "10, 20, 30"

// ── Array-based Stack ── class ArrayStack<T> { private var data = arrayOfNulls<Any>(8) private var size = 0 fun push(item: T) { if (size == data.size) resize() data[size++] = item } fun pop(): T { if (size == 0) throw NoSuchElementException() val item = data[--size] as T data[size] = null // prevent memory leak return item } fun peek(): T = data[size - 1] as T private fun resize() { data = data.copyOf(data.size * 2) } } // ── Linked-list Stack ── class LinkedStack<T> { private class Node<T>(val value: T, val next: Node<T>?) private var head: Node<T>? = null fun push(item: T) { head = Node(item, head) } fun pop(): T { val node = head ?: throw NoSuchElementException() head = node.next return node.value } fun peek(): T = head?.value ?: throw NoSuchElementException() }

// ── Valid parentheses with multiple bracket types ── fun isValid(s: String): Boolean { val pairs = mapOf(')' to '(', ']' to '[', '}' to '{') val stack = ArrayDeque<Char>() for (ch in s) { if (ch in pairs.values) { stack.addLast(ch) } else if (ch in pairs) { if (stack.isEmpty() || stack.removeLast() != pairs[ch]) return false } } return stack.isEmpty() } // ── Longest valid parentheses ── fun longestValidParentheses(s: String): Int { val stack = ArrayDeque<Int>() stack.addLast(-1) // sentinel var maxLen = 0 for (i in s.indices) { if (s[i] == '(') { stack.addLast(i) } else { stack.removeLast() if (stack.isEmpty()) stack.addLast(i) else maxLen = maxOf(maxLen, i - stack.last()) } } return maxLen }

class MinStack { private val stack = ArrayDeque<Int>() private val minStack = ArrayDeque<Int>() fun push(x: Int) { stack.addLast(x) val curMin = if (minStack.isEmpty()) x else minOf(x, minStack.last()) minStack.addLast(curMin) } fun pop() { stack.removeLast() minStack.removeLast() } fun top(): Int = stack.last() fun getMin(): Int = minStack.last() }

fun evalRPN(tokens: Array<String>): Int { val stack = ArrayDeque<Int>() for (token in tokens) { when (token) { "+", "-", "*", "/" -> { val b = stack.removeLast() val a = stack.removeLast() stack.addLast(when (token) { "+" -> a + b "-" -> a - b "*" -> a * b else -> a / b // truncate toward zero }) } else -> stack.addLast(token.toInt()) } } return stack.last() }

// ── Next Greater Element ── fun nextGreaterElement(nums: IntArray): IntArray { val result = IntArray(nums.size) { -1 } val stack = ArrayDeque<Int>() // indices for (i in nums.indices) { while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) { result[stack.removeLast()] = nums[i] } stack.addLast(i) } return result } // ── Next Smaller Element ── fun nextSmallerElement(nums: IntArray): IntArray { val result = IntArray(nums.size) { -1 } val stack = ArrayDeque<Int>() for (i in nums.indices) { while (stack.isNotEmpty() && nums[stack.last()] > nums[i]) { result[stack.removeLast()] = nums[i] } stack.addLast(i) } return result }

fun largestRectangleArea(heights: IntArray): Int { val stack = ArrayDeque<Int>() // indices var maxArea = 0 val h = heights + 0 // sentinel triggers final cleanup for (i in h.indices) { while (stack.isNotEmpty() && h[stack.last()] > h[i]) { val height = h[stack.removeLast()] val width = if (stack.isEmpty()) i else i - stack.last() - 1 maxArea = maxOf(maxArea, height * width) } stack.addLast(i) } return maxArea }

fun trap(height: IntArray): Int { val stack = ArrayDeque<Int>() // indices var water = 0 for (i in height.indices) { while (stack.isNotEmpty() && height[stack.last()] < height[i]) { val bottom = height[stack.removeLast()] if (stack.isEmpty()) break val width = i - stack.last() - 1 val bounded = minOf(height[i], height[stack.last()]) - bottom water += width * bounded } stack.addLast(i) } return water }

fun dailyTemperatures(temps: IntArray): IntArray { val result = IntArray(temps.size) val stack = ArrayDeque<Int>() // indices for (i in temps.indices) { while (stack.isNotEmpty() && temps[stack.last()] < temps[i]) { val j = stack.removeLast() result[j] = i - j } stack.addLast(i) } return result }

fun simplifyPath(path: String): String { val stack = ArrayDeque<String>() for (part in path.split("/")) { when (part) { ".." -> if (stack.isNotEmpty()) stack.removeLast() ".", "" -> { } // skip else -> stack.addLast(part) } } return "/" + stack.joinToString("/") }

// "3[a2[c]]" → "accaccacc" fun decodeString(s: String): String { val countStack = ArrayDeque<Int>() val stringStack = ArrayDeque<StringBuilder>() var current = StringBuilder() var k = 0 for (ch in s) { when { ch.isDigit() -> k = k * 10 + (ch - '0') ch == '[' -> { countStack.addLast(k) stringStack.addLast(current) current = StringBuilder() k = 0 } ch == ']' -> { val decoded = stringStack.removeLast() val count = countStack.removeLast() repeat(count) { decoded.append(current) } current = decoded } else -> current.append(ch) } } return current.toString() }

// ── Calculator I: +, -, parentheses ── fun calculate(s: String): Int { val stack = ArrayDeque<Int>() var result = 0; var num = 0; var sign = 1 for (ch in s) { when { ch.isDigit() -> num = num * 10 + (ch - '0') ch == '+' || ch == '-' -> { result += sign * num; num = 0 sign = if (ch == '+') 1 else -1 } ch == '(' -> { stack.addLast(result) stack.addLast(sign) result = 0; sign = 1 } ch == ')' -> { result += sign * num; num = 0 result *= stack.removeLast() // sign result += stack.removeLast() // prev result } } } return result + sign * num } // ── Calculator II: +, -, *, / (no parens) ── fun calculateII(s: String): Int { val stack = ArrayDeque<Int>() var num = 0; var op = '+' for ((i, ch) in s.withIndex()) { if (ch.isDigit()) num = num * 10 + (ch - '0') if ((!ch.isDigit() && ch != ' ') || i == s.lastIndex) { when (op) { '+' -> stack.addLast(num) '-' -> stack.addLast(-num) '*' -> stack.addLast(stack.removeLast() * num) '/' -> stack.addLast(stack.removeLast() / num) } op = ch; num = 0 } } return stack.fold(0) { acc, v -> acc + v } }

fun asteroidCollision(asteroids: IntArray): IntArray { val stack = ArrayDeque<Int>() for (ast in asteroids) { var alive = true while (alive && ast < 0 && stack.isNotEmpty() && stack.last() > 0) { if (stack.last() < -ast) { stack.removeLast() // top explodes } else if (stack.last() == -ast) { stack.removeLast() // both explode alive = false } else { alive = false // current explodes } } if (alive) stack.addLast(ast) } return stack.toIntArray() }

fun removeKdigits(num: String, k: Int): String { var remaining = k val stack = ArrayDeque<Char>() for (digit in num) { while (remaining > 0 && stack.isNotEmpty() && stack.last() > digit) { stack.removeLast() remaining-- } stack.addLast(digit) } // Remove remaining from end repeat(remaining) { stack.removeLast() } // Trim leading zeros while (stack.isNotEmpty() && stack.first() == '0') { stack.removeFirst() } return if (stack.isEmpty()) "0" else stack.joinToString("") }

// ── Iterative DFS for graph ── fun dfsIterative(graph: Map<Int, List<Int>>, start: Int): List<Int> { val visited = mutableSetOf<Int>() val stack = ArrayDeque<Int>() val result = mutableListOf<Int>() stack.addLast(start) while (stack.isNotEmpty()) { val node = stack.removeLast() if (node in visited) continue visited.add(node) result.add(node) for (neighbor in (graph[node] ?: emptyList()).reversed()) { if (neighbor !in visited) stack.addLast(neighbor) } } return result } // ── Iterative inorder traversal for tree ── fun inorderIterative(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = ArrayDeque<TreeNode>() var curr = root while (curr != null || stack.isNotEmpty()) { while (curr != null) { stack.addLast(curr) curr = curr.left } curr = stack.removeLast() result.add(curr.`val`) curr = curr.right } return result }

// ── Batch version ── fun stockSpan(prices: IntArray): IntArray { val result = IntArray(prices.size) val stack = ArrayDeque<Int>() // indices for (i in prices.indices) { while (stack.isNotEmpty() && prices[stack.last()] <= prices[i]) { stack.removeLast() } result[i] = if (stack.isEmpty()) i + 1 else i - stack.last() stack.addLast(i) } return result } // ── Online version (streaming) ── class StockSpanner { private val stack = ArrayDeque<Pair<Int, Int>>() // (price, span) fun next(price: Int): Int { var span = 1 while (stack.isNotEmpty() && stack.last().first <= price) { span += stack.removeLast().second } stack.addLast(price to span) return span } }

// ⚠ Empty stack exception stack.removeLast() // 💥 NoSuchElementException if empty stack.last() // 💥 same // RIGHT: stack.removeLastOrNull() stack.lastOrNull() if (stack.isNotEmpty()) stack.removeLast() // ⚠ Wrong end of ArrayDeque stack.addFirst(x) // 💥 This is queue behavior, not stack! stack.removeFirst() // 💥 This is dequeue, not pop! // RIGHT: addLast/removeLast for stack // ⚠ java.util.Stack instead of ArrayDeque val bad = java.util.Stack<Int>() bad[2] // 💥 random access — breaks abstraction // RIGHT: Kotlin ArrayDeque // ⚠ Stack overflow with deep recursion fun deep(n: Int) { if (n > 0) deep(n - 1) } deep(100000) // 💥 StackOverflowError // RIGHT: convert to iterative with explicit stack // ⚠ Forgetting sentinel in monotonic problems // Without sentinel, elements remaining on stack // are never processed (e.g., largest rectangle) // RIGHT: append sentinel value (0 or Int.MIN_VALUE) // ⚠ Confusing stack order with output order // Stack iteration = bottom → top // Stack drain (pop all) = top → bottom // RIGHT: use reversed() if you need top → bottom list // ⚠ Memory leak in array-based stack // After pop, old reference still in array data[size] = null // RIGHT: null out after pop