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

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

Сложность операции pop в Stack составляет O(1) — постоянное время выполнения. Это одно из главных преимуществ структуры данных Stack, и понимание этого критично для оптимизации алгоритмов.

Как устроен Stack в Java

Stack — это структура данных, которая работает по принципу LIFO (Last In, First Out). Элемент, добавленный последним, удаляется первым.

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

// push - добавить элемент в вершину
stack.push(1);  // [1]
stack.push(2);  // [1, 2]
stack.push(3);  // [1, 2, 3] <- вершина здесь

// pop - удалить и вернуть элемент с вершины
Integer top = stack.pop();  // Возвращает 3, stack = [1, 2]
Integer top2 = stack.pop(); // Возвращает 2, stack = [1]

Почему pop имеет сложность O(1)?

В Java Stack реализован на базе ArrayList (или Vector в старых версиях). Вот внутренняя реализация:

public class Stack<E> extends Vector<E> {
    // Удаление с конца массива
    public synchronized E pop() {
        E obj;
        int len = size();
        
        obj = peek();  // Получить последний элемент - O(1)
        removeElementAt(len - 1);  // Удалить с конца - O(1)
        
        return obj;
    }
}

Опасно не требует:

• Поиска элемента - мы знаем, что это последний элемент
• Смещения других элементов (в отличие от удаления из начала)
• Перестраивания структуры

Визуализация работы pop

Массив внутри Stack:
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │  <- индекс = size-1
└───┴───┴───┴───┴───┘
                  ▲
                 top

pop():
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ - │  <- просто уменьшить size, элемент остаётся в памяти
└───┴───┴───┴───┴───┘
                  ▲
              (удаляется)

Время выполнения: O(1)
Почему: просто изменить переменную size (size--)

Сравнение со списком

// Stack - O(1)
Stack<Integer> stack = new Stack<>();
stack.push(1); stack.push(2); stack.push(3);
Integer val = stack.pop();  // O(1) - удаляет с конца

// LinkedList - O(1) также
LinkedList<Integer> list = new LinkedList<>();
list.add(1); list.add(2); list.add(3);
Integer val = list.removeLast();  // O(1) - удаляет с конца

// ArrayList - O(1) с конца, но O(n) с начала
ArrayList<Integer> list = new ArrayList<>();
list.add(1); list.add(2); list.add(3);
Integer val = list.remove(list.size() - 1);  // O(1) - с конца
Integer val2 = list.remove(0);  // O(n) - с начала (нужно сдвинуть всё!)

Почему удаление с конца быстрее, чем с начала?

// Удаление с конца - O(1)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
            ▲
        Удалить
        
Действие: size-- (готово за O(1))

// Удаление с начала - O(n)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
▲
Удалить

Действие: 
┌───┬───┬───┬───┐
│ 2 │ 3 │ 4 │ - │  <- нужно сдвинуть все элементы на одну позицию
└───┴───┴───┴───┘

Это требует O(n) операций

Внутренняя реализация pop

private transient Object[] elementData;
private int elementCount;

public E pop() {
    // 1. Получить индекс верхнего элемента - O(1)
    int topIndex = elementCount - 1;  // Просто вычисление
    
    // 2. Получить значение - O(1)
    E value = (E) elementData[topIndex];
    
    // 3. Удалить ссылку - O(1)
    elementData[topIndex] = null;  // Для garbage collection
    
    // 4. Уменьшить счётчик - O(1)
    elementCount--;  // Просто изменить переменную
    
    return value;
}

Все операции — простые операции над переменными, никаких циклов.

Практический пример: работа со Stack

public class StackOperations {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        
        // push - O(1) в среднем, O(n) при необходимости расширения
        stack.push("First");    // O(1)
        stack.push("Second");   // O(1)
        stack.push("Third");    // O(1)
        
        // Временно сложность: O(1) за элемент = O(n) для n элементов
        
        // pop - ВСЕГДА O(1)
        while (!stack.empty()) {
            String item = stack.pop();  // O(1)
            System.out.println(item);   // Third, Second, First
        }
        
        // Временно сложность: O(n) для извлечения n элементов
    }
}

Вспомогательные операции Stack

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

// Все эти операции O(1):

// 1. peek - просмотр верхнего элемента без удаления
int top = stack.peek();  // 3, O(1)

// 2. empty - проверка, пуст ли стек
boolean isEmpty = stack.empty();  // false, O(1)

// 3. search - поиск позиции элемента
int pos = stack.search(2);  // 2 (от вершины), O(n) - требует поиска

// 4. pop - удаление верхнего элемента
int popped = stack.pop();  // 3, O(1)

Сложность vs Производительность

Хотя pop имеет O(1) сложность, это не означает, что операция очень быстрая:

// O(1) - но всё ещё требует циклировать
for (int i = 0; i < 1_000_000; i++) {
    stack.pop();  // O(1) * 1_000_000 = O(n)
}

// vs O(n) операция, но за один вызов
ArrayList<Integer> list = new ArrayList<>();
list.removeAll(list);  // O(n) - но за один вызов

Сравнение структур данных

Практическое применение

Благодаря O(1) pop, Stack идеален для:

// Валидация скобок
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);  // O(1)
        } else {
            if (stack.empty()) return false;
            char top = stack.pop();  // O(1)
            if (!matches(top, c)) return false;
        }
    }
    return stack.empty();
}
// Общая сложность: O(n)

// Обратный порядок
public void reverseString(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        stack.push(c);  // O(1)
    }
    
    while (!stack.empty()) {
        System.out.print(stack.pop());  // O(1)
    }
}
// Общая сложность: O(n)

Резюме

• Сложность pop: O(1) — постоянное время
• Причина: Stack удаляет элемент с конца без смещения других
• Реализация: просто изменить переменную size
• Важно: O(1) гарантирована, что делает Stack отличным выбором для алгоритмов, требующих быстрого добавления/удаления с одного конца