Что такое стек?

# Что такое стек (Stack)

Стек — это важное понятие в Java, которое может означать разные вещи в зависимости от контекста.

1. Стек как структура данных

Стек (Stack) — это коллекция с принципом LIFO (Last In, First Out): последний вошедший, первый вышедший.

Аналогия

Стопка тарелок:
- Кладёшь тарелку сверху (PUSH)
- Берёшь тарелку сверху (POP)
- Тарелка, которую положил последняя, берётся первая

Основные операции

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

// PUSH: добавить элемент на вершину
stack.push(10);   // [10]
stack.push(20);   // [10, 20]
stack.push(30);   // [10, 20, 30]

// PEEK: посмотреть верхний элемент БЕЗ удаления
int top = stack.peek();  // 30 (стек остаётся [10, 20, 30])

// POP: удалить и вернуть верхний элемент
int popped = stack.pop();  // 30 (стек становится [10, 20])

// EMPTY: проверить, пуст ли стек
boolean isEmpty = stack.empty();  // false

// SEARCH: найти позицию элемента с вершины
int pos = stack.search(10);  // 2 (10 находится на позиции 2 от вершины)

Реализация стека

public class MyStack<T> {
    private java.util.List<T> items = new java.util.ArrayList<>();
    
    public void push(T item) {
        items.add(item);
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return items.remove(items.size() - 1);
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return items.get(items.size() - 1);
    }
    
    public boolean isEmpty() {
        return items.isEmpty();
    }
    
    public int size() {
        return items.size();
    }
}

Примеры использования стека

1. Проверка сбалансированных скобок

public boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (stack.isEmpty()) return false;
            
            char open = stack.pop();
            if ((c == ')' && open != '(') ||
                (c == '}' && open != '{') ||
                (c == ']' && open != '[')) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

// Примеры
isBalanced("(())");      // true
isBalanced("({[]})");    // true
isBalanced("((");        // false
isBalanced(")(");        // false

2. Обратный порядок строки

public String reverseString(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        stack.push(c);
    }
    
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    
    return result.toString();
}

// Пример
reverseString("hello");  // "olleh"

3. Вычисление выражений (Postfix notation)

public int evalPostfix(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    
    for (String token : tokens) {
        if (token.matches("-?\\d+")) {
            stack.push(Integer.parseInt(token));
        } else {
            int b = stack.pop();
            int a = stack.pop();
            
            switch (token) {
                case "+" -> stack.push(a + b);
                case "-" -> stack.push(a - b);
                case "*" -> stack.push(a * b);
                case "/" -> stack.push(a / b);
            }
        }
    }
    
    return stack.peek();
}

// Пример
evalPostfix(new String[]{"2", "1", "+", "3", "*"});  // (2 + 1) * 3 = 9

2. Стек вызовов (Call Stack)

Это более важное понятие в контексте многопоточности и выполнения программы.

Что такое стек вызовов

Каждый поток имеет свой стек вызовов (call stack), который отслеживает последовательность вызовов функций.

public class CallStackExample {
    public static void main(String[] args) {
        methodA();
    }
    
    public static void methodA() {
        System.out.println("A start");
        methodB();
        System.out.println("A end");
    }
    
    public static void methodB() {
        System.out.println("B start");
        methodC();
        System.out.println("B end");
    }
    
    public static void methodC() {
        System.out.println("C start");
        System.out.println("C end");
    }
}

Стек вызовов при выполнении:

1. main() вызывает methodA()
   Call Stack: [main]
              [methodA]

2. methodA() вызывает methodB()
   Call Stack: [main]
              [methodA]
              [methodB]

3. methodB() вызывает methodC()
   Call Stack: [main]
              [methodA]
              [methodB]
              [methodC]  ← вершина стека

4. methodC() завершается
   Call Stack: [main]
              [methodA]
              [methodB]

5. methodB() завершается
   Call Stack: [main]
              [methodA]

6. methodA() завершается
   Call Stack: [main]

Stack Trace и StackOverflowError

// Stack trace показывает стек вызовов
public void printStackTrace() {
    try {
        riskyOperation();
    } catch (Exception e) {
        e.printStackTrace();  // Выведет стек вызовов до ошибки
    }
}

// StackOverflowError возникает, когда стек переполняется
public void infiniteRecursion() {
    infiniteRecursion();  // Вызывает сам себя
    // Call Stack: [infiniteRecursion]
    //             [infiniteRecursion]
    //             [infiniteRecursion]
    //             [infiniteRecursion]
    //             ... (пока не переполнится)
    // StackOverflowError!
}

Локальные переменные в стеке

Каждый вызов метода имеет свой frame в стеке с локальными переменными:

public class StackMemory {
    public void methodA() {
        int x = 10;  // x находится в frame methodA
        methodB();
    }
    
    public void methodB() {
        int y = 20;  // y находится в frame methodB
        int z = 30;  // z находится в frame methodB
        // x не видна здесь
    }
}

Структура стека в памяти:

┌─────────────────┐
│  Frame methodB  │ ← вершина стека
│  y = 20         │
│  z = 30         │
├─────────────────┤
│  Frame methodA  │
│  x = 10         │
├─────────────────┤
│  Frame main     │
└─────────────────┘
   ↑ стек растёт вверх

Многопоточность и стеки

Каждый поток имеет свой отдельный стек вызовов:

public class ThreadStackExample {
    public static void main(String[] args) {
        Thread t1 = new Thread(() -> method1());
        Thread t2 = new Thread(() -> method2());
        
        t1.start();
        t2.start();
        // У t1 и t2 разные стеки вызовов
        // Они не мешают друг другу
    }
    
    public static void method1() {
        // Stack t1: [main] -> [t1.run] -> [method1]
    }
    
    public static void method2() {
        // Stack t2: [main] -> [t2.run] -> [method2]
    }
}

3. Память: Heap vs Stack

Стек (Stack)

- БЫСТРЫЙ доступ
- Автоматическое освобождение памяти
- Ограниченный размер (может быть StackOverflowError)
- Локальные переменные и references
- LIFO порядок

Куча (Heap)

- МЕДЛЕННЕЕ доступ
- Ручное управление (или GC)
- Большой размер
- Объекты
- Нет порядка доступа

Пример

public void example() {
    int age = 30;              // Stack: примитив
    String name = "John";      // Stack: reference, Heap: "John" string
    Person person = new Person(); // Stack: reference, Heap: Person object
    
    // Стек:        Куча:
    // age: 30
    // name: ─────→ "John"
    // person: ────→ {name, age}
}

Размер стека и StackOverflowError

// Проверить размер стека
public class StackSize {
    public static void main(String[] args) {
        // В JVM размер стека по умолчанию:
        // -Xss1m  (1 MB для Linux)
        // -Xss2m  (для Windows)
        
        long maxStackMemory = Runtime.getRuntime().maxMemory();
        System.out.println("Max memory: " + maxStackMemory);
    }
}

// StackOverflowError из-за глубокой рекурсии
public class DeepRecursion {
    public static void recursive(int depth) {
        System.out.println(depth);
        if (depth < 10000) {
            recursive(depth + 1);  // Может привести к StackOverflowError
        }
    }
}

Итог

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

• LIFO принцип
• Используется для проверки скобок, вычисления выражений, обхода графов
• Java: Stack<T> класс

Стек вызовов:

• Отслеживает вложенность вызовов методов
• Каждый поток имеет свой стек
• Локальные переменные хранятся на стеке
• StackOverflowError возникает при переполнении

Память:

• Стек быстрее, но ограничен
• Куча медленнее, но больше
• Примитивы и references → Стек
• Объекты → Куча (reference на стеке указывает на объект на куче)