|
Очереди типов FIFO и LIFOКурс по структурам данных: https://stepik.org/a/134212 Мы продолжаем изучение структур данных. На этом занятии познакомимся с еще одним способом организации данных – очередями. Само слово очередь (по англ. queue) сразу ассоциируется с очередью в магазин за каким-нибудь долгожданным или дефицитным продуктом:
Здесь тот, кто первым пришел (First In), тот первым и покидает очередь (First Out). Именно поэтому такой тип очереди получил сокращенное название FIFO. То есть, в такой структуре данные добавляются в конец очереди, а извлекаются из начала. Где может быть полезна такая организация данных? Распространенный пример – буфер приема или передачи какого-либо устройства:
Здесь вновь поступающие данные добавляются в конец очереди, а извлекаются (читаются) из начала очереди. Или можно представить систему обработки заказов интернет-магазина. Здесь также целесообразно организовать очередь и обрабатывать заказы в порядке их поступления:
И так далее. Везде, где требуется работать с очередностью объектов, имеет смысл рассмотреть возможность использования очереди для хранения данных. Но это первый тип очереди, который, как мы уже знаем, носит название FIFO. Есть еще один тип очереди под названием: LIFO (Last In, First Out) Что это за очередь? Представьте себе ящик, в который складываются разные вещи:
А вынимать их можно только сверху. В результате, последняя положенная вещь будет извлечена первой, вторая – второй и так до последней. Получаем очередь типа LFIO: последний зашел, первый вышел. Классический пример использования этого типа очереди – организация стеков вызова функций в программах. Пусть имеется вот такая простая программа на языке Python, в которой последовательно вызываются три функции: сначала main, затем show_sum и последней print: def show_sum(a, b): print(a+b) def main(): show_sum () Чтобы интерпретатор «знал» в какой последовательности функции были вызваны и в какой последовательности продолжать их выполнять, после завершения очередной, формируется очередь по принципу LIFO: последняя вызванная функция должна первой и завершаться, затем, вторая и, наконец, третья.
Реализация очередей на основе связных списковВот принцип работы очередей. Они, как правило, добавляют и извлекают граничные элементы, не обращаясь к промежуточным. Хотя их функционал позволяет работать и с промежуточными элементами, но это используется крайне редко. Итак, для реализации очередей нужно выбрать структуру, которая бы обладала высокой скоростью обработки крайних элементов последовательности, то есть, O(1). И мы с такими структурами уже знакомы – это односвязные и двусвязные списки:
Но чаще всего применяют двусвязные списки для реализации очередей, так как это более универсальная структура. Сами же очереди на базе двусвязных списков получили название: deque (сокращение от double ended queue) То есть, очереди часто представляют собой обычные двусвязные списки. В результате, чтобы организовать очередь типа FIFO нам достаточно добавлять новые элементы в начало списка, а извлекать с конца. Это делается с помощью уже знакомых нам методов push_front() и pop_back(). А для очереди типа LIFO можно использовать методы push_front() и pop_front(). Кстати, можно заметить, что тот же эффект достигается, если мы будем конец списка считать началом, а начало – концом. Тогда очередь FIFO будет строиться методами push_back() и pop_front(), а очередь LIFO методами push_back() и pop_back(). Принципиальной разницы в их функционировании при этом не будет. Сразу отмечу, что очереди типа deque реализуются не только на основе обычных двухсвязных списков, но и на гибридной структуре двухсвязных списков и динамических массивов:
Благодаря такому подходу доступ к отдельным промежуточным элементам осуществляется несколько быстрее, чем в случае с обычными связными списками. В частности, по такой схеме реализована очередь deque в стандартной библиотеке шаблонов STL языка C++. Недостатком такой структуры является более медленный алгоритм вставки новых элементов в начало этого модифицированного списка, т.к. приходится сдвигать ранее записанные элементы массива первого объекта списка. Очередь, как абстрактная структура данныхВообще, очереди можно реализовывать не только на базе связных списков, но, например, и динамического массива. Тогда для типа FIFO нам придется при добавлении нового элемента в начало сдвигать все остальные элементы массива, что вычислительно несколько дольше – O(n) операций (вместо O(1) для связных списков). Да и операции добавления новых элементов в конец динамического массива требуют большего числа операций, чем у связных списков. Поэтому динамический массив для очередей, в общем случае, не лучший выбор. Хотя, в некоторых частных задачах, возможно, это будет иметь смысл. Я привел пример с динамическим массивом, чтобы вы ясно себе представляли, что очередь – это не какая то конкретная структура данных, как связные списки или массивы, а несколько абстрактная. Она лишь определяет порядок взаимодействия с элементами упорядоченной коллекции. А именно, добавление и удаление граничных элементов. С промежуточными элементами тоже возможно взаимодействие, но производительность этих операций, как правило, значительно ниже и составляет O(n), где n – число элементов в очереди. На следующих занятиях мы увидим, как реализуются очереди на языках программирования С++ и Python. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
