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

Что такое стек в программировании?

В программировании стек (stack) — это абстрактный тип данных, который работает по принципу LIFO (Last In, First Out — «последним пришел, первым вышел»). Это означает, что элемент, добавленный последним, будет удалён первым. Визуально стек можно представить как стопку тарелок: вы кладёте тарелки одну на другую, и чтобы взять нижнюю, нужно сначала снять верхние.

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

• push() (добавление): Помещает новый элемент на вершину стека.
• pop() (удаление): Удаляет элемент с вершины стека и возвращает его.
• peek() или top() (просмотр): Возвращает значение элемента на вершине стека, не удаляя его.
• isEmpty() (проверка на пустоту): Проверяет, пуст ли стек.

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

Стек можно реализовать на основе массива или связного списка. Вот пример простейшей реализации на Java с использованием массива:

public class ArrayStack<T> {
    private Object[] elements;
    private int top;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.top = -1; // Стек пуст
    }

    public void push(T item) {
        if (top == capacity - 1) {
            throw new RuntimeException("Стек переполнен");
        }
        elements[++top] = item;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Стек пуст");
        }
        return (T) elements[top--];
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Стек пуст");
        }
        return (T) elements[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

Где используется стек в Android-разработке?

1. Управление активностями (Activity Back Stack). Это ключевая концепция. Когда пользователь переходит из ActivityA в ActivityB, система помещает ActivityA в стек (Back Stack). Нажатие кнопки «Назад» (pop) удаляет текущую активность (ActivityB) из вершины стека, возвращая пользователя к предыдущей (ActivityA). Управление этим стеком осуществляется через Task и Intent с флагами (FLAG_ACTIVITY_NEW_TASK, FLAG_ACTIVITY_CLEAR_TOP и т.д.).

2. Стек вызовов (Call Stack). Во время выполнения программы каждый вызов метода помещает в стек вызовов новый фрейм (кадр), содержащий локальные переменные и адрес возврата. Когда метод завершается, его фрейм извлекается из стека, и управление возвращается в вызывающий метод. Именно по стеку вызовов строится трассировка стека (stack trace) при исключениях (Exception), что помогает в отладке.

3. Управление фрагментами (Fragment Back Stack). При использовании FragmentManager и FragmentTransaction мы можем добавлять транзакции в стек вызовов (addToBackStack(null)). Это позволяет пользователю навигацией «Назад» возвращаться к предыдущему состоянию интерфейса фрагментов.

4. Разбор выражений и синтаксический анализ. Стек используется для проверки корректности скобок в выражении, преобразования инфиксной записи в постфиксную (польскую нотацию) и её вычисления.

5. Алгоритмы обхода графов (Depth-First Search — DFS). Стек идеально подходит для реализации этого алгоритма, так как мы «идём вглубь», а при необходимости откатываемся назад.

6. Отмена действий (Undo). Во многих приложениях последовательность действий пользователя сохраняется в стеке, что позволяет их отменять в обратном порядке.

Важные технические аспекты

• Переполнение стека (Stack Overflow). Возникает, если глубина рекурсивных вызовов или количество фреймов превышает лимит, выделенный системой для стека вызовов. В Android это приводит к StackOverflowError.
• Стек в многопоточности. Каждый поток в приложении имеет свой собственный стек вызовов, но разделяет общую память кучи (heap) с другими потоками.
• Стек vs. Куча (Heap). Важно не путать структуру данных «стек» с областью памяти «стек». Область памяти стек используется для хранения примитивов и ссылок на объекты в рамках вызова метода, а также фреймов вызовов. Сами объекты создаются в куче.

Таким образом, стек — это не просто академическая структура данных, а фундаментальный механизм, глубоко интегрированный в работу Android Runtime (ART) и саму логику построения навигации приложения. Понимание его работы критически важно для создания корректных переходов между экранами, обработки глубоких ссылок (deep linking), отладки сложных ошибок и написания эффективных алгоритмов.