Stack

Struktur LIFO (Last In, First Out): elemen ditambahkan dan diambil dari ujung yang sama (top).

Kompleksitas

Waktu (Terbaik)

O(1)

Waktu (Rata-rata)

O(1)

Waktu (Terburuk)

O(1)

Memori

O(n)

Poin Penting

›LIFO: elemen yang terakhir di-push adalah yang pertama di-pop
›Push, Pop, dan Peek semuanya O(1)
›Biasanya diimplementasikan dengan dynamic array atau linked list
›Menjadi dasar call stack fungsi, fitur undo/redo, dan evaluasi ekspresi
›Banyak masalah rekursif bisa ditulis ulang secara iteratif dengan stack eksplisit

Contoh Kode

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

Latihan Soal

Valid Parentheses

MudahLeetCode ↗

Min Stack

SedangLeetCode ↗

Evaluate Reverse Polish Notation

SedangLeetCode ↗

Daily Temperatures

SedangLeetCode ↗