Стек. Физическое представление (динамические объекты): связный список узлов

Модуль "Стек" • урок 5 из 8 • ~7 минут

Стек. Физическое представление (динамические объекты): что это такое

В прошлом уроке стек жил в сплошном массиве, и лимит был зашит в код. Теперь пойдем другим путем: будем выделять память под каждый элемент отдельно - в куче (heap). Элементы окажутся разбросаны по памяти, поэтому их нужно связать: каждый узел держит указатель на своего "соседа снизу". Получается однонаправленный связный список, у которого голова цепочки и есть вершина стека.

Зачем это нужно

Главный выигрыш - исчезает Stack Overflow из-за жестко заданного размера. Стек на динамических объектах может расти, пока в оперативной памяти есть место. Это важно для алгоритмов, у которых глубина вложенности заранее непредсказуема: обход глубоких деревьев, разбор выражений, длинные цепочки отмены действий.

Как организовано

Понадобятся две структуры:

• Узел Item: полезные данные data + указатель prev на элемент, положенный в стек до него (то есть лежащий ниже).
• Сам стек: единственный указатель top на вершину (и, для удобства, счетчик size). Пустой стек - это top == NULL: нулевой указатель играет роль дна.

Операции - чистая работа с указателями:

• Push: выделить память под новый узел, записать в его prev текущий top, перенести top на новый узел.
• Pop: запомнить узел-вершину, опустить top на top->prev, освободить память запомненного узла.

Обе операции по-прежнему O(1), но теперь внутри каждой прячется обращение к менеджеру памяти - malloc или free. Это и есть цена свободы: накладные расходы на каждый элемент вместо одного большого массива.

Реализация на C

#include <stdlib.h>
#include <stdbool.h>

/* Узел динамического стека */
typedef struct Item {
    int data;
    struct Item* prev; /* элемент, лежащий ПОД текущим */
} Item;

/* Стек: указатель на вершину и счетчик элементов */
typedef struct {
    Item* top;
    int size;
} Stack;

void Create(Stack* s) {
    s->top = NULL; /* NULL - это дно стека */
    s->size = 0;
}

bool Push(Stack* s, int val) {
    Item* newItem = (Item*)malloc(sizeof(Item));
    if (!newItem) return false; /* память закончилась */

    newItem->data = val;
    newItem->prev = s->top; /* подвязываем к прежней вершине */
    s->top = newItem;       /* новый узел стал вершиной */
    s->size++;
    return true;
}

bool Pop(Stack* s) {
    if (s->size == 0) return false;

    Item* i = s->top;      /* запоминаем узел на удаление */
    s->top = s->top->prev; /* вершина опускается на слой ниже */
    free(i);               /* возвращаем память системе */
    s->size--;
    return true;
}

Обратите внимание на порядок действий в Pop: сначала перенести top, потом free. Освободить узел раньше времени - значит потерять единственную ссылку на остальную часть стека.

Массив или список: что выбрать

• Массив: быстрее на практике (сплошная память, никакого malloc), но размер фиксирован.
• Связный список: нет лимита размера, но каждый Push и Pop ходит к менеджеру памяти, а узлы тратят место на указатели.

Интересный факт: из двух стеков можно собрать очередь - элементы переливаются во вспомогательный стек и обратно, дважды инвертируясь и восстанавливая порядок. Эту задачу мы разберем в теме "Очередь и дек".