Введение и реализация массива Queue

Подобно стеку, очередь представляет собой линейную структуру данных, которая следует определенному порядку, в котором выполняются операции для хранения данных. Заказ осуществляется в порядке очереди (FIFO) . Можно представить очередь как очередь людей, ожидающих получения чего-либо в последовательном порядке, который начинается с начала очереди. Это упорядоченный список, в котором вставки выполняются с одного конца, известного как задний, а удаления выполняются с другого конца, известного как передний. Хорошим примером очереди является любая очередь потребителей ресурса, в которой потребитель, пришедший первым, обслуживается первым.
Разница между стеками и очередями заключается в удалении. В стеке мы удаляем последний добавленный элемент; в очереди мы удаляем элемент, добавленный последним.

Основные операции с очередью:

• enqueue(): вставляет элемент в конец очереди, т.е. в конец очереди.
• dequeue(): эта операция удаляет и возвращает элемент, находящийся в начале очереди.
• front(): эта операция возвращает элемент на переднем конце, не удаляя его.
• Rear(): Эта операция возвращает элемент в конце, не удаляя его.
• Empty(): Эта операция указывает, пуста ли очередь или нет.
• size(): Эта операция возвращает размер очереди, т.е. общее количество содержащихся в ней элементов.

Типы очередей:

• Простая очередь. Простая очередь, также известная как линейная очередь, является самой простой версией очереди. Здесь вставка элемента, т.е. операция постановки в очередь, происходит на заднем конце, а удаление элемента, т.е. операция удаления из очереди, происходит на переднем конце.
• Круговая очередь: в круговой очереди элемент очереди действует как круговое кольцо. Работа циклической очереди аналогична линейной очереди, за исключением того факта, что последний элемент соединяется с первым элементом. Его преимущество в том, что память используется лучше. Это связано с тем, что если есть пустое место, т.е. если в определенной позиции в очереди нет элемента, то элемент может быть легко добавлен в эту позицию.
• Приоритетная очередь: эта очередь является особым типом очереди. Его особенность в том, что он упорядочивает элементы в очереди на основе некоторого приоритета. Приоритет может быть чем-то, где элемент с наибольшим значением имеет приоритет, поэтому он создает очередь с убывающим порядком значений. Приоритет также может быть таким, что элемент с наименьшим значением получает наивысший приоритет, поэтому, в свою очередь, он создает очередь с возрастающим порядком значений.
• Dequeue: Dequeue также известен как Double Ended Queue. Как следует из названия, двусторонний означает, что элемент может быть вставлен или удален с обоих концов очереди, в отличие от других очередей, в которых это можно сделать только с одного конца. Из-за этого свойства он может не подчиняться свойству First In First Out.

Применение очереди:

Очередь используется, когда что-то не нужно обрабатывать немедленно, а нужно обрабатывать в порядке «первым пришел – первым вышел » , как при поиске в ширину. Это свойство Queue также делает его полезным в следующих сценариях.

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

Реализация массива Queue:

Для реализации очереди нам нужно отслеживать два индекса, передний и задний. Мы ставим элемент в очередь сзади и удаляем из очереди элемент спереди. Если мы просто инкрементируем передний и задний индексы, то могут быть проблемы, передний может доходить до конца массива. Решение этой проблемы состоит в том, чтобы увеличить перед и зад по кругу.

Шаги для постановки в очередь:

1. Проверить очередь заполнена или нет
2. Если заполнено, напечатать переполнение и выйти
3. Если очередь не заполнена, увеличьте хвост и добавьте элемент

Шаги для удаления из очереди:

1. Проверить очередь пуста или нет
2. если пусто, напечатать нижнее заполнение и выйти
3. если не пусто, напечатать элемент в начале и увеличить заголовок

Ниже приведена программа для реализации вышеуказанной операции в очереди.

Анализ сложности:

• Сложность времени

• Вспомогательное пространство:
  O(N), где N — размер массива для хранения элементов.

Преимущества реализации массива:

• Легко реализовать.
• Можно легко и эффективно управлять большими объемами данных.
• Такие операции, как вставка и удаление, могут выполняться с легкостью, поскольку они следуют правилу «первым пришел — первым вышел».

Недостатки реализации массива:

• Статическая структура данных, фиксированный размер.
• Если в очереди большое количество операций enqueue и dequeue, в какой-то момент (в случае линейного приращения переднего и заднего индексов) мы можем не успеть вставить элементы в очередь, даже если очередь пуста (эта проблема избегается с использованием циклической очереди).