Введение и реализация массива Queue
Подобно стеку, очередь представляет собой линейную структуру данных, которая следует определенному порядку, в котором выполняются операции для хранения данных. Заказ осуществляется в порядке очереди (FIFO) . Можно представить очередь как очередь людей, ожидающих получения чего-либо в последовательном порядке, который начинается с начала очереди. Это упорядоченный список, в котором вставки выполняются с одного конца, известного как задний, а удаления выполняются с другого конца, известного как передний. Хорошим примером очереди является любая очередь потребителей ресурса, в которой потребитель, пришедший первым, обслуживается первым.
Разница между стеками и очередями заключается в удалении. В стеке мы удаляем последний добавленный элемент; в очереди мы удаляем элемент, добавленный последним.
Основные операции с очередью:
- enqueue(): вставляет элемент в конец очереди, т.е. в конец очереди.
- dequeue(): эта операция удаляет и возвращает элемент, находящийся в начале очереди.
- front(): эта операция возвращает элемент на переднем конце, не удаляя его.
- Rear(): Эта операция возвращает элемент в конце, не удаляя его.
- Empty(): Эта операция указывает, пуста ли очередь или нет.
- size(): Эта операция возвращает размер очереди, т.е. общее количество содержащихся в ней элементов.
Типы очередей:
- Простая очередь. Простая очередь, также известная как линейная очередь, является самой простой версией очереди. Здесь вставка элемента, т.е. операция постановки в очередь, происходит на заднем конце, а удаление элемента, т.е. операция удаления из очереди, происходит на переднем конце.
- Круговая очередь: в круговой очереди элемент очереди действует как круговое кольцо. Работа циклической очереди аналогична линейной очереди, за исключением того факта, что последний элемент соединяется с первым элементом. Его преимущество в том, что память используется лучше. Это связано с тем, что если есть пустое место, т.е. если в определенной позиции в очереди нет элемента, то элемент может быть легко добавлен в эту позицию.
- Приоритетная очередь: эта очередь является особым типом очереди. Его особенность в том, что он упорядочивает элементы в очереди на основе некоторого приоритета. Приоритет может быть чем-то, где элемент с наибольшим значением имеет приоритет, поэтому он создает очередь с убывающим порядком значений. Приоритет также может быть таким, что элемент с наименьшим значением получает наивысший приоритет, поэтому, в свою очередь, он создает очередь с возрастающим порядком значений.
- Dequeue: Dequeue также известен как Double Ended Queue. Как следует из названия, двусторонний означает, что элемент может быть вставлен или удален с обоих концов очереди, в отличие от других очередей, в которых это можно сделать только с одного конца. Из-за этого свойства он может не подчиняться свойству First In First Out.
Применение очереди:
Очередь используется, когда что-то не нужно обрабатывать немедленно, а нужно обрабатывать в порядке «первым пришел – первым вышел » , как при поиске в ширину. Это свойство Queue также делает его полезным в следующих сценариях.
- Когда ресурс используется несколькими потребителями. Примеры включают планирование ЦП, планирование дисков.
- Когда данные передаются асинхронно (данные не обязательно принимаются с той же скоростью, что и отправка) между двумя процессами. Примеры включают буферы ввода-вывода, каналы, файловый ввод-вывод и т. д.
- Очередь может использоваться как важный компонент в различных других структурах данных.
Реализация массива Queue:
Для реализации очереди нам нужно отслеживать два индекса, передний и задний. Мы ставим элемент в очередь сзади и удаляем из очереди элемент спереди. Если мы просто инкрементируем передний и задний индексы, то могут быть проблемы, передний может доходить до конца массива. Решение этой проблемы состоит в том, чтобы увеличить перед и зад по кругу.
Шаги для постановки в очередь:
- Проверить очередь заполнена или нет
- Если заполнено, напечатать переполнение и выйти
- Если очередь не заполнена, увеличьте хвост и добавьте элемент
Шаги для удаления из очереди:
- Проверить очередь пуста или нет
- если пусто, напечатать нижнее заполнение и выйти
- если не пусто, напечатать элемент в начале и увеличить заголовок
Ниже приведена программа для реализации вышеуказанной операции в очереди.
Анализ сложности:
- Сложность времени
Операции | Сложность |
---|---|
Очередь (вставка) | О(1) |
Дек (удаление) | О(1) |
Фронт (Получить фронт) | О(1) |
Задний (получить задний) | О(1) |
- Вспомогательное пространство:
O(N), где N — размер массива для хранения элементов.
Преимущества реализации массива:
- Легко реализовать.
- Можно легко и эффективно управлять большими объемами данных.
- Такие операции, как вставка и удаление, могут выполняться с легкостью, поскольку они следуют правилу «первым пришел — первым вышел».
Недостатки реализации массива:
- Статическая структура данных, фиксированный размер.
- Если в очереди большое количество операций enqueue и dequeue, в какой-то момент (в случае линейного приращения переднего и заднего индексов) мы можем не успеть вставить элементы в очередь, даже если очередь пуста (эта проблема избегается с использованием циклической очереди).