Руководство для начинающих по пониманию очередей и очередей с приоритетом
Как программист, вы будете работать с разными структурами данных в зависимости от объема ваших проектов. Одна из таких концепций – структура данных очереди; очереди важны для студентов и используются во многих важных алгоритмах. Как и очереди, очереди с приоритетом имеют схожую концепцию, но имеют несколько фундаментальных отличий.
Прочтите, чтобы понять очереди и очереди с приоритетом.
Что такое очередь?
Очередь – это простая структура данных, которая имеет множество приложений в реальных проектах кодирования. Структуры данных по своей сути абстрактны, но для простоты мы предполагаем, что структура данных очереди имеет линейную форму с двумя разными концами.
Что касается временной сложности, очередь допускает вставку (постановку в очередь) и удаление (удаление из очереди) за время O (1). Благодаря своей асимптотической эффективности очереди эффективны для больших наборов данных. Очереди являются по своей природе «первым пришел – первым обслужен» (FIFO), что означает, что первым будет доступ к элементу данных, который вставлен первым. Напротив, стеки работают по принципу «последним пришел – первым ушел» (LIFO) и имеют только один открытый конец.
Представьте себе очередь за билетами в кинотеатре; каждый новый поступающий заказчик присоединяется к очереди с одного конца. Один за другим каждый клиент покупает билет и покидает очередь через интерфейс пользователя. Структура данных очереди функционирует точно так же, как любая реальная очередь, и данные вставляются (ставятся в очередь) на одном конце и удаляются (выводятся из очереди) на другом конце. Надеюсь, теперь вы понимаете, почему очереди следуют методологии FIFO.
В очереди есть множество реальных приложений для кодирования. Он чаще используется в приложениях, где данные нужно обрабатывать не сразу, а в порядке FIFO. Планирование диска, асинхронная передача данных, семафоры – вот некоторые типичные приложения. В задачах планирования в порядке очереди, таких как буферизация печати или буферы устройства ввода, также используется очередь.
Что такое приоритетная очередь?
Очередь с приоритетом похожа на очередь, но имеет дополнительные свойства. Когда элемент данных помещается в очередь приоритета, ему присваивается номер приоритета. В отличие от удаления из стандартной очереди, элементы данных с высоким приоритетом удаляются из очереди перед элементами данных с низким приоритетом. Приоритет заменяет порядок прибытия в очереди с приоритетом, поэтому очереди с приоритетом не имеют последовательной природы FIFO.
Программисты могут реализовать приоритетную очередь несколькими способами. Простая реализация заключается в использовании массива с элементом данных структуры / класса, при этом элемент данных будет содержать приоритет каждого элемента данных и самих данных. Еще одна примитивная реализация очереди с приоритетом – использование связного списка. Очереди приоритетов, реализованные с помощью связанных списков, функциональны, но не идеальны из-за своей производительности.
Вы можете реализовать очередь с более высоким приоритетом с помощью кучи. Если вы помните, двоичные кучи дают максимальный или минимальный элемент за 0 (1) время, а вставка занимает только 0 (logN) время. С помощью куч очереди с приоритетом асимптотически обеспечивают лучшую производительность по сравнению с очередями или массивами.
Очередь с приоритетом также имеет множество важных приложений. Очереди приоритетов имеют решающее значение в алгоритмах графов, таких как минимальное связующее дерево Прима и алгоритм кратчайшего пути Дейкстры. Они также идеально подходят для алгоритмов планирования процессов компьютерного процессора (ЦП).
Изучите структуры данных
Очереди и очереди с приоритетом – важные структуры данных для всех новичков. Крайне важно, чтобы учащимся было удобно реализовывать эти структуры данных и использовать их в различных проектах.
Другие структуры данных, такие как кучи, стеки и деревья, одинаково важны для студентов и профессионалов. Интервьюеры также часто задают кандидатам вопросы о структурах данных.
Прочитав эту статью, вы должны иметь хорошее представление о том, как работают очереди и очереди с приоритетом. Если все еще кажется немного неясным, вы разберетесь с ними, когда приобретете больше опыта их использования.