Учебные заметки: структуры данных и алгоритмы Python
Обзор
Очереди - это популярные линейные структуры данных или, говоря более абстрактно, последовательная коллекция. Изменения в структуре данных очереди выполняются в порядке очереди (FIFO). Добавления в очередь выполняются сзади, что называется enqueue, а удаление элементов выполняется спереди, что называется dequeue.
Хороший способ концептуализировать структуру данных очереди - представить ее, как если бы клиенты выстраивались в очередь за чашкой кофе в местном Starbucks. Первый покупатель, который войдет в магазин, будет обслужен первым, поэтому его заказ будет выполнен первым, и он сможет уйти. Любой другой покупатель, который входит в магазин в это время, должен стоять в очереди за покупателем, который опережает их.
Почему существуют очереди?
Как и стеки, очереди чрезвычайно полезны, когда важен порядок действий. В отличие от стеков, очереди требуются, когда управление данными должно выполняться в таком, что первый элемент должен быть первым элементом, пока другие элементы ждут своей очереди. Например, рассмотрим сценарий, в котором несколько человек хотят что-то напечатать, и все запросы отправляются на один общий принтер. Принтер будет ставить листы в очередь для печати, начиная с первого запроса. Когда первый запрос будет выполнен, принтер перейдет к следующему листу в очереди.
Преимущества
- Помогает управлять данными в порядке FIFO (First In First Out)
- Может обрабатывать элементы любого типа данных, что делает его чрезвычайно гибким
Недостатки
- Добавление или удаление элементов из середины - сложная задача
Очереди в Python
Очереди в Python могут быть реализованы несколькими способами. В этой статье я сосредоточусь в первую очередь на использовании структур данных и встроенных модулей Python для реализации нашей очереди. Следующие способы реализации очередей в Python:
Список
Python list можно использовать как очередь. Вместо метода enqueue() для добавления элементов в очередь мы просто используем метод append(). Кроме того, мы используем pop(0) вместо deque() для удаления первого элемента, добавленного в очередь - это репликация порядка FIFO.
# example of list to implement stack queue = [] queue.append(1) queue.append(2) queue.append(3) print(queue) >>>> [1, 2, 3] print(queue.pop(0)) >>>> 1 print(queue.pop(0)) >>>> 2 print(queue.pop(0)) >>>> 3 print(queue) >>>> []
Списки - не самый эффективный способ создания очередей. Вставка или удаление элемента в начале очереди означает, что другие элементы должны быть сдвинуты на единицу, таким образом, операция выполняется за время O (n).
collections.deque
Модуль collections также служит удобным способом реализации очередей.
# example of collections.deque to implement queue from collections import deque queue= deque() queue.append(1) queue.append(2) queue.append(3) print(queue) >>>> deque([1, 2, 3]) print(queue.popleft()) >>>> 1 print(queue.popleft()) >>>> 2 print(queue.popleft()) >>>> 3 print(queue) >>>> deque([])
На первый взгляд, операции deque напоминают операции list. Однако внутри deque представлен как двусвязный список (или список массивов, а не объектов, если быть более точным - для большей эффективности). Каждый элемент хранится в собственном блоке памяти со ссылкой на следующую запись в списке и предыдущую запись. Следовательно, deque преодолевает проблемы, обнаруженные в реализации list, выполняя операции добавления / извлечения в O (1) на обоих концах очереди.
queue.Queue
Следующий вариант - использовать модуль queue, который реализует очередь с классом Queue. Мы используем put() для добавления элементов в стек и get() для удаления элементов.
# example of queue.Queue to implement queue # source code https://www.geeksforgeeks.org/queue-in-python/fromqueue importQueue# Initializing a queue queue =Queue(maxsize =3)# qsize() give the maxsize of the Queue print(queue.qsize())>>>> 0# Adding of element to queue queue.put('a') queue.put('b') queue.put('c')# Return Boolean for Full Queueprint("\nFull: ", queue.full()) >>>> Full: True# Removing element from queue print("\nElements dequeued from the queue")print(queue.get()) print(queue.get()) print(queue.get())>>>> Elements dequeued from the queue a b c# Return Boolean for Empty Queue print("\nEmpty: ", queue.empty()) >>>> Empty: Truequeue.put(1)print("\nEmpty: ",queue.empty()) print("Full: ",queue.full())>>>> False >>>> False
Заворачивать
Очереди - это популярные линейные структуры данных, в которых элементы хранятся в порядке очереди (FIFO). Представление об очереди как о очереди в магазине - это самый простой способ представить себе, как работают очереди. По сути, мы добавляем новый элемент в конец очереди (enqueue) и удаляем элемент из начала очереди (dequeue).
Спасибо за чтение!
Если вам понравилась эта статья, свяжитесь со мной, подписавшись на мою БЕСПЛАТНУЮ еженедельную рассылку. Не пропустите мой пост об искусственном интеллекте, машинном обучении и фрилансе.
