Очередь может быть описана как не примитивная линейная структура данных, следующая за порядком FIFO, в котором элементы данных вставляются с одного конца (задний конец) и удаляются с другого конца (передний конец). Другими вариантами очереди являются круговая очередь, очередь с двойным окончанием и приоритетная очередь.
Сравнительная таблица
| Основа для сравнения | Линейная очередь | Круговая Очередь |
|---|---|---|
| основной | Упорядочивает элементы данных и инструкции в последовательном порядке один за другим. | Располагает данные в круговой схеме, где последний элемент связан с первым элементом. |
| Порядок выполнения задания | Задачи выполняются в том порядке, в котором они были размещены ранее (FIFO). | Порядок выполнения задания может измениться. |
| Вставка и удаление | Новый элемент добавляется с задней части и удаляется с передней части. | Вставка и удаление могут быть сделаны в любой позиции. |
| Спектакль | неэффективный | Работает лучше, чем линейная очередь. |
Определение линейной очереди
Линейная очередь является рационально первым по порядку упорядоченным списком. Это так называемый линейный, потому что он напоминает прямую линию, где элементы расположены один за другим. Он содержит однородную коллекцию элементов, в которых новые элементы добавляются на одном конце и удаляются с другого конца. Концепция очереди может быть понята на примере очереди аудитории, ожидающей снаружи кассы, чтобы получить билет в театр. В этой очереди человек присоединяется к заднему концу очереди, чтобы получить билет, и билет выдается в переднем конце очереди.
В очереди выполняется несколько операций
- Сначала очередь инициализируется на ноль (т. Е. Пустая).
- Определите, пуста ли очередь или нет.
- Определите, заполнена очередь или нет.
- Вставка нового элемента с задней части (Enqueue).
- Удаление элемента из передней части (Dequeue).
Очередь может быть реализована двумя способами
- Статически (с использованием массивов)
- Динамически (с помощью указателей)
Ограничение линейной очереди состоит в том, что она создает сценарий, в котором новый элемент не может быть добавлен в очередь, даже если очередь содержит пустые места. Эта ситуация выше проиллюстрирована на рисунке ниже. Здесь задняя часть указывает на последний индекс, в то время как все поля еще пусты, новый элемент добавить нельзя.
Определение круговой очереди
Круговая очередь - это вариант линейной очереди, который эффективно преодолевает ограничение линейной очереди. В циклической очереди новый элемент добавляется в самую первую позицию очереди, если последняя занята и место доступно. Когда дело доходит до линейной очереди, вставка может выполняться только с заднего конца, а удаление - с внешнего. В полной очереди после выполнения серии последовательных удалений в очереди возникает определенная ситуация, когда новый элемент не может быть добавлен дальше, даже если доступно пространство, потому что условие недостаточного заполнения (Rear = max - 1) все еще существует.
Круговая очередь соединяет два конца через указатель, где самый первый элемент идет после последнего элемента. Он также отслеживает переднюю и заднюю части, реализуя некоторую дополнительную логику, чтобы можно было отслеживать элементы, которые должны быть вставлены и удалены. При этом круговая очередь не создает условия переполнения, пока очередь не заполнится в реальном времени.
Некоторые условия, сопровождаемые циклической очередью:
- Фронт должен указывать на первый элемент.
- Очередь будет пустой, если Front = Rear.
- При добавлении нового элемента очередь увеличивается на единицу (Rear = Rear + 1).
- Когда элемент удаляется из очереди, фронт увеличивается на единицу (Front = Front + 1).
Ключевые различия между линейной очередью и круговой очередью
- Линейная очередь представляет собой упорядоченный список, в котором элементы данных организованы в последовательном порядке. В отличие от циклической очереди данные хранятся в циклическом режиме.
- Линейная очередь следует порядку FIFO для выполнения задачи (элемент, добавленный в первую позицию, будет удален в первой позиции). И наоборот, в циклической очереди порядок операций, выполняемых над элементом, может измениться.
- Вставка и удаление элементов фиксируется в линейной очереди, т. Е. Добавление с заднего конца и удаление с внешнего конца. С другой стороны, круговая очередь способна вставлять и удалять элемент из любой точки, пока он не будет занят.
- Линейная очередь тратит впустую пространство памяти, в то время как круговая очередь эффективно использует пространство.
Реализация линейной очереди
Приведенный ниже алгоритм иллюстрирует добавление элементов в очередь:
Очередь нуждается в трех переменных данных, включая один массив для хранения очереди и другую для хранения передней и задней начальной позиции, равной -1.
вставить (элемент, очередь, n, задний) {если (задний == n), то вывести «переполнение очереди»; иначе {тыл = тыл + 1; очередь [задняя часть] = элемент; }} Приведенный ниже алгоритм иллюстрирует удаление элементов в очереди:
delete_circular (элемент, очередь, задний, передний) {если (задний == передний), то выведите «underflow queue»; else {front = front + 1; item = queue [front]; }} Реализация круговой очереди
Алгоритм для интерпретации добавления элемента в круговую очередь:
insert_circular (элемент, очередь, сзади, спереди) {сзади = (сзади + 1) mod n; если (спереди == сзади), то выведите «очередь заполнена»; else {queue [Rear] = элемент; }} Алгоритм объясняет удаление элемента в круговой очереди:
delete_circular (элемент, очередь, сзади, спереди) {если (спереди == сзади), то печатать («очередь пуста»); else {front = front + 1; item = queue [front]; }} Заключение
Линейная очередь неэффективна в определенных случаях, когда элементы должны сдвигаться в свободные места для выполнения операции вставки. По этой причине он имеет тенденцию тратить пространство памяти, в то время как круговая очередь соответствующим образом использует пространство хранения, так как элементы добавляются в любой позиции, если существует пустое пространство.
