005 — Stacks

05 — Stacks

Of all the data structures in this wiki, the stack is the one whose real-world name is literally the data structure. There's no metaphor to translate — a stack of plates behaves exactly like a Stack<T>.

---

🍽️ Intuition

Picture a stack of cafeteria trays at the start of the line. You only ever interact with the top tray — you take the top one, or you place a new one on top. You never reach into the middle of the stack to grab the fifth tray down; if you want it, you have to remove the four trays above it first.

• 🍽️ Last tray placed on top = first tray taken off. Last In, First Out — LIFO.
• 🧱 The bottom tray is essentially "locked" until everything above it is gone.

That's it. That's a stack.

---

🧠 What It Is & When To Reach For It

A stack supports exactly two core operations at one end (the "top"): push (add) and pop (remove). Optionally, peek lets you look at the top without removing it. There's no reaching into the middle — that's the whole point of the structure. It enforces a discipline, not just a capability.

Swift doesn't ship a dedicated Stack type, but Array already behaves perfectly as one: append and removeLast both operate on the end of the array, and both are O(1) (amortized for append) — no shifting required, unlike operating on the front of an array.

Reach for a stack when:

• You need to reverse order naturally (undo history, browser back button).
• You're matching nested/paired structures — parentheses, brackets, HTML tags, anything where "the most recently opened thing must be the first thing closed."
• You're doing a depth-first traversal iteratively (an explicit stack replaces the recursion call stack).
• You're evaluating expressions (converting infix to postfix, evaluating postfix, tracking operator precedence).
• You need to track "what am I currently in the middle of" — the actual function call stack in every programming runtime is, unsurprisingly, a stack.

---

📊 ASCII Diagram

        push 42 ──▶ ┌────┐
                     │ 42 │  ← top (only accessible element)
                     ├────┤
                     │  7 │
                     ├────┤
                     │ 25 │
                     ├────┤
                     │ 10 │  ← bottom (locked until everything above is popped)
                     └────┘

pop() removes and returns 42 (the top) → next pop() would return 7, then 25, then 10.

---

💻 Swift Implementation

Idiomatic stdlib usage — Array as a stack

var stack: [Int] = []

stack.append(10)     // push — O(1) amortized
stack.append(25)
stack.append(7)

let top = stack.last          // peek — O(1), doesn't remove
let popped = stack.popLast()  // pop — O(1), returns Int? (nil if empty)

let isEmpty = stack.isEmpty   // O(1)

popLast() is preferred over removeLast() here because it returns nil instead of crashing on an empty array — handy for loops like while let value = stack.popLast() { ... }.

Hand-rolled: a generic Stack<T>

Interviews often want the wrapper type explicitly, both to prove you understand the discipline (no reaching into the middle) and because it reads clearly at call sites.

struct Stack<T> {
    private var elements: [T] = []

    var isEmpty: Bool { elements.isEmpty }
    var count: Int { elements.count }

    mutating func push(_ value: T) {
        elements.append(value)               // O(1) amortized
    }

    @discardableResult
    mutating func pop() -> T? {
        elements.popLast()                   // O(1)
    }

    func peek() -> T? {
        elements.last                        // O(1)
    }
}

That's it — the entire value of this type is that it hides Array's front-facing operations (insert(at: 0), first, removeFirst()) so nobody accidentally uses the stack the wrong way.

---

⏱️ Core Operations & Big-O

Operation	Big-O	Why
Push	O(1) amortized	Appending to the end of the underlying array — no shifting. Occasional resize is amortized away. See Big-O Notation.
Pop	O(1)	Removing the last element needs no shifting of anything before it.
Peek	O(1)	Just reads the last element, no removal.
Search (is x anywhere in the stack?)	O(n)	You'd have to pop everything (or scan) to look past the top — stacks aren't built for this.
isEmpty	O(1)	Just checks the count.

---

🧸 Memory Sentence

A stack is a stack of cafeteria trays — you only ever touch the top, so the last tray placed is always the first one taken.

---

✅ Check Your Understanding

Using only a single stack (no other data structure), trace through checking whether the string "([)]" has balanced brackets. Push opening brackets; on a closing bracket, compare it against the top of the stack. Walk through each character step by step and explain exactly which comparison fails and why that correctly proves the string is not balanced — even though it has equal numbers of (, ), [, and ].

---

⬅️ Previous: Linked Lists · Next: Queues and Deques ➡️