У попередніх відео ми розглянули абстрактну модель та імплементацію для списків. Поговорили про Array та LinkedList. Сьогодні ми перейдемо до наступної базової структури даних Стек / Stack. Тож погнали!
Що таке цей стек. Дуже знайоме слово для розробників і не тільки.
Давайте розглянемо на пальцях, а точніше на прикладах із реального життя.
Стеки знаходяться всюди серед нас, наприклад:
Стопка посуду
Чи Коробок з піцою
Або Дитяча пірамідка
Все це Стек - колекція елементів, додавати чи видаляти які можна тільки з одного кінця top / верхівка стеку. Це основне обмеження, умова для Стеку. Також цю структуру часто називають last-in-first-out LIFO. Останній зайшов перший вийшов.
На базі цього, пропоную визначити абстрактну модель для структури даних Стек / Stack
- Може додавати та видаляти елементи тільки з одного кінця
- Може читати / отримувати елемент з верхівки стеку
Взагалі стек дуже широко використовується у комп'ютері, наприклад копіювання / вставка copy & paste працює на базі стеку.
Або ж редактори коду для перевірки синтаксису теж використовую стек.
Stack має наступні фічі / методи
- push
- pop
- top
- isEmpty
Перейдемо до специфікації та реалізації.
Визначимо специфікацію абстрактної моделі для структури даних Stack / Стек:
Імплементація для структури даних Stack / Стек на базі класу LinkedList:
Git репозиторій https://github.com/kostrub-online/Computer-Science
Підсумуємо. Сьогодні ми познайомились з базовою структурою даних Стек / Stack. Зробили опис абстрактної моделі, специфікації та розглянули одну з можливих реалізацій на базі LinkedList. Дякую за перегляд. Якщо є питання, звертайтесь в коментарях та підписуйтесь на канал, щоб не пропустити наступне відео про Чергу / Queue.
Далі більше!
0 Коментарі