🟢 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]]