|
Очереди типов FIFO и LIFOКурс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs Стандартная библиотека Python содержит несколько весьма полезных классов для работы с такой структурой данных, как очереди:
Но прежде чем переходить непосредственно к рассмотрению этих классов, давайте в целом познакомимся с идеей очередей. Я о них уже рассказывал в курсе по структурам данных. Здесь повторю этот материал. Само слово очередь (по англ. queue) сразу ассоциируется с очередью в магазин за каким-нибудь долгожданным или дефицитным продуктом:
Здесь тот, кто первым пришел (First In), тот первым и покидает очередь (First Out). Именно поэтому такой тип очереди получил сокращенное название FIFO. То есть, в такой структуре данные добавляются в конец очереди, а извлекаются из начала. Где может быть полезна такая организация данных? Распространенный пример – буфер приема или передачи какого-либо устройства:
Здесь вновь поступающие данные добавляются в конец очереди, а извлекаются (читаются) из начала очереди. Или можно представить систему обработки заказов интернет-магазина. Здесь также целесообразно организовать очередь и обрабатывать заказы в порядке их поступления:
И так далее. Везде, где требуется работать с очередностью объектов, имеет смысл рассмотреть возможность использования очереди для хранения данных. Но это первый тип очереди, который, как мы уже знаем, носит название FIFO. Есть еще один тип очереди под названием: LIFO (Last In, First Out) Что это за очередь? Представьте себе ящик, в который складываются разные вещи:
А вынимать их можно только сверху. В результате, последняя положенная вещь будет извлечена первой, вторая – второй и так до последней. Получаем очередь типа LIFO: последний зашел, первый вышел. Классический пример использования этого типа очереди – организация стеков вызова функций в программах. Пусть имеется вот такая простая программа на языке Python, в которой последовательно вызываются три функции: сначала main, затем show_sum и последней print: def show_sum(a, b): print(a+b) def main(): show_sum () Чтобы интерпретатор «знал» в какой последовательности функции были вызваны и в какой последовательности продолжать их выполнять, после завершения очередной, формируется очередь по принципу LIFO: последняя вызванная функция должна первой и завершаться, затем, вторая и, наконец, третья.
Реализация очередей на основе связных списковВот принцип работы очередей. Они, как правило, добавляют и извлекают граничные элементы, не обращаясь к промежуточным. Хотя их функционал позволяет работать и с промежуточными элементами, но это используется крайне редко. Итак, для реализации очередей нужно выбрать структуру, которая бы обладала высокой скоростью обработки крайних элементов последовательности, то есть, O(1). Этим свойством обладают односвязные и двусвязные списки:
Идея их очень проста. Каждый элемент (объект) двусвязного списка содержит ссылки на следующий (next) и предыдущий (prev) такие же элементы. С помощью этих ссылок мы можем переходить последовательно от одного элемента к другому в обоих направлениях, пока не дойдем до крайних, у которых эти ссылки принимают значение None (или NULL, или какое-либо другое предопределенное значение). В каждом элементе связного списка хранятся данные в поле data. Кроме того, имеются глобальные ссылки: head – на первый элемент связного списка; tail – на последний элемент связного списка. Особенность такой структуры организации данных заключается в простоте добавления новых крайних элементов, а также их быстрого удаления, при необходимости. Именно поэтому одно- и двусвязные списки довольно часто применяются для реализации очередей. Очередь, как абстрактная структура данныхВообще, очереди можно реализовывать не только на базе связных списков, но, например, и динамического массива (например, списка list). Тогда для очереди типа FIFO нам придется при добавлении нового элемента в начало сдвигать все остальные элементы массива, что вычислительно несколько дольше – O(n) операций (вместо O(1) для связных списков). Да и операции добавления новых элементов в конец динамического массива требуют большего числа операций, чем у связных списков. Поэтому динамический массив для очередей, в общем случае, не лучший выбор. Хотя, в некоторых частных задачах, возможно, это будет иметь смысл. Я привел пример с динамическим массивом, чтобы вы ясно себе представляли, что очередь – это не какая-то конкретная структура данных, как связные списки или массивы, а несколько абстрактная. Она лишь определяет порядок взаимодействия с элементами упорядоченной коллекции. А именно, добавление и удаление граничных элементов. С промежуточными элементами тоже возможно взаимодействие, но производительность этих операций, как правило, значительно ниже и составляет O(n), где n – число элементов в очереди. На следующих занятиях мы увидим, как реализуются очереди с использованием приведенных классов. Курс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs Видео по теме |
