🟢 Junior Level

Stack (Стек) — структура данных по принципу LIFO (Last In, First Out).

Простая аналогия: Стопка тарелок. Кладёте сверху, берёте сверху.

Зачем нужен LIFO: последний добавленный элемент — самый актуальный. Примеры: отмена действий (Ctrl+Z), вызовы методов (call stack), разбор скобок, DFS (обход графа в глубину).

Операции:

• push(e) — положить наверх
• pop() — взять сверху
• peek() — посмотреть верхний

// ❌ Не используйте java.util.Stack
Stack<String> stack = new Stack<>();  // Устарел!

// ✅ Используйте ArrayDeque
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.pop();  // → "B" (последний вошёл, первый вышел)

---

🟡 Middle Level

Почему java.util.Stack плох

// Stack наследуется от Vector!
public class Stack<E> extends Vector<E> { ... }

// Проблемы:
// 1. Все методы synchronized → медленно
// 2. Можно вызвать get(0), add(0, e) → нарушение LIFO
// 3. Наследование от Vector = legacy

Правильная альтернатива: ArrayDeque

// ✅ ArrayDeque — быстрый, без синхронизации
Deque<String> stack = new ArrayDeque<>();

stack.push("A");      // Добавляем
stack.push("B");
String top = stack.peek();  // "B" — посмотрели
String popped = stack.pop(); // "B" — забрали

// Исключения:
// pop() на пустом → NoSuchElementException
// peek() на пустом → null

Сравнение

	Stack	ArrayDeque	LinkedList
push/pop	O(1)	O(1)	O(1)
Синхронизация	Да	Нет	Нет
Память	Средняя	Мало	Много
Можно get(index)	❌ Да (плохо! get(index) позволяет обращаться к элементам не через вершину стека, нарушая LIFO-семантику. Клиент кода может случайно использовать стек как обычный список)	❌ Нет	❌ Нет

Use Cases

// 1. Undo/Redo
Deque<Action> undo = new ArrayDeque<>();
undo.push(action);
Action last = undo.pop();

// 2. Проверка скобок
Deque<Character> stack = new ArrayDeque<>();
for (char c : expression.toCharArray()) {
    if (c == '(') stack.push(c);
    if (c == ')') stack.pop();
}

// 3. DFS (обход в глубину)
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);

---

🔴 Senior Level

Когда НЕ использовать стек

1. Если нужен доступ к произвольному элементу — возьмите List
2. Если обработка по порядку FIFO — возьмите Queue/ArrayDeque
3. Если обход графа в ширину (BFS) — очередь, не стек

LSP Violation

LSP (Liskov Substitution Principle) — подкласс должен быть заменяем базовым классом. Stack extends Vector нарушает это: Vector позволяет get(index), что ломает LIFO-семантику стека.

Stack extends Vector
  → Stack "является" списком
  → Но можно вставить в середину: stack.add(0, x)
  → Это нарушает инкапсуляцию стека!
  
ArrayDeque implements Deque
  → Доступ только через push/pop/peek
  → Нельзя нарушить LIFO семантику

Exception Contracts

// java.util.Stack:
stack.pop();        // → EmptyStackException

// ArrayDeque:
deque.pop();        // → NoSuchElementException

// При рефакторинге: ловите правильный тип!

Concurrency

// Если нужен thread-safe стек:

// ❌ Stack (медленный, coarse-grained lock)
Stack<String> stack = new Stack<>();

// ✅ ConcurrentLinkedDeque (lock-free)
Deque<String> stack = new ConcurrentLinkedDeque<>();

// ✅ synchronized Deque
Deque<String> stack = Collections.synchronizedDeque(new ArrayDeque<>());

Production Experience

Реальный сценарий: Stack → ArrayDeque

• Парсер выражений: Stack
• Lock contention: 60% времени
• Решение: ArrayDeque
• Результат: +250% throughput

(По данным внутренних бенчмарков. Ваши результаты будут зависеть от нагрузки, JVM и CPU.)

Best Practices

1. НЕ используйте java.util.Stack
2. ArrayDeque — для стека в 99% случаев
3. ConcurrentLinkedDeque — для thread-safe
4. Deque интерфейс в сигнатуре, не реализация
5. push/pop/peek — стандартные методы
6. Наследование от Vector = architectural mistake

Резюме для Senior

• Stack = legacy, extends Vector, synchronized
• ArrayDeque = правильная замена (быстрее, меньше памяти)
• LSP Violation = Stack можно использовать как список
• Lock-free = ConcurrentLinkedDeque для concurrency
• Исключения = EmptyStackException vs NoSuchElementException
• Никогда не используйте java.util.Stack в новом коде

---

🎯 Шпаргалка для интервью

Обязательно знать:

• Stack = LIFO (Last In, First Out), push/pop/peek — основные операции
• java.util.Stack устарел — наследуется от Vector, все методы synchronized, LSP violation
• ArrayDeque — правильная замена для стека в 99% случаев (быстрее, меньше памяти, нет синхронизации)
• LSP Violation: Stack extends Vector → можно вызвать get(index), что нарушает LIFO-семантику
• Exception контракты: Stack.pop() → EmptyStackException, ArrayDeque.pop() → NoSuchElementException
• Use Cases: Undo/Redo, call stack, проверка скобок, DFS (обход в глубину)
• Thread-safe: ConcurrentLinkedDeque (lock-free) или Collections.synchronizedDeque
• Реальный кейс: замена Stack → ArrayDeque дала +250% throughput в парсере

Частые уточняющие вопросы:

• Почему java.util.Stack плох? — Наследуется от Vector: synchronized (медленно) + можно нарушить LIFO через get(index)
• Чем ArrayDeque лучше Stack? — Нет синхронизации, меньше памяти, нельзя нарушить LIFO-семантику
• Как сделать thread-safe стек? — ConcurrentLinkedDeque (lock-free) или Collections.synchronizedDeque(new ArrayDeque<>())
• Когда НЕ использовать стек? — Если нужен доступ к произвольному элементу (List) или FIFO обработка (Queue)

Красные флаги (НЕ говорить):

• ❌ “java.util.Stack — нормальный выбор” — это legacy, используйте ArrayDeque
• ❌ “Stack полностью инкапсулирует LIFO” — нет, можно вызвать get(index) через наследование от Vector
• ❌ “Synchronized = thread-safe стек” — coarse-grained lock убивает параллелизм, используйте lock-free
• ❌ “Stack и Queue взаимозаменяемы” — LIFO vs FIFO, разные семантики

Связанные темы:

• [[Что такое Vector и чем он отличается от ArrayList]]
• [[Что такое Queue и какие реализации существуют]]
• [[Что такое Deque]]
• [[Какие основные интерфейсы Collection Framework]]