Структура данных очереди | Кодементор

Структура данных очереди
Структура данных очереди является абстрактным типом данных. Мы также можем назвать это коллекцией. Это прежде всего линейная и последовательная структура данных. Все элементы в очереди в порядке. Важными операциями в очереди являются добавление элемента в заднее конечное положение и удаление элемента из переднего положения. Операция добавления называется постановкой элемента в очередь. И операция удаления называется удалением элемента из очереди. Это эффективная процедура First In First Out (FIFO). Другими словами, первый элемент, попадающий в очередь, становится первым элементом, покидающим очередь. Это понятие заказа в очереди.

Удаление конкретного элемента зависит от удаления предыдущего элемента. Это становится основным ограничением в структуре данных очереди.

Есть еще одна операция, которая не является обязательной. Это называется заглянуть в очередь. Вы можете заглянуть в начало очереди, если это реализовано в коде. Peek не удаляет элемент, а просто возвращает элемент в начале очереди.

Одним из экземпляров очереди является буфер. Буфер содержит данные, которые можно прочитать с противоположного конца. Таким образом, буфер получает данные с одного конца, а затем сбрасывает данные с другого конца. Поэтому, если вас попросят реализовать буфер, вы можете сделать это с помощью очереди. Очереди могут быть реализованы с использованием связанных списков. Существуют и другие типы реализации очередей, например циклический буфер, в котором буфер фиксированного размера выделяется путем сквозного соединения. Затем вы можете выполнять потоковую передачу данных поверх него. Я перейду к части потоковой передачи данных чуть позже. Пока просто помните, что циклические буферы — это реализация очереди, т. е. FIFO, а нециклические буферы — реализация LIFO. Существует еще один тип очереди, который называется ограниченной очередью. Ограниченная очередь имеет фиксированный размер, что означает, что если она заполнена, она не позволяет добавлять операции, поэтому нам нужны дополнительные проверки ограничений поверх очереди. Помните, что чем больше проверок вы введете, тем больше будет накладных расходов на производительность.

Мы можем использовать двусвязные списки для реализации очередей. В таких случаях добавление и удаление элементов в/из очереди дает нам временную сложность O(1) на каждом конце. Динамические массивы можно использовать для реализации очередей.

Удобство использования (преимущества/недостатки)
Его можно использовать для поддержки подмножества определенного размера. Например, если вы хотите сохранить подмножество из 3 элементов из набора из 10 элементов. Примером этого являются простые скользящие средние. Простые скользящие средние в основном используются в анализе финансовых данных. Если вы хотите сохранить скользящее окно в наборе, очень привлекательно подумать о его реализации с использованием структуры данных Queue.
В задаче с ограниченным буфером или проблеме производитель-потребитель циклическая очередь может оказаться полезной. Проблема ограниченного буфера возникает из-за проблемы синхронизации процессов. Эта проблема возникает, когда производитель пытается записать в буфер фиксированного размера, в то время как в какой-то другой момент потребитель может попытаться прочитать пустой буфер. Чтобы решить эту проблему, вам нужен механизм уведомления процесса. Если говорить о пользе, то очереди данных становятся самым быстрым методом межпроцессного взаимодействия.
Очереди могут иметь элементы любых типов данных. Это аспект гибкости. У вас может быть очередь очередей, очередь целых чисел, очередь строк, очередь массивов или очередь объекта любого типа.
Очередь недоступна для поиска. Вы должны начать с конца и, возможно, придется поддерживать еще одну очередь. Так что, если у вас есть какие-то данные, которые позже вы хотели бы сделать доступными для поиска, то даже не думайте об использовании очереди.
Добавление или удаление элементов из середины очереди также является сложной задачей.
Многие очереди реализованы с использованием указателей, поэтому многие программисты считают, что их сложно создавать, поддерживать и манипулировать ими.
Очередь занимает меньше места, чем большинство нелинейных структур данных. Позже вам, возможно, придется поддерживать матрицы смежности и списки.
Вы также можете создать очередь, используя только два стека. Существуют методы их реализации с использованием одного стека. Вы можете добавить отправленный элемент в очередь, а затем повернуть очередь. Помните, что стек разрешает только операции push и pop. Подход с одним стеком может быть дорогостоящим, и может потребоваться рекурсивное извлечение до конца, а затем возврат его в качестве первого элемента из логической очереди.
Они используются для реализации очень полезной структуры данных, называемой очередями с приоритетом, где задания с одинаковым приоритетом следуют правилам FIFO. Если вы изучите приоритетные очереди, вы сможете понять внутренности куч и полных двоичных деревьев.
Вопросы, связанные с очередями, являются фаворитами на многих собеседованиях, связанных с разработкой программного обеспечения, поэтому их изучение может привести вас к работе.