Стек

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

Стек — структура данных, работающая по принципу LIFO (last in, first out): последний пришедший элемент уходит первым. Стек хранит один указатель — вершину (top), и все операции выполняются только с ней.

Аналогия. Стопка тарелок: положить можно только сверху, взять — тоже только сверху. До нижней тарелки не добраться, пока не снимешь все, что над ней.

Операции стека:

Все четыре операции выполняются за O(1) — на размер стека они не зависят. В этом и смысл стека: быстрый доступ ровно к одному концу.

Реализация на односвязном списке

Стек проще всего сделать на односвязном списке, где вершина — это head. Почему так: добавление и удаление в начало односвязного списка — это O(1), а именно эти две операции и нужны стеку. Узел хранит одно значение:

typedef struct StackNode
{
    int value;
    struct StackNode *next;
} StackNode;

Стек задаётся указателем на вершину:

StackNode *top = NULL;   /* пустой стек */

Пустой стек — это top == NULL.

StackNode *make_node(int value)
{
    StackNode *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;
    }

    node->value = value;
    node->next = NULL;
    return node;
}

push

Положить на вершину — значит добавить новый узел в начало списка:

int push(StackNode **top, int value)
{
    StackNode *node = make_node(value);
    if (node == NULL)
    {
        return 0;          /* не выделилось — стек не изменился */
    }

    node->next = *top;     /* прицепляем старую вершину к новому узлу */
    *top = node;           /* новый узел становится вершиной */
    return 1;
}

Здесь top передаётся как StackNode **, потому что push меняет саму переменную вершины. Порядок двух последних строк важен: сначала новый узел цепляется к старой вершине, потом вершина переставляется. Наоборот — потеряем стек. Возвращаемое значение 1/0 сообщает, удалось ли выделить память.

pop

Снять с вершины — удалить первый узел списка:

int pop(StackNode **top, int *out)
{
    if (*top == NULL)
    {
        return 0;          /* стек пуст — снимать нечего */
    }

    StackNode *node = *top;
    *out = node->value;    /* отдаём значение наружу */
    *top = node->next;     /* вершина опускается на следующий узел */
    free(node);            /* освобождаем снятый узел */
    return 1;
}

Значение выносится через выходной параметр out, а 1/0 сообщает об успехе. Проверка пустоты обязательна: pop на пустом стеке означал бы разыменование NULL. Сначала значение сохраняется, потом вершина переставляется, и только затем free — после освобождения читать узел уже нельзя.

peek и is_empty

peek смотрит вершину, ничего не меняя; is_empty проверяет пустоту:

int peek(const StackNode *top, int *out)
{
    if (top == NULL)
    {
        return 0;
    }

    *out = top->value;
    return 1;
}

int is_empty(const StackNode *top)
{
    return top == NULL;
}

peek принимает const StackNode *: он только читает. Проверка на NULL нужна и здесь.

free_stack

В конце работы стек освобождают целиком, проходя от вершины вниз:

void free_stack(StackNode *top)
{
    while (top != NULL)
    {
        StackNode *next = top->next;   /* СНАЧАЛА сохраняем следующий */
        free(top);
        top = next;
    }
}

Как заменить int на Student

В ЛР 3 стек не используется, но понимание того, как поменять тип данных, пригодится в работе со списками. Чтобы хранить в стеке не число, а структуру, меняют только тип данных в узле:

typedef struct
{
    int id;
    int course;
    double score;
} Student;

typedef struct StudentStackNode
{
    Student data;
    struct StudentStackNode *next;
} StudentStackNode;

Всё остальное — push, pop, peek — остаётся прежним, только int value заменяется на Student data, а сравнения и печать адаптируются под поля структуры. Ключевой момент: значение копируется в узел целиком (node->data = value), а не хранится как указатель на чью-то локальную переменную.

Если вместо копии сохранить в узле указатель на локальную переменную-источник, после выхода из функции этот указатель станет висячим. Поэтому в узел кладут копию структуры — тогда узел остаётся корректным сам по себе, сколько бы ни жил.

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

Стек можно сделать и на массиве — с индексом вершины. У каждого способа свои плюсы и минусы.

Главный минус массива — фиксированный размер и риск переполнения: если положить больше элементов, чем вмещает массив, нужна явная проверка и обработка ошибки. Список растёт по мере надобности и переполняется только при реальной нехватке памяти, но платит лишним указателем в каждом узле. Для учебных задач на указателях список интереснее: он тренирует работу с malloc, NULL и перестановкой ссылок — то, что нужно в ЛР 3.

Применения

Стек появляется во множестве алгоритмов, где важен порядок «последним пришёл — первым обработал»:

• проверка скобок в выражении — каждая открывающая кладётся в стек, каждая закрывающая сверяется с вершиной;
• постфиксные выражения (обратная польская запись) — операнды кладут в стек, операция забирает два верхних;
• откат действий (undo) — стек хранит историю шагов, откат снимает последний;
• обход в глубину (DFS) — стек хранит вершины, к которым нужно вернуться.

Небольшой пример — проверка скобок. Это учебная иллюстрация, не часть ЛР 3. Чтобы не заводить второй тип стека, будем хранить в существующем StackNode (поле int value) код символа: char в C свободно приводится к int и обратно.

#include <stdio.h>

/* push/pop/is_empty/free_stack — из начала статьи, они работают с int */

int check_brackets(const char *s)
{
    StackNode *top = NULL;
    int ok = 1;

    for (int i = 0; s[i] != '\0'; i++)
    {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{')
        {
            if (!push(&top, (int)c))
            {
                ok = 0;
                break;
            }
        }
        else if (c == ')' || c == ']' || c == '}')
        {
            int open;
            if (!pop(&top, &open))
            {
                ok = 0;               /* закрывающая без открывающей */
                break;
            }
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{'))
            {
                ok = 0;               /* скобки не совпадают */
                break;
            }
        }
    }

    if (!is_empty(top))
    {
        ok = 0;                       /* остались незакрытые открывающие */
    }

    free_stack(top);
    return ok;
}

Логика простая: открывающая скобка кладётся на вершину, закрывающая сверяется с вершиной и снимает её. Если на закрывающую не нашлось открывающей, или скобки не совпали, или в конце стек не пуст — выражение некорректно. Обратите внимание: даже при ошибке стек освобождают полностью.

Постфиксное выражение (обратная польская запись) — ещё один классический пример. Выражение 2 3 + означает «сложи 2 и 3». Операнды по очереди кладут в стек; встретив операцию, снимают два верхних операнда, вычисляют результат и кладут его обратно:

выражение: 2 3 + 4 *
шаг 1: push 2        -> стек [2]
шаг 2: push 3        -> стек [2, 3]
шаг 3: операция '+'  -> снять 3 и 2, push 5        -> стек [5]
шаг 4: push 4        -> стек [5, 4]
шаг 5: операция '*'  -> снять 4 и 5, push 20       -> стек [20]

В конце в стеке остаётся один элемент — результат 20. Тот же принцип «сняли верхние, положили результат» лежит в основе стековой машины вычислений. Для ЛР 3 это не нужно, но показывает, насколько естественно стек описывает вложенные вычисления.

Связь с ЛР 3

Стек не входит в варианты ЛР 3. В лабораторной работе студенты строят односвязный, двусвязный или кольцевой список из данных Student/Value, а стек и очередь — структуры на указателях для общего развития. Не подставляйте стек в решение варианта: это не соответствует заданию.

Тем не менее стек полезен именно здесь: его реализация — минимальный, но полный пример работы с узлами, malloc/free, NULL и перестановкой ссылок. Если вы поняли, как push и pop переставляют вершину, вам будет проще разобраться с вставкой и удалением в списках ЛР 3.

Частые ошибки

Что запомнить

1. Стек — LIFO: последним пришёл, первым вышел.
2. Вершина стека — это head односвязного списка; все операции O(1).
3. push цепляет новый узел к вершине, pop снимает и освобождает вершину.
4. peek только читает вершину, is_empty сравнивает top с NULL.
5. В узел кладут копию значения, а не указатель на локальную переменную.
6. Стек на массиве имеет фиксированный размер и может переполниться; список растёт свободно.
7. Стек не входит в варианты ЛР 3, но тренирует те же приёмы работы с указателями.