В этой статье мы рассмотрим основные концепции очереди, ее типы и методы реализации.
Очередь
Очередь — это АТД с линейной структурой, которая следует определенному порядку выполнения операций. Заказ First In First Out (FIFO).
Практические примеры:
Хорошим примером очереди является любая очередь людей в банке или магазине. Что следует правилу: приходит первым и обслуживается первым.
Основное различие между стеком (Нажмите, чтобы увидеть мой блог в этом ADT) и очередью заключается в том, что мы удаляем недавно добавленные элементы из стека (при выполнении операции извлечения). Но в Queue мы удаляем первый добавленный элемент при вызове операции удаления.
Операции в очереди:
В очереди выполняются следующие основные операции:
→ Enqueue():добавляет элемент в очередь.
→ Dequeue(): удаляет элемент из очереди.
→ IsEmpty (): Очереди пусты или не
Все операции будут иметь временную сложность O(1)
Типы очереди
1. Приоритетная очередь
Это похоже на перегородки в общественном транспорте, которые имеют секции первого, второго и эконом-класса для пассажиров.
Характеристики
→ Каждый элемент имеет связанный с ним приоритет.
→ Элемент с высоким приоритетом удаляется из очереди перед элементом с низким приоритетом.
→ Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди.
2. Дек
Это версия Queue, которая позволяет вставлять и удалять на обоих концах.
Реализация для очередей
Существует два метода реализации очередей.
на основе массива
Легко реализовать, но потому что массив имеет фиксированный размер, и это может где-то создать проблему (когда очередь превышает размер массива).
Связанный список на основе
Эффективный, но сложный в реализации, а также требует больше памяти, чем массивы (узел указателя).
Спасибо за чтение и удачного обучения! 🙌
PS: Вы можете найти коды реализации очередей и приоритетных очередей в моей Учетной записи GitHub.
