Структура данных циклической очереди в C++

Структура данных циклической очередиЦиклическая очередь — это расширение базовой очереди, которую мы обсуждали ранее. Циклическая очередь также называют “кольцевой буфер”.

Что такое циклическая очередь в C ++?

Циклическая очередь — это линейная структура данных, которая используется для хранения элементов данных. Она выполняет операции, следуя подходу FIFO (первый вход, первый выход), и последняя позиция в очереди соединяется обратно с первой позицией, образуя круг или кольцо.

Циклическая очередь в C++

На следующей схеме показана циклическая очередь:

Циклическая очередь

На приведенной выше схеме показана циклическая структура данных размером 10. Первые шесть элементов уже находятся в очереди, и мы видим, что первая позиция и последняя позиция соединены. Благодаря такому расположению пространство не тратится впустую, как это происходит в линейной очереди.

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

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

Далее мы расскажем об основных операциях циклической очереди.

Основные операции

Некоторые из основных операций циклической очереди заключаются в следующем:

Front: возвращает начальную позицию в циклической очереди.

Rear: возвращает заднюю позицию в циклической очереди.

Enqueue: enqueue (значение) используется для вставки элемента в циклическую очередь. Элемент всегда вставляется в конец очереди.

Нам нужно выполнить следующую последовательность шагов, чтобы вставить новый элемент в циклическую очередь:

  1. Проверить, заполнена ли циклическая очередь: test ((rear == SIZE-1 && front == 0) || (rear == front-1)) , где ‘SIZE’ — это размер циклической очереди.
  2. Если циклическая очередь заполнена, то отображается сообщение “Очередь заполнена” (Queue is full). Если очередь не заполнена, проверить, является ли (rear == SIZE – 1 && front != 0). Если это верно, то установите rear=0 и вставьте элемент.

Читать также:  Пирамидальная сортировка в C++

Dequeue: Функция удаления из очереди (Dequeue) используется для удаления элемента из очереди. В циклической очереди элемент всегда удаляется из внешнего интерфейса. Ниже приведена последовательность операций удаления из очереди в циклической очереди:

  1. Проверить, пуста ли циклическая очередь: проверить, если (front==-1).
  2. Если она пуста, отобразить сообщение “Очередь пуста”(Queue is empty). Если очередь не пуста, выполнить шаг 3.
  3. Проверить, если (front==rear). Если это верно, то установить front=rear= -1, еще проверить, если (front==size-1), если это верно, то установить front=0 и вернуть элемент.

Демонстрация

В этой части статьи мы подробно рассмотрим добавление / удаление элементов в циклической очереди.

Рассмотрим следующую циклическую очередь из 5 элементов, как показано ниже:

Циклическая очередь из 5 элементов

Далее мы вставляем элемент 1 в очередь:

Элемент 1 в очередь

Далее мы вставляем элемент со значением 3:

Элемент со значением 3

Когда мы вставим элементы для заполнения очереди, представление будет таким, как показано ниже:

Элементы для заполнения очереди

Теперь мы удаляем два элемента, т.е. элемент 1 и элемент 3, из очереди, как показано ниже:

Удаляем два элемента

Затем мы вставляем или ставим в очередь элемент 11 в циклическую очередь, как показано ниже:

Читать также:  Списки инициализаторов в C++

Ставим в очередь элемент 11

Теперь вставим элемент 13 в циклическую очередь. Очередь будет выглядеть так, как показано ниже:

Вставим элемент 13 в циклическую очередь

Видно, что в циклической очереди мы перемещаем или вставляем элементы по кругу. Следовательно, мы можем использовать все пространство очереди, пока оно не заполнится.

Реализация

Давайте реализуем циклическую очередь с помощью C++:

Вывод данных:

Circular Queue elements: 2 4 6 8
Element Dequeued = 2
Element Dequeued = 4
Circular Queue elements: 6 8
Circular Queue elements: 6 8 10 12 14
Queue is Full

Выше показан результат операций циклической очереди. Сначала мы добавляем элементы, а затем удаляем два элемента из очереди. Далее мы вставляем или помещаем в очередь еще три элемента в циклическую очередь. Мы видим, что в отличие от линейной очереди, элементы добавляются в конце очереди.

Реализация связного списка

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

Выводные данные показывают циклическую очередь после операции постановки в очередь, удаления из очереди, а также после второй операции постановки в очередь:

Вывод данных:

Circular Queue elements after enqueue operation: 1 3 5
Dequeued Item: 1
Dequeued Item: 3
Circular Queue elements after two dequeue operation: 5
Circular Queue elements after two enqueue operations: 5 7 9

Следующая реализация — это программа на Java для демонстрации циклической очереди с использованием связного списка:

Читать также:  Класс stringstream в C++

Вывод данных:

Circular Queue elements after Enqueue Operation: 2 4 6
Dequeued Item = 2
Dequeued Item = 4
Circular Queue element aft Dequeue Operation: 6
Circular Queue elements after second Enqueue Operation: 6 8 10

Выводные данные приведенной выше программы аналогичны предыдущей программе.

Применение

Давайте обсудим некоторые применения циклической очереди:

  • Планирование процессора: процесс операционной системы, который требует, чтобы произошло какое-либо событие или завершились некоторые другие процессы для выполнения, часто поддерживающихся в циклической очереди, так что они выполняются один за другим, когда выполняются все условия или когда происходят все события.
  • Управление памятью: использование обычных очередей приводит к потере места в памяти. Использование циклической очереди для управления памятью полезно для оптимального использования памяти.
  • Система светофоров с компьютерным управлением: компьютеризированные сигналы светофора часто добавляются в круговую очередь, чтобы они повторялись по истечении заданного интервала времени.

Итог

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

Мы также рассмотрели основные операции циклической очереди. Циклические очереди в основном полезны для целей планирования и приложений, таких как системы светофоров, где сигналы светятся по очереди.

В нашей следующей статье мы расскажем о двухсторонней очереди, которая называется “deque”.

С Уважением, МониторБанк

Добавить комментарий