Stack

A LIFO (Last In, First Out) structure where elements are added and removed from the same end (top).

Complexity

Time (Best)

O(1)

Time (Avg)

O(1)

Time (Worst)

O(1)

Space

O(n)

Key Points

›LIFO: the last element pushed is the first popped
›Push, Pop, and Peek are all O(1)
›Typically implemented with a dynamic array or linked list
›Powers the function call stack, undo/redo, and expression evaluation
›Many recursive problems can be rewritten iteratively using an explicit stack

Code Examples

Swift

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

    mutating func push(_ element: T) {
        elements.append(element)
    }

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

    func peek() -> T? { elements.last }
    var isEmpty: Bool { elements.isEmpty }
    var count: Int { elements.count }
}

var stack = Stack<Int>()
stack.push(1); stack.push(2); stack.push(3)
print(stack.peek()!)  // 3
stack.pop()
print(stack.count)    // 2

Practice Problems

Valid Parentheses

EasyLeetCode ↗

Min Stack

MediumLeetCode ↗

Evaluate Reverse Polish Notation

MediumLeetCode ↗

Daily Temperatures

MediumLeetCode ↗