На этом шаге мы приведем общие сведения об очереди.
Начиная с этого шага, вы увидите, как реализовывать очередь, то есть структуру данных с дисциплиной доступа FIFO, используя только встроенные типы данных и классы из стандартной библиотеки Python. Но сначала давайте вкратце повторим, что такое очередь.
Очередь представляет собой коллекцию объектов, которая поддерживает быструю семантику доступа "первым пришел - первым ушел" (FIFO - first in, first out) для вставок и удалений. Операции вставки и удаления иногда называются поставить в очередь (enqueue) и убрать из очереди (dequeue). В отличие от списков или множеств, очереди, как правило, не допускают произвольного доступа к объектам, которые они содержат.
Ниже приведена аналогия для очереди с дисциплиной доступа "первым пришел - первым ушел" из реального мира:
Представьте очередь разработчиков-питонистов, ожидающих получения значка участника конференции в день регистрации на PyCon. По мере прибытия новых участников к месту проведения конференции они выстраиваются в очередь, "становясь в ее конец", чтобы получить свои значки. Удаление (обслуживание) происходит в начале очереди, когда разработчики получают свои значки и пакет с материалами и подарками конференции и покидают очередь.
Еще один способ запомнить особенности структуры данных очередь состоит в том, чтобы представить ее как конвейер:
Новые элементы (молекулы воды, теннисные мячи, ...) вставляются в одном конце и проходят в другой, где вы или кто-то другой их все время удаляете. Когда элементы находятся в очереди (в твердой металлической трубе), вы не можете до них добраться. Единственный способ взаимодействия с элементами из очереди заключается в том, чтобы добавлять новые элементы в конец (ставить в очередь) или удалять элементы из начала конвейера (убирать из очереди).
Очереди похожи на стеки, и разница между ними в том, как удаляются элементы.
В случае с очередью вы удаляете элемент, который был добавлен в нее раньше всех (принцип "первым пришел - первым ушел", или FIFO); однако в случае со стеком вы удаляете элемент, который был добавлен в него позже всех (принцип "последним пришел - первым ушел", или LIFO).
С точки зрения производительности предполагается, что надлежащая реализация очереди будет занимать O(1) времени на операции вставки и удаления. Эти две выполняемые с очередью операции являются главными, и при правильной реализации они обеспечивают высокое быстродействие.
Очереди находят широкое применение в алгоритмах и нередко помогают решать задачи планирования и параллельного программирования. Короткий и красивый алгоритм с использованием очереди представлен поиском в ширину (breadth-first search, BFS) на древовидной или графовой структуре данных.
В алгоритмах планирования выполнения задач во внутреннем представлении нередко используются очереди с приоритетом. Они представляют собой специализированные очереди: вместо получения следующего элемента по времени вставки очередь с приоритетом получает элемент с самым высоким приоритетом. Приоритет отдельных элементов определяется очередью, основанной на примененном к их ключам упорядочении. В дальнейшем мы обратимся к очередям с приоритетом и рассмотрим ближе, как они реализуются в Python. Однако в обычной очереди содержащиеся в ней элементы не переупорядочиваются. Точно так же, как и в примере с конвейером, "вы получите только то, что вы вставили", и именно в таком порядке. Python поставляется с несколькими реализациями очереди, каждая из которых обладает несколько различающимися характеристиками. Давайте их рассмотрим.
На следующем шаге мы рассмотрим класс list.
