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

Структура данных очередиОчередь — это базовая структура данных, такая же, как и стек. В отличие от стека, который использует подход LIFO, очередь (queue) использует подход FIFO (первый вход, первый выход). При таком подходе первый элемент, добавляемый в очередь, является первым элементом, удаляемым из очереди. Как и стек, очередь также является линейной структурой данных.

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

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

Очередь расположена линейно

На схеме есть два указателя, то есть “передний” и “задний” очереди. Когда очередь пуста, то обоим указателям присваивается значение -1.

Указатель «rear» (задний) — это место, откуда элементы вставляются в очередь. Операция добавления / вставки элементов в очередь называется “постановкой в очередь” (enqueue).

Указатель «front» (передний) — это место, откуда элементы удаляются из очереди. Операция по удалению / удалению элементов из очереди называется “удалением из очереди” (dequeue).

Когда значение заднего указателя равно size-1, мы говорим, что очередь заполнена. Когда начальное значение равно нулю, очередь пуста.

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

Структура данных очереди включает в себя следующие операции:

  • EnQueue: добавляет элемент в очередь. Добавление элемента в очередь всегда выполняется в конце очереди.
  • DeQueue: удаляет элемент из очереди. Элемент всегда удаляется из очереди в начале очереди.
  • isEmpty: проверяет, пуста ли очередь.
  • isFull: проверяет, заполнена ли очередь.
  • peek: возвращает элемент в начало очереди, не удаляя его.

Читать также:  Классы и объекты в C++

Постановка в очередь

В этом процессе выполняются следующие шаги:

  • Проверить, заполнена ли очередь.
  • Если заполнена, выдать ошибку переполнения и завершить работу.
  • В противном случае увеличить значение ‘rear’.
  • Добавить элемент в местоположение, указанное ‘rear’.
  • Выполнено успешно.

Удаление из очереди

Операция удаления из очереди состоит из следующих шагов:

  • Проверить, пуста ли очередь.
  • Если пуста, отобразить ошибку переполнения и завершить работу.
  • В противном случае элемент доступа указывается с помощью ‘front’ .
  • Увеличить «начало», чтобы указать на следующие доступные данные.
  • Выполнено успешно.

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

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

Пустая очередь

Это пустая очередь, и, таким образом, мы имеем задний указатель и пустую очередь, равную -1.

Далее мы добавляем 1 в очередь, и в результате задний указатель перемещается вперед на одно местоположение:

Задний указатель

На следующей схеме мы добавляем элемент 2 в очередь, перемещая задний указатель вперед на еще одно местоположение (приращение):

Перемещение заднего указателя

На следующей схеме мы добавляем элемент 3 и перемещаем задний указатель на 1:

Добавляем элемент 3

На этом этапе задний указатель имеет значение 2, в то время как передний указатель находится на нулевом местоположении.

Далее мы удаляем элемент, на который указывает передний указатель. Поскольку передний указатель равен 0, удаляемый элемент равен 1.

Передний указатель равен 0

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

Реализация массива для очереди

Давайте реализуем структуру данных очереди, используя C++:

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

Читать также:  Полиморфизм времени выполнения в C++

Queue is empty!!
Queue created:
10 20 30 40 50
Queue is full!!
Front = 0
Queue elements : 10 20 30 40 50
Rear = 4
Deleted => 10 from myqueue
Front = 1
Queue elements: 20 30 40 50
Rear = 4

Приведенная выше реализация показывает очередь, представленную в виде массива. Мы указываем max_size для массива, также определяем операции постановки в очередь и удаления из очереди, а также операции isFull и isEmpty.

Ниже приведена реализация на Java структуры данных очереди:

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

Queue created as:
10 20 30 40
Element 10 dequeued from queue
Front item is 20
Rear item is 40

Приведенная выше реализация аналогична реализации на C++.

Далее давайте реализуем очередь на C++, используя связный список.

Реализация связного списка для очереди:

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

Queue Created:
10 20 30 40 50
Element deleted from queue is: 10
Queue after one deletion:
20 30 40 50

Стек или очередь

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

Стек Очередь
Использует подход LIFO (последний вход, первый выход). Использует подход FIFO (первый вход, первый выход).
Элементы добавляются или удаляются только с одного конца, называемого «Вершиной стека». Элементы добавляются из “rear” конца очереди и удаляются из “front» части очереди.
Основными операциями для стека являются “push” и “pop”. Основными операциями для очереди являются “enqueue” и “dequeue”.
Мы можем выполнять все операции со стеком, поддерживая только один указатель для доступа к вершине стека. В очередях нам нужно поддерживать два указателя: один для доступа к началу очереди, а второй для доступа к задней части очереди.
Стек в основном используется для решения рекурсивных задач. Очереди используются для решения проблем, связанных с упорядоченной обработкой.

Читать также:  Согласование приводов и датчиков с контроллером робота

Применение queue (очереди)

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

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

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

Итог

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

В нашей следующей статье мы поговорим о структуре данных приоритетной очереди в C++.

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

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