Стек (Stack): анимация и код | Деление на ноль

Визуализация

Сценарий: Заполнение и опустошение

Сценарий:

Легенда цветов

push - кладем на вершину pop и peek - читаем вершину свободная ячейка

Операций 6

Нажмите "Пуск" или листайте по шагам.

Размер стека: 0 Операций: 0 Шаг: 0 / 0 Сложность по времени: -

Как работает стек

Идея структуры: Стек работает по принципу LIFO (Last In, First Out - последним пришел, первым ушел). Представьте стопку тарелок: положить тарелку можно только на самый верх и взять тоже только верхнюю.

Стек: элемент кладут на вершину операцией push и снимают оттуда операцией pop, указатель top ходит по краю массива (Stack)

Базовые операции:

Push (положить в стек): добавление элемента на вершину стека (top).
Pop (снять со стека): извлечение самого верхнего элемента.
Peek / Top (просмотр вершины): чтение значения с вершины без его удаления из стека.

Где применяется:

Стек вызовов (Call Stack): отслеживание активных функций в программировании (кто кого вызвал).
Отмена действий (Undo): каждое действие кладется в стек, при отмене - снимается с вершины.
Парсинг: проверка правильности скобочных последовательностей или вычисление выражений в обратной польской записи.
Алгоритм поиска в глубину (DFS) в графах и деревьях.

Зеркальная структура. Если брать элементы не с того конца, куда кладем, а с противоположного, получится очередь с принципом FIFO. Обе операции сразу с двух концов умеет дек.

Синонимы названия: Stack, LIFO-стек, магазинная память.

Сложность

Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.

По времени

У стека все три операции не зависят от размера: работа идет только с вершиной, а до остальных элементов алгоритм не добирается. Лейбл "Сложность по времени" под визуализацией показывает оценку той операции, которая только что завершилась.

Операция	Сложность	Комментарий
Добавление (Push)	O(1)	Запись в следующую свободную ячейку `top`.
Удаление (Pop)	O(1)	Извлечение значения по индексу `top`.
Просмотр (Peek)	O(1)	Чтение значения по индексу `top`.

По памяти

Характеристика	Оценка	Комментарий
Затраты по памяти	O(n)	Для хранения `n` элементов требуется соответствующий массив.

Свойства

Свойство	Значение	Комментарий
Принцип работы	LIFO	Последним пришел - первым ушел. Все операции происходят строго на вершине стека (top).
Доступ к элементам	Ограничен	Доступен только верхний элемент. Чтение и изменение элементов внутри стека запрещены.
Эффективность	O(1)	Добавление (push), удаление (pop) и просмотр вершины (peek) выполняются за константное время.

Примеры реализации: Стек (Stack)

Код на C (массив)

#include <stdio.h>

#define MAX_SIZE 100 // Максимальная вместимость стека

int stack[MAX_SIZE]; // Статический массив для элементов
int top = -1;        // Индекс вершины. Изначально -1 (стек пуст)

// Добавление элемента на вершину стека (Push)
void push(int item) {
    // Защита от переполнения: нельзя добавить, если массив заполнен
    if (top >= MAX_SIZE - 1) {
        printf("Ошибка: переполнение стека\n");
        return;
    }
    top++;             // Сдвигаем индекс вершины вверх
    stack[top] = item; // Записываем новое значение
}

// Извлечение элемента с вершины стека (Pop)
int pop() {
    // Защита от извлечения: нельзя взять из пустого стека
    if (top < 0) {
        printf("Ошибка: стек пуст\n");
        return -1;
    }
    int item = stack[top]; // Запоминаем верхнее значение
    top--;                 // Сдвигаем индекс вершины вниз
    return item;
}

// Просмотр верхнего элемента без извлечения (Peek)
int peek() {
    if (top < 0) return -1;
    return stack[top];
}

Код на Python (list)

# В Python встроенные списки (list) реализованы как динамические массивы.
# Добавление в конец (append) и удаление с конца (pop) работают за O(1),
# поэтому они идеально подходят для использования в качестве стека.

# Создаем пустой стек
stack = []

# Положить на вершину стека (Push)
stack.append(10) # Стек: [10]
stack.append(20) # Стек: [10, 20]

# Снять с вершины стека (Pop)
# Метод pop() без аргументов удаляет и возвращает последний элемент
item = stack.pop() # Вернет 20, стек станет: [10]

# Просмотр вершины без извлечения (Peek)
if stack: # Проверка на пустоту
    top_item = stack[-1] # -1 означает последний элемент списка

Код на JavaScript (Array)

// Встроенный массив (Array) в JavaScript уже имеет идеальные методы
// для работы в качестве стека, так как push и pop работают с концом массива O(1).
// Создадим класс-обертку, чтобы ограничить доступ (инкапсуляция).
class Stack {
    constructor() {
        this.items = []; // Внутреннее хранилище
    }

    // Добавление элемента на вершину (Push)
    push(element) {
        this.items.push(element); // Добавляем в конец массива
    }

    // Извлечение элемента с вершины (Pop)
    pop() {
        if (this.items.length === 0) return null; // Защита от пустого стека
        return this.items.pop(); // Удаляем и возвращаем последний элемент
    }

    // Чтение значения вершины без удаления (Peek)
    peek() {
        if (this.items.length === 0) return null;
        return this.items[this.items.length - 1]; // Возвращаем последний элемент
    }

    // Вспомогательный метод для проверки на пустоту
    isEmpty() {
        return this.items.length === 0;
    }
}

Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про стек и принцип LIFO - с подробной теорией, задачами и проверочными вопросами.