Stacks and Queues

Stack Push/Pop

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

Algorithm

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))
}

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

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.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.