Создание динамического связанного стека на C: реализация и подводные камни

Большинство новичков полагают, что структуры данных статичны. Это не так. Связанный стек — это динамическая сущность. Он растет и сжимается на лету. Вы не выделяете память заранее. Вы получаете её, когда она нужна. Освобождаете, когда закончили.

В этом примере используются целые числа. Измените typedef int stack_data на float или char, если хотите. Логика останется той же.

Интерфейс

Посмотрите на заголовочный файл. Это контракт.

stack_init настраивает структуру. stack_clear очищает её. stack_empty сообщает, есть ли там что-то осталось. push помещает данные внутрь. pop извлекает их.

Просто. Чисто.

Движок

Исходный файл скрывает внутреннюю начинку.

top указывает на самый новый элемент. NULL означает пустоту.

stack_init просто сбрасывает top в NULL. Готово.

stack_clear извлекает элементы, пока стек не опустеет. Это цикл. Это дешево.

stack_empty проверяет, равен ли top NULL. Возвращает 1, если истинно. 0, если ложно.

stack_push выполняет основную работу.

Он выделяет память. Устанавливает данные. Связывает их со старым верхом. Обновляет top.

stack_pop выполняет процесс в обратном порядке.

Он забирает данные. Перемещает top вниз. Освобождает старый узел. Возвращает значение.

Если стек пуст? Он вернет мусор. Не извлекайте данные из пустого стека.

Скрытие информации

Это ключевой момент.

Вы видите только заголовочный файл. Вы не видите код реализации.

Стек может использовать массивы. Указатели. Файлы. Связный список. Неважно.

Пока интерфейс работает, вам не важно, как он устроен.

Это и есть скрытие информации. Это не просто модное словечко. Это то, как вы создаете программное обеспечение, которое не ломается при изменении внутренней реализации.

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

C не прощает ошибок.

1. Скобки имеют значение. (*p).i не то же самое, что *p.i. В первом случае сначала разыменовывается указатель. Во втором — сначала доступ к члену, затем разыменование. Ошибетесь — получите сбой.
2. Утечки памяти. Никогда не просто присваивайте top = NULL. Вы потеряете все узлы в списке. Вы потеряете данные. Вы потеряете память. Используйте free. Всегда.
3. Подключайте заголовочные файлы. NULL находится в stdio.h. Если вы забудете его подключить, ваш код может скомпилироваться на некоторых компиляторах. Но не на других. Или он определит NULL как ноль странным образом. Подключайте , если используете указатели.

Что дальше?

Базовый стек прост. Реальные стеки требуют большего.

Добавьте dup. Дублируйте верхний элемент. Добавьте count. Возвращайте количество элементов. Добавьте add. Извлеките два верхних элемента, сложите их, поместите результат обратно.

Напишите драйверную программу. Напишите Makefile. Скомпилируйте. Запустите.

Если он падает, вы пропустили free. Или вы обратились к освобожденной памяти. Отлаживайте.

Реальная оценка

Динамическое выделение памяти быстро. Пока не станет иначе.

malloc и free имеют накладные расходы. В плотных циклах это накапливается.

Но для общего использования? Это гибко. Это стандартно. Это то, что вы увидите в большинстве кодовых баз на C.

Связанный стек — это строительный блок.

Вы будете использовать его для вызовов функций. Для вычисления выражений. Для кнопок «Отменить».

Он повсюду.

Просто помните: если вы выделили память, вы должны её освободить. Иначе.

«Код подобен юмору»