Краткий ответ

Удаление первого элемента из Array имеет линейную сложность O(n) относительно текущего числа элементов: оставшиеся элементы должны переместиться на одну позицию к началу. Если повторять такую операцию для всех элементов, суммарная сложность составит O(n²).

Исторический контекст

Массивы традиционно оптимизированы для хранения элементов в непрерывной области памяти и быстрого доступа по индексу. Такая организация делает эффективными обращение к элементу и операции с концом массива, но вставка или удаление в начале требуют сдвига большого диапазона элементов.

В Swift Array сохраняет эту модель, одновременно предоставляя семантику значения и оптимизацию копирования при записи. Для очередей, где часто удаляют элементы с начала, обычно применяют другую структуру данных.

Постановка проблемы

Рассмотрим обработку массива, при которой первый элемент удаляется после каждой итерации:

var values = Array(0..<10_000)

while !values.isEmpty {
    values.removeFirst()
}

На первой итерации перемещается почти весь массив, на следующей — немного меньше, и так далее. Поэтому общее число перемещений пропорционально сумме n + (n - 1) + ... + 1, то есть имеет квадратичный порядок роста.

На больших объёмах данных это может привести к заметным задержкам и лишней нагрузке на память, даже если логика обработки каждого элемента сама по себе постоянна.

Подробное решение

Array хранит элементы последовательно. После удаления первого элемента прежний второй элемент должен стать первым, третий — вторым и так далее. Поэтому стоимость одного removeFirst() зависит от текущего размера массива и равна O(n).

Удаление последнего элемента обычно имеет амортизированную сложность O(1): достаточно уменьшить логический размер массива, не перемещая остальные элементы. Поэтому для стека или обратного обхода можно использовать конец массива.

Для последовательной обработки без физического удаления лучше хранить индекс текущего элемента. Тогда обход будет линейным:

var values = Array(0..<10_000)
var position = 0

while position < values.count {
    let value = values[position]
    _ = value
    position += 1
}

Если нужна именно очередь с эффективным удалением с обоих концов, подходит специализированная двусторонняя очередь, например Deque из Swift Collections. Она лучше соответствует операции удаления с начала, но добавляет зависимость от отдельного пакета и имеет собственные правила доступа.

Можно также поддерживать индекс начала в массиве и периодически уплотнять оставшиеся элементы. Это уменьшает число сдвигов, но усложняет управление памятью и жизненным циклом уже обработанных элементов.

Ситуация из практики

В сетевом обработчике в Array накапливались сообщения, а обработчик удалял их через removeFirst(). На небольших тестовых наборах решение выглядело корректным, но при росте очереди задержка резко увеличивалась из-за повторяющихся сдвигов.

Вариант с ArraySlice позволил быстро перемещать логическую границу начала, но мог удерживать исходное хранилище массива дольше ожидаемого. Полное копирование оставшихся элементов периодически освобождало старое хранилище, однако создавало дополнительные расходы при каждом уплотнении.

Для постоянной очереди был выбран Deque: он предоставляет подходящую модель данных и эффективные операции с обоих концов. Результат — линейная обработка входного потока вместо квадратичного поведения при последовательном удалении из начала.

Что кандидаты часто упускают

Всегда ли удаление последнего элемента у Array имеет строго O(1)?

Обычно говорят об амортизированной сложности O(1). В отдельных операциях могут возникнуть перераспределение хранилища или действия, связанные с управлением памятью, поэтому строгая стоимость каждой конкретной операции не обязана быть постоянной.
Ускорит ли ситуацию передача массива в функцию?

Нет. Передача Array сама по себе обычно использует оптимизацию копирования при записи, но алгоритмическая стоимость removeFirst() не меняется. Пока массив изменяется, Swift обеспечивает необходимое уникальное хранилище, а сдвиг оставшихся элементов всё равно требуется.
Можно ли заменить удаление на хранение индекса и затем безопасно изменить массив?

Да, если индекс используется только для чтения и массив не мутирует так, чтобы нарушить его валидность. На практике безопаснее сначала завершить обход или явно контролировать границы, потому что мутация коллекции может сделать ранее сохранённые индексы недействительными. Такой подход эффективен, когда элементы не требуется физически удалять немедленно.