Очередь (queue) в C++: легко и просто!

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

Мы попытаемся ответить на несколько вопросов: что такое очередь, принцип работы очереди и какая у нее есть разновидность. Поехали!

Эта статья будет полезна не только новичкам, но и уже обросшим программистам 🙂 .

• Как создать очередь
• Функции очереди
• Как создать очередь через массив
• Очередь с приоритетом

Что  такое очередь

Очередь — это структура данных (как было сказано выше), которая построена по принципу FILO (last in — last out: первым пришел — последним вышел). В C++ уже есть готовый STL контейнер — queue.

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

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

На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!

Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.

Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу.

Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать.

Как создать очередь в С++

Если вы хотите использовать шаблон очереди в C++, то вам сначала нужно подключить библиотеку — <queue>.

Дальше для объявления очереди нужно воспользоваться конструкцией ниже.

• Сначала нам нужно написать слова queue.
• Дальше в <тип данных> мы должны указать тот тип, которым будем заполнять нашу очередь.
• И в конце нам остается только указать название очереди.

Вот пример правильного объявления:

Методы очереди

Метод — это та же самая функция, но она работает только с контейнерами STL. Например, очередь и стек.

Для работы с очередью вам понадобится знать функции: push(), pop(), front(), back(), empty(). Кстати, если хотите узнать, как в C++ работают функции и как их правильно использовать в проекте, то можете узнать все это здесь.

1. Для добавления в очередь нового элемента нужно воспользоваться функцией — push(). В круглых скобках должно находится значение, которое мы хотим добавить.
2. Если нам понадобилось удалить первый элемент нужно оперировать функцией pop(). В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать! Эти функции тоже не нуждаются в указании аргумента: empty(), back() и front().
3. Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция front().
4. Чтобы обратиться к последнему элементу в очереди вам поможет функция back().
5. Чтобы узнать пуста ли очередь нужно воспользоваться функцией empty().
   • Если ваша очередь пуста — возвратит true.
   • Если же в ней что-то есть — возвратит false.

Ниже мы использовали все выше перечисленные методы:

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

Создание очереди с помощью массива

Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют queue.  Мы бы также назвали массив, но это уже зарезервированное слова в C++. Поэтому его назовем так, как назвали выше шаблон очереди — q.

Для реализации нам понадобится создать две дополнительные переменные start и ends. start будет указывать на первый элемент очереди, a ends на последний элемент.

Чтобы обратится к последнему элементу нам придется использовать эту конструкцию — queue[ends]. Обращение к первому элементу будет выглядеть аналогично queue[start].

Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start на один.

«А как же проверить пуста ли очередь?» — спросите вы. Для этого мы просто проверим условие start == ends:

1. Если результатом условия будет true, то очередь пуста.
2. Если же результат условия false, значит очередь чем-то заполнена.

Ниже находится живой пример создания такой очереди:

Очередь с приоритетом

Очередь с приоритетом (priority_queue) — это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию.

Так самый большой элемент в приоритетной очереди будет стоять на первом месте.

Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже:

• В начале нужно написать priority_queue.
• Потом в скобках указать тип данных, который будет находится в очереди.
• И конечно же в самом конце мы должны дать ей имя.

Для добавления элемента в очередь с приоритетом мы должны использовать функцию push(). Но чтобы обратится к первому элементу должны использоваться именно функция — top() (как и в стеке). А не функция — front().

Также нельзя использовать функцию back() для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front().

Вот пример использования очереди с приоритетом в программе:

Какой вид создания очереди использовать

Сегодня мы изучили два способа реализации очереди:

• Реализация через шаблон C++.
• Реализация через массив.

Лично мы всегда используем первый способ реализации очереди. Он работает быстрее чем второй способ и реализация совсем простая.

Упражнение

Если вы хотите усвоить данный материал то:

1. Создайте очередь.
2. Предложите пользователю ввести 7 чисел.
3. Добавьте все 7 чисел в очередь.
4. Выведите одно число.
5. Удалите 1 число из очереди.
6. Проверьте пуста ли очередь.

Мы рады, если в этой статье вы узнали что-то новое!

Мы советуем вам изучить еще одну важную структуру данных STL — стек. Ее использование вы можете встретить во многих больших проектах.

Если есть вопрос, то пиши в комментарии, мы с радостью вам ответим. Удачи!