Стек. Физическое представление (массив): одна переменная решает все

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

Что это такое

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

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

Для управления всем стеком хватает одной переменной size. Она играет две роли сразу:

• показывает текущее количество элементов в стеке (глубину);
• служит индексом первой свободной ячейки массива - именно туда ляжет следующий элемент. А сама вершина при этом всегда живет по индексу size - 1.

Push - это "записать в data[size] и увеличить size". Pop - просто size--: элемент даже не стирается физически, он лишь оказывается "за границей" стека и будет перезаписан следующим Push.

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

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

Обратите внимание: интерфейс тот же, что в функциональной спецификации, - меняется только "начинка" структуры:

#include <stdbool.h>

#define POOL_SIZE 100

typedef struct {
    int data[POOL_SIZE]; /* сплошной массив элементов */
    int size;            /* глубина стека и индекс свободной ячейки */
} Stack;

void Create(Stack* s) {
    s->size = 0; /* изначально стек пуст */
}

/* Положить элемент на вершину */
bool Push(Stack* s, int val) {
    if (s->size >= POOL_SIZE) return false; /* переполнение! */
    s->data[s->size] = val; /* кладем в свободную ячейку */
    s->size++;
    return true;
}

/* Снять элемент с вершины */
bool Pop(Stack* s) {
    if (s->size == 0) return false; /* стек пуст */
    s->size--; /* просто сдвигаем границу вниз: O(1) */
    return true;
}

/* Посмотреть вершину, не снимая */
int Top(Stack* s) {
    return s->data[s->size - 1];
}

Цена простоты: переполнение

Массив задан раз и навсегда: если элементов станет больше POOL_SIZE, Push вернет ошибку. Это то самое переполнение стека - Stack Overflow, в честь которого назван известный сайт. С аппаратным стеком вызовов вы уже встречали эту проблему в прошлом уроке, а в следующем увидим реализацию, у которой лимита нет вовсе.