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

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

Есть четыре типа очередей:

  • Простая очередь.
  • Круговая очередь.
  • Приоритетная очередь.
  • Двукратная очередь.
  • Круговая двойная очередь.

В этом блоге мы не будем рассматривать очередь приоритетов и подробно обсудим все остальное, поэтому приступим.

Операции и методы очереди

Фронт

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

Задний

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

полон

isFull используется для проверки, заполнена ли очередь. Реализация проста, нам нужно просто проверить, равен ли задний индекс последнему индексу контейнера очереди. Это функция логического типа.

MAX_SIZE = n; // max_size is the maximum size of the queue container 
bool isFull(){
     return rear == MAX_SIZE-1 ;

пусто

isEmpty используется для проверки того, пуста ли очередь. Это функция логического типа. Он возвращает истину, если переднее значение равно -1 или переднее значение больше заднего.

bool isEmpty(){
     return front == -1;
}

Поставить в очередь

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

1) Проверьте условие isFull, так как мы не можем вставить новый элемент в уже заполненную очередь.
if (isFull ())
print («Overflow»);
return;

2) Если очередь не заполнена, нам снова нужно проверить еще два условия.

3) Если передний == -1, тогда мы будем увеличивать как передний, так и задний. Вначале мы инициализируем как передний, так и задний ряд с -1, и если передний равен -1, это означает, что очередь пуста, и мы добавляем первый элемент в очередь, и, следовательно, как передний, так и задний элемент имеют одинаковое значение индекса, то есть 0.

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

5) Наконец, мы просто поместим данные в заднюю часть очереди индекса.
queue [rear] = data;

6) Возврат

Dequeue

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

1) Проверьте условие isEmpty, так как мы не можем удалить элемент из пустой очереди.
if (isEmpty ())
print («Underflow»);
return;

2) Если очередь не пуста, нам снова нужно проверить еще два условия.

3) Если передний == задний, этот случай возникает только в том случае, если в очереди присутствует только один элемент, мы сбросим и передний, и задний, так как после удаления этого последнего элемента очередь будет пустой, мы сделаем это, установив значение передней и сзади до -1.

4) В противном случае мы просто увеличим фронт.

5) Возврат

Реализация кодирования на C ++

Реализация простым массивом

Пустая очередь тоже может быть полной !!!

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

Предположим, мы создали очередь из 8 блоков и теперь добавили 8 элементов, в этом случае очередь заполнена, а задняя часть указывает на индекс 7, если мы удалим несколько элементов, предположим, что 4 элемента из очереди, тогда передняя переменная, которая указывала на 0 теперь указывает на пятый элемент, то есть на индекс 4. Теперь у нас есть 4 пустых блока, но если мы попытаемся добавить новый элемент, мы не сможем этого сделать, потому что задний элемент уже имеет максимально возможный индекс. Таким образом, вы можете видеть, что даже если у нас есть 4 пустых блока, мы столкнулись с переполнением, которое приводит к огромным потерям памяти. Следовательно, нам нужны более эффективные методы для решения этой проблемы.

Как преодолеть?

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

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

Круговая очередь

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

Реализация кругового массива

Мы увидим реализацию кодирования циклической очереди на C ++, и как только я покажу вам код, я объясню все подробно.

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

Очередь STL

Стандартная библиотека шаблонов C ++ имеет отличные встроенные функции и методы, и мы будем их использовать.

  • пусто → Проверить, пуст ли контейнер.
  • размер → Возвращает размер контейнера.
  • front → Доступ к переднему элементу контейнера очереди.
  • назад → Доступ к последнему элементу контейнера очереди.
  • push → Вставить элемент в контейнер очереди ..
  • emplace → Создайте и вставьте элемент в контейнер очереди. .
  • pop → Удалить следующий элемент из контейнера очереди ..
  • swap → поменять местами содержимое контейнера очереди.

Двукратная очередь (Deque)

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

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

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

Deque в STL

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

Итераторы:

  • begin → Вернуть итератор в начало очереди.
  • end → Вернуть итератор в конец контейнера очереди.
  • rbegin → Вернуть обратный итератор к обратному началу очереди.
  • rend → Вернуть обратный итератор в обратный конец контейнера очереди.
  • cbegin → «» Вернуть const_iterator в начало очереди.
  • cend → «» Вернуть const_iterator в конец очереди.
  • crbegin → Вернуть const_reverse_iterator для изменения начала очереди.
  • crend ​​→ Вернуть const_reverse_iterator в обратный конец контейнера очереди.

Вместимость

  • size → Возвращает размер контейнера очереди.
  • max_size → Возвращает максимальный размер контейнера очереди.
  • изменить размер → изменить размер контейнера очереди.
  • пусто → Проверить, пуст ли контейнер от контейнера очереди.
  • shrink_to_fit → «» Уменьшить до размера контейнера очереди.

Доступ к элементу:

  • at → элемент доступа к контейнеру очереди ..
  • front → Доступ к первому элементу контейнера очереди ..
  • назад → Доступ к последнему элементу контейнера очереди ..

Модификаторы:

  • assign → Назначить содержимое контейнера.
  • push_back → Добавить элемент в конец очереди.
  • push_front → Вставить элемент в начало очереди.
  • pop_back → Удалить последний элемент очереди.
  • pop_front → Удалить первый элемент очереди.
  • вставить → Вставить элементы из очереди.
  • erase → Удалить элементы из очереди.
  • поменять местами → поменять местами содержимое очереди.
  • очистить → Очистить содержимое очереди.
  • emplace → Создайте и вставьте элемент в очередь.
  • emplace_front → Создайте и вставьте элемент в начало очереди.
  • emplace_back → Создайте и вставьте элемент в конец очереди.
  • swap → Меняет содержимое двух контейнеров deque.

Вот и конец….

Итак, мы подошли к концу блога, рассмотрели основы простой, двойной, круговой очереди и познакомились с функциями и методами STL для простой очереди и двухсторонней очереди. Надеюсь, вы поняли то, что мы обсуждали, и попытаетесь самостоятельно закодировать все очереди, это еще больше укрепит концепцию.
Если вы считаете, что в блоге чего-то не хватает, дайте мне знать, оставив ответ.

Хорошо, тогда продолжайте учиться и удачного программирования: -)