Руководство для начинающих по пониманию очередей и очередей с приоритетом

Как программист, вы будете работать с разными структурами данных в зависимости от объема ваших проектов. Одна из таких концепций - структура данных очереди; очереди важны для студентов и используются во многих важных алгоритмах. Как и очереди, очереди с приоритетом имеют схожую концепцию, но имеют несколько фундаментальных отличий.

Прочтите, чтобы понять очереди и очереди с приоритетом.

Что такое очередь?

Очередь - это простая структура данных, которая имеет множество приложений в реальных проектах кодирования. Структуры данных по своей сути абстрактны, но для простоты мы предполагаем, что структура данных очереди имеет линейную форму с двумя разными концами.

Что касается временной сложности, очередь допускает вставку (постановку в очередь) и удаление (удаление из очереди) за время O (1). Благодаря своей асимптотической эффективности очереди эффективны для больших наборов данных. Очереди являются по своей природе «первым пришел - первым обслужен» (FIFO), что означает, что первым будет доступ к элементу данных, который вставлен первым. Напротив, стеки работают по принципу «последним пришел - первым ушел» (LIFO) и имеют только один открытый конец.

Представьте себе очередь за билетами в кинотеатре; каждый новый поступающий заказчик присоединяется к очереди с одного конца. Один за другим каждый клиент покупает билет и покидает очередь через интерфейс пользователя. Структура данных очереди функционирует точно так же, как любая реальная очередь, и данные вставляются (ставятся в очередь) на одном конце и удаляются (выводятся из очереди) на другом конце. Надеюсь, теперь вы понимаете, почему очереди следуют методологии FIFO.

В очереди есть множество реальных приложений для программирования. Он чаще используется в приложениях, где данные нужно обрабатывать не сразу, а в порядке FIFO. Планирование диска, асинхронная передача данных, семафоры - вот некоторые типичные приложения. В задачах планирования в порядке очереди, таких как буферизация печати или буферы устройства ввода, также используется очередь.

Что такое приоритетная очередь?

Очередь с приоритетом похожа на очередь, но имеет дополнительные свойства. Когда элемент данных помещается в очередь приоритета, ему присваивается номер приоритета. В отличие от удаления из стандартной очереди, элементы данных с высоким приоритетом удаляются из очереди перед элементами данных с низким приоритетом. Приоритет заменяет порядок прибытия в очереди с приоритетом, поэтому очереди с приоритетом не имеют последовательной природы FIFO.

Связанный: Алгоритмы, которые должен знать каждый программист

Программисты могут реализовать приоритетную очередь несколькими способами. Простая реализация заключается в использовании массива с элементом данных структуры / класса, при этом элемент данных будет содержать приоритет каждого элемента данных и самих данных. Еще одна примитивная реализация очереди с приоритетом - использование связного списка. Очереди приоритетов, реализованные с помощью связанных списков, функциональны, но не идеальны из-за своей производительности.

Вы можете реализовать очередь с более высоким приоритетом с помощью кучи. Если вы помните, двоичные кучи дают максимальный или минимальный элемент за 0 (1) время, а вставка занимает только 0 (logN) время. С помощью куч очереди с приоритетом асимптотически обеспечивают лучшую производительность по сравнению с очередями или массивами.

Очередь с приоритетом также имеет множество важных приложений. Очереди приоритета имеют решающее значение в алгоритмах графов, таких как минимальное связующее дерево Прима и алгоритм кратчайшего пути Дейкстры. Они также идеально подходят для алгоритмов планирования процессов компьютерного процессора (ЦП).

Изучите структуры данных

Очереди и очереди с приоритетом - важные структуры данных для всех новичков. Крайне важно, чтобы учащимся было комфортно реализовывать эти структуры данных и использовать их в различных проектах.

Другие структуры данных, такие как кучи, стеки и деревья, одинаково важны для студентов и профессионалов. Интервьюеры также часто задают кандидатам вопросы о структурах данных.

Прочитав эту статью, вы должны иметь хорошее представление о том, как работают очереди и очереди с приоритетом. Если все еще кажется немного неясным, вы разберетесь с ними, когда приобретете больше опыта их использования.

Кучи vs. Стеки: что их отличает?

Вы слышали о кучах и стеках, но когда стоит использовать одно вместо другого?

Читать далее

Об авторе