У попередньому відео ми розглянули абстрактну модель та одну імплементацію для Cтека на базі зв'язаного списку. Сьогодні ми перейдемо до наступної дуже важливої структури даних Черга / Queue.
Тож погнали. Пропоную розглянути що ж таке ця Queue. Насправді, це ця ж саме черга, в якій ми стоїмо у реальному житті.
Черга - це структура, в котрій кожен об'єкт який входить першим також виходить першим. Іншими словами First in First out (FIFO) структура. Якщо ви не дивились попереднє відео про Cтек - то нагадаю, Стек на відміну від Черги - Last in First Out (LIFO) структура. Це треба чітко розуміти, тому ще це одне з найчастіших запитань на технічному скринінгу.
Також, на відміну від Стеку, додавання нового елементу відбувається з кінця (rear/tail). A видалення з іншої сторони - голови Черги (front/head).
Таким чином ми можемо визначити абстрактну модель для Черги, як структура що може
- додавати елементи тільки з одного кінця (rear)
- видаляти елементи тільки з протилежного кінця - голови черги (front)
Також Черга має наступні основні операції над елементами:
- вставити елемент (enQueue / push)
- видалити елемент (deQueue / pop)
- прочитати перший елемент з голови (front / peek)
- перевірити на наявність елементів (isEmpty)
На базі цього можемо перейти до специфікації та імплементації нашої абстрактної моделі для структури даних Черга.
Але пропоную ще розглянути приклади використання цієї структури у реальних системах.
Наприклад, це може бути спільний мережевий принтер в офісі:
Для того, щоб коректно обробляти запити на друк, принтер має вбудовану чергу.
Наступний приклад, будь-які системи чи сервіси з покупки чи бронювання, скажемо квитків
Хто перший передплатив - той перший і отримав. Теж дотримуючись черги.
Перейдемо до специфікації та реалізації.
Визначимо специфікацію абстрактної моделі для структури даних Queue / Черга:
Імплементація для структури даних Queue / Черга на базі класу List:
Git репозиторій https://github.com/kostrub-online/Computer-Science
Підсумуємо. Сьогодні ми розглянули абстрактну модель та специфікацію структури даних Черга / Queue. Зробили реалізацію Черги на базі нашого класу List. Також познайомились з декораторами. Вирішуйте задачі, щоб краще зрозуміти матеріал та підготуватись до співбесіди. Пишіть якщо щось не виходить, будемо фіксити разом. Та підписуйтесь на канал, щоб не пропустити наступну тему Tree / Дерево. Далі більше!
0 Коментарі