Какая сложность операции push в Stack?

Сложность операции push в Stack

O(1) в среднем случае, иногда O(n) при расширении массива.

Как работает Stack

Stack в Java реализован через расширяющийся массив (как ArrayList):

public class Stack<E> extends Vector<E> {
    public E push(E item) {
        addElement(item);  // Добавляет в конец массива
        return item;
    }
    
    public synchronized void addElement(Object obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
}

O(1) - обычный случай

Если в массиве есть свободное место:

┌─────────────────────────────────┐
│ [1] [2] [3] [4] [ ] [ ] [ ]     │  <- есть свободное место
└─────────────────────────────────┘
                    ↑
                  push(5)

┌─────────────────────────────────┐
│ [1] [2] [3] [4] [5] [ ] [ ]     │  <- просто добавляем O(1)
└─────────────────────────────────┘

Просто добавляем элемент в следующую позицию - O(1).

O(n) - редкий случай (при расширении)

Когда массив полностью заполнен, нужно:

1. Выделить новый, больший массив
2. Скопировать все старые элементы
3. Добавить новый элемент

┌─────────────────────┐
│ [1] [2] [3] [4]     │  <- полный массив
└─────────────────────┘

└─> Расширяем в 1.5-2 раза

┌─────────────────────────────────┐
│ [1] [2] [3] [4] [5] [ ] [ ]     │  <- копируем все + новый
└─────────────────────────────────┘

Эта операция O(n), где n - текущее количество элементов.

Амортизированная сложность: O(1)

Хотя иногда push требует O(n), в среднем это O(1):

№   Операция    Стоимость   Амортизированная
────────────────────────────────────────────
1   push(1)      1           1
2   push(2)      1           1
3   push(3)      1           1
4   push(4)      1           1
5   push(5)      4 (расширение)  1
6   push(6)      1           1
...

Средняя стоимость всё ещё O(1) благодаря экспоненциальному расширению.

Stack vs LinkedList

// Stack (через Vector/ArrayList)
push():  O(1) в среднем, O(n) редко при расширении
pop():   O(1)
peek():  O(1)

// LinkedList Stack
push():  O(1) всегда
pop():   O(1)
peek():  O(1)

LinkedList не требует расширения, но занимает больше памяти.

Практический пример

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < 1000; i++) {
    stack.push(i);  // Обычно O(1), редко O(n) при расширении
}

// Амортизированная сложность: O(1) в среднем
// Худший случай одной операции: O(n)
// Общая сложность всех 1000 операций: O(1000) = O(n)

Ответ на собеседовании

"Stack.push() имеет O(1) амортизированную сложность.

Обычно это просто добавление элемента в конец массива - O(1).

Однако, когда массив заполняется полностью, нужно расширить массив и скопировать все элементы - это O(n).

Такие редкие O(n) операции происходят редко (экспоненциальное расширение), поэтому амортизированная средняя сложность всё ещё O(1)."

Сравнение операций в Stack

Стратегия расширения

// Для оптимизации, Stack расширяется при превышении capacity
protected int capacityIncrement;

// Если capacityIncrement = 0:
// Новый размер = старый * 2 (удвоение)

// Если capacityIncrement > 0:
// Новый размер = старый + capacityIncrement

Удвоение массива даёт лучшую амортизированную сложность O(1).