Инварианты и граничные случаи: 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() // crash, если 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 сломается. Инвариант должен быть единым и соблюдаться во всех методах.

1

Задача

Swift SELF, 44 уровень, 0 лекция

Недоступна

Склад табличек

Склад табличек

Открыть

1

Задача

Swift SELF, 44 уровень, 0 лекция

Недоступна

Камера хранения

Камера хранения

Открыть

1

Задача

Swift SELF, 44 уровень, 0 лекция

Недоступна

Инкассация монет

Инкассация монет

Открыть

1

Задача

Swift SELF, 44 уровень, 0 лекция

Недоступна

Проверка инвариантов

Проверка инвариантов

Открыть