Черги в Python
Як запустити FIFO структуру даних у Python, використовуючи лише вбудовані типи даних і класи зстандартної бібліотеки. Черга – це набір об'єктів, що підтримує швидку семантику first-in, first-out (FIFO) для вставки та видалення. Операції вставки та видалення іноді називаютьenqueue таdequeuer. На відміну від списків і масивів, черги, як правило, не пропускають випадковий доступ до об'єктів, що містяться.
Аналогія черги first-in, first-out на пальцях
Подайте ряд пітоністів, чекаючи отримання бейджиків на конференції в день реєстрації наPyCon. Нові доповнення у низці знаходяться наприкінці черги, оскільки нові люди стають у чергу на конференцію в очікуванні бейджиків. Скорочення черги (подача) відбувається на її початку, оскільки розробники отримують свої бейджі з новими кепками з написом SWAG і залишають чергу.
Інший спосіб описати таку структуру даних, як черга, це уявити її як трубку:
Нові об'єкти (молекули води, кульки для тенісу, і т.д.) поміщаються в один кінець трубки, і рухаються до іншого, коли ви, або щось інше пропихає їх уздовж трубки. Поки об'єкти знаходяться у черзі (у нашому випадку це трубка), ви не можете дістати їх. Єдиний спосіб взаємодії з об'єктами в черзі, це додати нові об'єкти в кінці черги (enqueuer ) або прибрати існуючі з початку (dequeuer ) трубки.
Черги схожі на стеки, але відрізняються способом видалення елементів :
У випадку з чергою ви видаляєте об'єкт, який був нещодавно доданий (за принципом перший увійшов – першим вийшов first-in, first-out абоFIFO ), у разі сто стеком ви видаляєте останній доданий елемент (останнім зайшов – першим вийшов, last-in, first-out orLIFO ).
З погляду продуктивності, правильна реалізація черги полягає у виділенні О(1) часу для вставки та видалення операцій. Існує дві основні операції, що використовуються в черзі, і вони повинні виконувати роботу швидко і коректно. Черги Python мають широку низку додатків в алгоритмах, а також все необхідне для складання графіків, а також вирішення паралельних проблем у програмуванні. Короткий і зручний алгоритм під назвоюBFS (breadth-first search) підходить для роботи з такими структурами даних якtree таgraph.
Алгоритми планування часто використовують пріоритетні черги зсередини. Існують певні види черг: замість отримання наступного елемента відповідно до зазначеного часу вставки, пріоритетна черга витягує елемент із найвищим пріоритетом. Пріоритет окремих елементів визначається чергою виходячи з порядку застосовуваних до них ключам. Однак, звичайна черга не перевизначатиме порядок об'єктів, які в ній знаходяться. Ви отримуєте тільки те, і в тому порядку, в якому ви поміщали об'єкти у чергу (приклад із трубкою). Python дозволяє виконати кілька реалізацій черги, кожна з яких має невеликі відмінності. Давайте розглянемо їх:
Вбудований список
Ми можемо використовувати звичайний список як черга, але це не дуже ефективно з точки зору продуктивності. Списки занадто повільні для цього завдання, так як вставка та видалення елемента з початку вимагає зсуву всіх інших елементів по одному, на це йде час. У зв'язку з цим, я не поспішаю рекомендувати список як тимчасова черга в Python (хіба що ви маєте справу з невеликою кількістю елементів).