Інваріанти та граничні випадки: pop() із порожнього стека

1. Інваріант: правила для контейнера

Коли ви пишете структуру даних, то фактично будуєте маленький світ зі своїми законами фізики. У цьому світі стек має свої обіцянки: як він зберігає елементи, що вважається «верхом», які операції допустимі та що саме вони гарантують. Інваріант — це якраз така обіцянка, яка має бути правдою завжди: до і після кожного публічного методу. Інакше стек перетворюється на «коробку із сюрпризами».

Інваріант корисний не лише «для краси». Він допомагає писати код простіше, бо варіантів стану менше; швидше, бо ми обираємо дешеві операції; і безпечніше, бо заздалегідь вирішуємо, що робити на межах: коли порожньо, коли є один елемент або коли їх багато.

Уявіть, що ви робите конструктор LEGO. Інваріант — це правило «деталь №X завжди прикріплена ось сюди». Якщо ви його порушили, уся конструкція може виглядати «майже зібраною», але розвалиться, щойно ви спробуєте її підняти.

2. Інваріант реалізації стека: LIFO і «верх = кінець масиву»

Стек зазвичай описують коротко: LIFO (Last In — First Out), «останнім поклали — першим дістали». Але це радше поведінка. А нам потрібен ще й інваріант реалізації: як ми забезпечуємо цю поведінку всередині.

Найпрактичніший інваріант для стека на масиві звучить так:

«Верх стека — це кінець масиву items».

Тобто:

• push кладе елемент у кінець масиву (append)
• pop знімає елемент з кінця масиву (popLast)
• peek дивиться в кінець масиву (last)

Чому це важливо? Бо операції з кінця масиву для Array природні й зазвичай дешеві. А от операції з початку масиву, наприклад removeFirst, — це вже інша історія. Дуже легко випадково зробити стек повільним.

Невелика схема (знизу — «дно», зверху — «верх»):

items = [A, B, C]
         ↑     ↑
       дно    верх

І ось так працює LIFO:

push(D)  -> [A, B, C, D]
pop()    -> поверне D, залишиться [A, B, C]

Давайте зафіксуємо це в коді.

import Foundation

struct Stack<T> {
    // Деталь реалізації: ззовні ніхто не повинен чіпати масив напряму
    private var items: [T] = []

    mutating func push(_ value: T) {
        items.append(value)              // верх = кінець
    }

    mutating func pop() -> T? {
        items.popLast()                  // верх = кінець
    }
}

Ключовий момент: якщо ми вирішили «верх = кінець масиву», то ми більше не повинні писати реалізацію, яка робить верхом початок. Навіть якщо вона «ніби теж працює». Інваріанти — не про «ніби», а про «завжди однаково».

3. Порожній стек — нормальний стан

Початківці часто підсвідомо сприймають порожнечу як помилку: «ой, порожньо, значить щось пішло не так». На практиці порожній стек — це звичайний стан, як порожній кошик в інтернет-магазині: він не зламаний, він просто поки що без покупок. І це, до речі, корисно для бюджету.

Тому ми маємо заздалегідь відповісти на запитання: що означає pop() на порожньому стеку?

У нашому контракті (повернення T?) відповідь проста:

«Якщо стек порожній, pop() повертає nil і не змінює стан».

Це важливо: «не змінює стан» означає, що якщо стек був порожній, він і залишається порожнім. Не зʼявляється «мінус один елемент», не відбувається спроба видалити щось із порожнечі, не виникає випадкова помилка доступу до памʼяті. Просто nil.

Перевіримо поведінку:

import Foundation

var s = Stack<Int>()

let a = s.pop()
print(a as Any)     // nil

Тут as Any потрібен лише для зручного виведення nil (інакше print іноді скаржиться на Optional у різних контекстах).

І ще один важливий випадок: «витягли останній елемент, а потім витягли ще раз».

import Foundation

var s = Stack<String>()
s.push("A")

print(s.pop() as Any)   // Optional("A")
print(s.pop() as Any)   // nil

Жодних збоїв, жодних index out of range. Порожнеча виражена чесно.

4. popLast() vs removeLast(): безпечний контракт

Далі Swift буквально дає вам два інструменти: один безпечний, другий — «для тих, хто впевнений, що ніколи не помиляється». І вгадайте, хто частіше помиляється? Правильно: всі.

У масиву є два близькі методи:

• popLast() повертає Optional і повертає nil, якщо масив порожній.
• removeLast() повертає звичайний Element і вимагає, щоб масив не був порожнім (інакше програма падає).

Ця різниця прямо пов’язана з їхнім контрактом: removeLast вважає порожнечу порушенням передумови, а popLast — нормальним варіантом результату.

Ось так виглядає «поганий стек», який іноді падає:

import Foundation

struct BadStack<T> {
    private var items: [T] = []

    mutating func pop() -> T {
        // Так не можна, якщо порожній стек — допустимий стан:
        return items.removeLast() // збій, якщо items порожній
    }
}

А ось так виглядає коректна реалізація для нашого контракту:

import Foundation

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

    mutating func push(_ value: T) {
        items.append(value)
    }

    mutating func pop() -> T? {
        return items.popLast() // nil, якщо порожньо
    }
}

Якщо ви запам’ятаєте із сьогоднішньої лекції лише одне правило, нехай це буде воно:

«Якщо порожнеча — нормальний сценарій, використовуйте операції, які виражають порожнечу в типах (Optional), а не операції з передумовою, які падають».

5. Захищаємо інваріанти: private, peek, count

Є ще одна тиха катастрофа, яка вбиває інваріанти без жодного попередження: коли внутрішній устрій контейнера стає публічним, і зовнішній код починає «допомагати».

Наприклад, якби items був доступний ззовні, хтось міг би зробити так:

// уявіть, що items НЕ private
// stack.items.insert(value, at: 0)   // і «верх» раптом став початком

Зовнішній код не зобов’язаний пам’ятати ваш інваріант «верх = кінець масиву». Він узагалі не зобов’язаний нічого знати про нього. Тому інваріант захищають дві речі: інкапсуляція і правильні методи читання.

Додамо безпечні властивості:

import Foundation

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

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

    var peek: T? {
        items.last            // дивимося на верх, але не видаляємо
    }

    mutating func push(_ value: T) {
        items.append(value)
    }

    mutating func pop() -> T? {
        items.popLast()
    }
}

Зверніть увагу: peek теж повертає T?. Чому? Бо «подивитися на верх» на порожньому стеку — це той самий граничний випадок: елемента немає.

Перевіримо, що peek нічого не ламає:

import Foundation

var s = Stack<Int>()
s.push(10)
s.push(20)

print(s.peek as Any)    // Optional(20)
print(s.count)          // 2
print(s.peek as Any)    // Optional(20)
print(s.count)          // 2

Якщо після peek змінюється count, це вже не peek, а pop у масці.

6. Контракт стека та перевірки інваріантів

Контракт: що ми гарантуємо

Корисно прямо сформулювати, що саме ми вважаємо інваріантом і граничною поведінкою. Це звучить трохи бюрократично, зате різко зменшує кількість багів.

Невелика таблиця «домовленостей» нашого Stack<T>:

push(x)

x

pop()

nil

peek

nil

count

0

isEmpty

true

І ось маленька блок-схема для pop():

flowchart TD
    A["Викликали pop()"] --> B{items порожній?}
    B -->|так| C[Повернути nil]
    B -->|ні| D[Видалити останній елемент]
    D --> E[Повернути видалений елемент]

Коли у вас у голові така модель, реалізація стає майже очевидною: «порожньо → nil, інакше → popLast».

Перевіряємо інваріанти через assert

Інваріант — це не лише думка в голові; його можна, а іноді й потрібно перевіряти. Але важливо розуміти філософію: assert — це перевірка для розробника, а не обробка користувацького введення.

Ми можемо зробити внутрішній метод «самоперевірки» і викликати його в ключових місцях. У навчальних цілях це дуже корисно: ви одразу бачите, де контейнер зламав сам себе.

Приклад: ми хочемо бути впевнені, що isEmpty узгоджений із count.

import Foundation

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

    var count: Int { items.count }
    var isEmpty: Bool { items.isEmpty }
    var peek: T? { items.last }

    mutating func push(_ value: T) {
        items.append(value)
        assertInvariants()
    }

    mutating func pop() -> T? {
        let v = items.popLast()
        assertInvariants()
        return v
    }

    private func assertInvariants() {
        // Інваріант узгодженості
        assert((count == 0) == isEmpty, "Порушення: count і isEmpty мають збігатися за змістом")
        // «Верх = кінець масиву» тут не перевіряється напряму,
        // але він зафіксований самим вибором append/popLast/last.
    }
}

Це не обов’язкова частина бойового коду, але як навчальний інструмент — чудовий спосіб упіймати помилку там, де вона виникла, а не через десять кроків, коли «десь потім усе стало дивним».

7. Мініінтеграція: історія дій і undo

Щоб стек був не просто абстракцією, давайте вбудуємо його в маленький фрагмент нашого зростаючого консольного застосунку. Уявімо, що ми ведемо список книг або задач і хочемо зберігати історію дій, щоб мати можливість «відкотити» останню дію без складної магії.

Ми не будемо робити повноцінний undo зі складним станом — нам достатньо показати, що стек природно зберігає історію, а pop із порожнього стека — це нормальний сценарій («відкочувати нічого»).

Зробимо дію як рядок: на цьому етапі нам не потрібно ускладнювати типи.

import Foundation

struct LibraryActions {
    private var history = Stack<String>()

    mutating func record(_ action: String) {
        history.push(action)
    }

    mutating func undoLastAction() -> String? {
        return history.pop()
    }
}

Тепер подивимося, як поводиться undo, коли дій немає:

import Foundation

var actions = LibraryActions()

let undone1 = actions.undoLastAction()
print(undone1 as Any) // nil

actions.record("Додали книгу: Swift для початківців")
actions.record("Видалили книгу: Старий довідник")

print(actions.undoLastAction() as Any) // Optional("Видалили книгу: Старий довідник")
print(actions.undoLastAction() as Any) // Optional("Додали книгу: Swift для початківців")
print(actions.undoLastAction() as Any) // nil

Зверніть увагу на останній рядок. Це і є той самий граничний випадок: після того як історія закінчилася, undo знову повертає nil, а не падає і не «відкочує» щось випадкове.

І це не дрібниця. Це ознака того, що ви проєктуєте API так, щоб він був передбачуваним навіть у «порожніх» ситуаціях, а реальний користувач і реальний застосунок найчастіше потрапляють саме в такі ситуації.

8. Типові помилки під час роботи з інваріантами та порожнім стеком

Помилка №1: реалізація pop() через removeLast() за допустимої порожнечі.
Коли ви робите removeLast(), ви не «дістаєте елемент», а заявляєте: «елемент точно є, інакше можна падати». Якщо за змістом порожній стек — нормальний стан, такий код перетворює звичайну ситуацію на збій. Для стека з м’яким контрактом використовуйте popLast(), бо він повертає nil на порожньому масиві й тим самим чесно відображає реальність.

Помилка №2: приховувати порожнечу через !.
Іноді пишуть items.last! або items.popLast()! і думають: «ну я ж майже впевнений, що там щось є». Проблема в тому, що «майже впевнений» — не частина контракту. На практиці це призводить до рідкісних збоїв, які найважче налагоджувати: вони трапляються не завжди, а лише іноді — саме у користувача.

Помилка №3: руйнувати інваріант, роблячи внутрішнє сховище публічним.
Якщо items доступний ззовні, будь-який код може вставити елемент на початок, видалити із середини, відсортувати масив або зробити removeAll(). Після цього ваш стек зовні ще компілюється, але його поведінка перестає бути поведінкою стека. Інваріант «верх = кінець масиву» має бути захищений через private (або хоча б через дуже обережний fileprivate, якщо ви розширюєте API в extension).

Помилка №4: плутати peek і pop.
Дуже часта логічна помилка: реалізувати peek через pop() і потім «повертати назад» елемент або просто забути повернути. У підсумку «перегляд вершини» починає змінювати контейнер. Правильна ментальна модель така: peek — чисте читання, pop — читання плюс видалення.

Помилка №5: не зафіксувати домовленість «верх = кінець масиву» й випадково написати операції «з початку».
Якщо в одному місці ви робите append/popLast, а в іншому раптом insert(at: 0)/removeFirst, стек стає внутрішньо суперечливим. Він може «якось працювати» на простих прикладах, але рано чи пізно порядок LIFO зламається. Інваріант має бути єдиним і дотримуватися в усіх методах.