Більшість новачків вважають, що структури даних статичні. Це негаразд. Пов’язаний стек – це динамічна сутність. Він росте і стискується на льоту. Ви не виділяєте пам’ять заздалегідь. Ви отримуєте її, коли вона потрібна. Визволяєте, коли закінчили.
У цьому вся прикладі використовуються цілі числа. Змініть 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 не вибачає помилок.
- Купки мають значення.
(*p).iне те ж саме, що*p.i. У першому випадку спочатку розіменовується покажчик. У другому – спочатку доступ до члена, потім розйменування. Помилитесь – отримайте збій. - Виток пам’яті. Ніколи не просто привласнюйте
top = NULL. Ви втратите всі вузли у списку. Ви втратите дані. Ви втратите пам’ять. Використовуйтеfree. Завжди. - Підключайте заголовні файли.
NULLзнаходиться вstdio.h. Якщо ви забудете його підключити, код може скомпілюватися на деяких компіляторах. Але не на інших. Або він визначитьNULLяк нуль дивним чином. Підключайте
Що далі?
Базовий стек простий. Реальні стеки потребують більшого.
Додайте dup. Дублюйте верхній елемент. Додайте count. Повертайте кількість елементів. Додайте add. Вийміть два верхні елементи, складіть їх, помістіть результат назад.
Напишіть драйверну програму. Напишіть Makefile. Скомпілюйте. Запустіть.
Якщо він падає, ви пропустили free. Або ви звернулися до звільненої пам’яті. Налагоджуйте.
Реальна оцінка
Динамічний виділення пам’яті швидко. Поки що не стане інакше.
malloc та free мають накладні витрати. У щільних циклах це накопичується.
Але для загального користування? Це гнучко. Це стандартно. Це те, що ви побачите у більшості кодових баз на C.
Пов’язаний стек – це будівельний блок.
Ви будете використовувати його для функцій викликів. Для обчислення виразів. Для кнопок “Скасувати”.
Він усюди.
Просто пам’ятайте: якщо ви виділили пам’ять, ви маєте її звільнити. Інакше.
“Код подібний до гумору”
