Для чего нужны Stack?

Для чего нужны Stack?

Stack (стек) — это одна из фундаментальных структур данных в информатике. Давайте разберёмся, что это такое и где его использовать.

Определение и принцип работы

Stack работает по принципу LIFO (Last In, First Out — последним пришёл, первым ушёл). Представьте стопку книг: вы кладёте книгу сверху и берёте книгу сверху.

import java.util.Stack;

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

// push — добавить элемент
stack.push("First");
stack.push("Second");
stack.push("Third");

// pop — удалить и вернуть верхний элемент
String top = stack.pop();  // "Third"

// peek — посмотреть верхний элемент без удаления
String nextTop = stack.peek();  // "Second"

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

Внутреннее устройство Stack в Java

Stack в Java наследуется от Vector (устаревший класс), поэтому лучше использовать Deque:

// Более современный подход
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int value = stack.pop();  // 2

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

1. Обратный порядок (Реверс)

Stack<Integer> stack = new Stack<>();
int[] arr = {1, 2, 3, 4, 5};

for (int num : arr) {
    stack.push(num);
}

while (!stack.empty()) {
    System.out.print(stack.pop() + " ");  // 5 4 3 2 1
}

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

public boolean isBalanced(String expression) {
    Stack<Character> stack = new Stack<>();
    
    for (char ch : expression.toCharArray()) {
        if (ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        } else if (ch == ')' || ch == '}' || ch == ']') {
            if (stack.empty()) return false;
            char top = stack.pop();
            if (!matches(top, ch)) return false;
        }
    }
    
    return stack.empty();
}

private boolean matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

// Использование
isBalanced("({[]})");  // true
isBalanced("({[}])");  // false

3. Вычисление обратной польской нотации (RPN)

public int evaluateRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    
    for (String token : tokens) {
        if (isOperator(token)) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(calculate(a, b, token));
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    
    return stack.pop();
}

private int calculate(int a, int b, String op) {
    return switch(op) {
        case "+" -> a + b;
        case "-" -> a - b;
        case "*" -> a * b;
        case "/" -> a / b;
        default -> 0;
    };
}

4. Отмена операций (Undo)

public class TextEditor {
    private StringBuilder text = new StringBuilder();
    private Stack<String> history = new Stack<>();
    
    public void type(String input) {
        history.push(text.toString());
        text.append(input);
    }
    
    public void undo() {
        if (!history.empty()) {
            text = new StringBuilder(history.pop());
        }
    }
}

5. Обход графа (DFS)

public void depthFirstSearch(Node startNode) {
    Stack<Node> stack = new Stack<>();
    Set<Node> visited = new HashSet<>();
    
    stack.push(startNode);
    
    while (!stack.empty()) {
        Node current = stack.pop();
        
        if (visited.contains(current)) continue;
        visited.add(current);
        
        System.out.println(current.value);
        
        for (Node neighbor : current.neighbors) {
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

6. Парсинг и компиляция

Stack используется в компиляторах для разбора синтаксиса языков, управления вложенностью блоков кода и обработки вызовов функций.

Вызовы функций в Java

Каждый раз, когда функция вызывает другую функцию, создаётся frame в стеке вызовов. Это видно при StackOverflowError при бесконечной рекурсии — стек вызовов переполняется.

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

Operations на Stack имеют O(1) амортизированную сложность: push, pop и peek работают за константное время.

Stack — это мощный инструмент для решения множества задач от реверса данных до сложного парсинга кода.