Стек на массиве¶

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

¶Основные характеристики

Стек на массиве представляет собой абстрактный тип данных (ADT), поддерживающий две основные операции: push (добавление элемента на вершину) и pop (удаление элемента с вершины). Дополнительно часто реализуется операция peek (или top) для чтения значения вершины без её удаления. В реализации на массиве все эти операции выполняются за константное время O(1) при условии, что массив не требует перераспределения памяти.

Ключевые параметры реализации:

• Размерность: фиксированный (статический) или динамический массив.
• Указатель вершины: целочисленная переменная (часто называется top или sp), хранящая индекс последнего добавленного элемента. Изначально устанавливается в −1 (пустой стек).
• Ёмкость: максимальное количество элементов, которое может вместить массив без перераспределения.

¶Реализация

¶Статический стек на массиве

В статической реализации стек создаётся с заранее заданным максимальным размером (например, MAX_SIZE). Массив объявляется фиксированной длины, а указатель вершины инициализируется значением −1.

Псевдокод (C-подобный): ```c

¶define MAX_SIZE 100

int stack[MAX_SIZE]; int top = -1;

void push(int value) { if (top == MAX_SIZE - 1) { // Обработка переполнения (overflow) return; } stack[++top] = value; }

int pop() { if (top == -1) { // Обработка пустого стека (underflow) return -1; // или выброс исключения } return stack[top--]; }

int peek() { if (top == -1) return -1; return stack[top]; } ```

Особенности:

• Простота и предсказуемость.
• Риск переполнения (overflow) при превышении MAX_SIZE.
• Неэффективен, если максимальный размер неизвестен или сильно варьируется.

¶Динамический стек на массиве

Динамическая реализация использует массив, который может увеличиваться (реже — уменьшаться) при необходимости. Обычно применяется стратегия удвоения размера при заполнении (амортизированная сложность O(1) на операцию push).

Псевдокод (C++-подобный): ```cpp class DynamicStack { private: int* arr; int capacity; int top;

public: DynamicStack(int initialCapacity = 10) { arr = new int[initialCapacity]; capacity = initialCapacity; top = -1; }

void push(int value) { if (top == capacity - 1) { resize(capacity * 2); } arr[++top] = value; }

int pop() { if (top == -1) throw "Stack empty"; return arr[top--]; }

private: void resize(int newCapacity) { int* newArr = new int[newCapacity]; for (int i = 0; i <= top; ++i) { newArr[i] = arr[i]; } delete[] arr; arr = newArr; capacity = newCapacity; } }; ```

Особенности:

• Гибкость: стек может расти до размеров доступной памяти.
• Амортизированная сложность push — O(1), хотя в худшем случае (при перераспределении) — O(n).
• Требует управления памятью (в языках без сборщика мусора).

¶Преимущества и недостатки

¶Преимущества

• Быстрый доступ: операции push, pop, peek выполняются за O(1) без накладных расходов на указатели (как в связном списке).
• Локальность данных: элементы хранятся в непрерывном блоке памяти, что улучшает кэширование процессора.
• Простота реализации: минимальный код, легко отлаживается.
• Экономия памяти: для хранения n элементов требуется ровно n ячеек (плюс небольшой резерв при динамическом расширении), в отличие от связного списка, где каждый элемент требует дополнительной памяти под указатель.

¶Недостатки

• Ограниченная ёмкость (в статическом варианте): при превышении — потеря данных или аварийное завершение.
• Перераспределение памяти (в динамическом варианте): может вызывать задержки и фрагментацию кучи.
• Неэффективность при частых вставках/удалениях в середину: стек не предназначен для произвольного доступа, но массив сам по себе позволяет вставку по индексу за O(n), что не является его типичным использованием.
• Сложность уменьшения размера: динамический стек обычно не уменьшается автоматически после удаления элементов, что может приводить к избыточному потреблению памяти.

¶Применение

Стек на массиве широко используется в системном и прикладном программировании:

• Вызов функций и управление контекстом: в большинстве языков программирования стек вызовов (call stack) реализован именно на массиве. Каждый вызов функции помещает на стек кадр (frame) с локальными переменными и адресом возврата.
• Обработка выражений: алгоритмы преобразования инфиксной записи в постфиксную (обратная польская нотация) и вычисления арифметических выражений.
• Парсинг и синтаксический анализ: проверка правильности скобочных последовательностей, разбор XML/HTML.
• Алгоритмы на графах: поиск в глубину (DFS) использует стек для хранения вершин.
• Отмена действий (undo): в текстовых редакторах и графических приложениях стек хранит историю изменений.
• Виртуальные машины: стековые машины (например, JVM, .NET CLR) используют стек для хранения операндов и промежуточных результатов.

¶Сравнение с другими реализациями стека

¶Примеры в языках программирования

• C++: std::stack (по умолчанию использует std::deque, но можно задать std::vector как базовый контейнер).
• Java: java.util.Stack (реализован на массиве, унаследован от Vector).
• Python: список (list) используется как стек через методы append() и pop().
• C#: System.Collections.Generic.Stack<T> (внутренне использует массив).
• JavaScript: массив (Array) с методами push() и pop().

¶Интересные факты

• В ранних версиях языка C стек вызовов часто реализовывался аппаратно (регистр SP), но программно — как массив в памяти.
• Алгоритм «решето Эратосфена» можно реализовать с использованием стека на массиве для хранения простых чисел, хотя обычно это неэффективно.
• В некоторых системах реального времени (RTOS) стек задач реализуется как статический массив фиксированного размера, чтобы избежать динамического выделения памяти.

¶Критика и ограничения

Основная критика стека на массиве связана с его негибкостью в статическом варианте: программист должен заранее знать максимальный размер, что в сложных приложениях часто невозможно. Динамическое расширение решает эту проблему, но вносит недетерминированность по времени, что критично для систем реального времени. Кроме того, в языках без автоматического управления памятью (C, C++) требуется явное освобождение ресурсов, что повышает риск утечек.