Структура даних Черга / Queue

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

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