Структура даних Стек / Stack

Привіт всім айтішникам, вітаю на каналі kostrub.online

У попередніх відео ми розглянули абстрактну модель та імплементацію для списків. Поговорили про 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 Коментарі