Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

The replay uses the same three values in every language, so this Kotlin DSA implementation can be compared directly with the rest of the DSA track.

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Basic Implementation

basic.kt 
import java.util.ArrayDeque

fun render(values: List<Int>) = values.joinToString(" -> ")

fun main() {
    val stack = ArrayDeque<Int>()
    for (value in listOf(10, 20, 30)) stack.addLast(value)
    val popped = mutableListOf<Int>()
    while (!stack.isEmpty()) popped.add(stack.removeLast())
    println(render(popped))
}

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • Kotlin imports java.util.ArrayDeque and creates val stack = ArrayDeque<Int>(); the binding is not rebound, but the deque contents mutate.
  • Push uses stack.addLast(value) for listOf(10, 20, 30), making the back of the deque the stack top.
  • Pop uses stack.removeLast() inside while (!stack.isEmpty()), so the newest value is removed first.
  • The emptiness guard avoids the exception path for removeLast() on an empty deque; values are non-null Ints, not nullable pop results.
  • Popped values are collected in val popped = mutableListOf<Int>(), a separate mutable output list.
  • The trace shows stack=[], then [10, 20, 30], then popping 30 leaves [10, 20], and the final popped order is [30, 20, 10] with an empty stack.
  • render(values: List<Int>) uses joinToString(" -> "), and println(render(popped)) prints 30 -> 20 -> 10.