Очередь (queue) в C++: легко и просто!
Всем привет! Для решения задач многие программисты используют структуру данных — очередь. Вы наверно когда-то слышали о ней, а возможно и применяли в своей программе.
Мы попытаемся ответить на несколько вопросов: что такое очередь, принцип работы очереди и какая у нее есть разновидность. Поехали!
Эта статья будет полезна не только новичкам, но и уже обросшим программистам 🙂 .
Что такое очередь
Очередь — это структура данных (как было сказано выше), которая построена по принципу LILO (last in — last out: последним пришел — последним вышел). В C++ уже есть готовый STL контейнер — queue
.
В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым.
Чтобы понять принцип работы очереди вы можете представить себе магазинную очередь. И вы стоите посреди нее, чтобы вы оказались напротив кассы, сначала понадобится всех впереди стоящих людей обслужить. А вот для последнего человека в очереди нужно, чтобы кассир обслужил всех людей кроме него самого.
На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!
Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.
Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу.
Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать.
Как создать очередь в С++
Если вы хотите использовать шаблон очереди в C++, то вам сначала нужно подключить библиотеку — <queue>
.
Дальше для объявления очереди нужно воспользоваться конструкцией ниже.
1 |
queue <тип данных> <имя>; |
- Сначала нам нужно написать слова queue.
- Дальше в <тип данных> мы должны указать тот тип, которым будем заполнять нашу очередь.
- И в конце нам остается только указать название очереди.
Вот пример правильного объявления:
1 |
queue <int> q; |
Методы очереди
Метод — это та же самая функция, но она работает только с контейнерами STL. Например, очередь и стек.
Для работы с очередью вам понадобится знать функции: push()
, pop()
, front()
, back()
, empty()
. Кстати, если хотите узнать, как в C++ работают функции и как их правильно использовать в проекте, то можете узнать все это здесь.
- Для добавления в очередь нового элемента нужно воспользоваться функцией —
push()
. В круглых скобках должно находится значение, которое мы хотим добавить. - Если нам понадобилось удалить первый элемент нужно оперировать функцией
pop()
. В круглых скобках уже не чего не нужно указывать, но по правилам они в обязательном порядке должны присутствовать! Эти функции тоже не нуждаются в указании аргумента:empty()
,back()
иfront()
. - Если вам понадобилось обратиться к первому элементу очереди, то вам понадобится функция
front()
. - Чтобы обратиться к последнему элементу в очереди вам поможет функция
back()
. - Чтобы узнать пуста ли очередь нужно воспользоваться функцией
empty()
.- Если ваша очередь пуста — возвратит
true
. - Если же в ней что-то есть — возвратит
false
.
- Если ваша очередь пуста — возвратит
Ниже мы использовали все выше перечисленные методы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <queue> // подключили библиотеку queue using namespace std; int main() { setlocale(LC_ALL,"rus"); queue <int> q; // создали очередь q cout << "Пользователь, пожалуйста введите 7 чисел: " << endl; for (int h = 0; h < 7; h++) { int a; cin >> a; q.push(a); // добавляем в очередь элементы } cout << endl; cout << "Самый первый элемент в очереди: " << q.front() << endl; // выводим первый // элемент очереди q.pop(); // удаляем элемент из очереди cout << "Новый первый элемент (после удаления): " << q.front() << endl; if (!q.empty()) cout << "Очередь не пуста!"; // проверяем пуста ли очередь (нет) system("pause"); return 0; } |
Давайте посмотрим, как будет выглядеть консоль при запуске:
Создание очереди с помощью массива
Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют queue
. Мы бы также назвали массив, но это уже зарезервированное слова в C++. Поэтому его назовем так, как назвали выше шаблон очереди — q
.
Для реализации нам понадобится создать две дополнительные переменные start
и ends
. start
будет указывать на первый элемент очереди, a ends
на последний элемент.
Чтобы обратится к последнему элементу нам придется использовать эту конструкцию — queue[ends]
. Обращение к первому элементу будет выглядеть аналогично queue[start]
.
Если понадобится удалить элемент из очереди, то придется всего лишь уменьшить переменную start
на один.
«А как же проверить пуста ли очередь?» — спросите вы. Для этого мы просто проверим условие start == ends
:
- Если результатом условия будет
true
, то очередь пуста. - Если же результат условия
false
, значит очередь чем-то заполнена.
Ниже находится живой пример создания такой очереди:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
setlocale(LC_ALL,"rus"); int q[7]; // создали массив q int start = 0, ends = 0; // создали переменные начала и конца очереди cout << "Пользователь, пожалуйста введите 7 чисел: " << endl; for (int h = 0; h < 7; h++) { int a; cin >> a; int a; cin >> a; q[ends++] = a; // добавляем элементы в очередь(массив) } cout << "Самый первый элемент в очереди: " << q[start] << endl; start++; // удаляем первый элемент(увеличиваем индекс начала очереди на 1) cout << "Новый первый элемент (после удаления): " << q[start] << endl; cout << "Самый последний элемент в очереди: " << q[ends - 1]; // выводим последний // элемент очереди if (start != ends) cout << "Очередь заполнена!"; // проверяем пуста ли очередь |
Очередь с приоритетом
Очередь с приоритетом (priority_queue) — это обычная очередь, но в ней новый элемент добавляется в то место, чтобы очередь была отсортирована по убыванию.
Так самый большой элемент в приоритетной очереди будет стоять на первом месте.
Для объявления шаблона очереди с приоритетом нужно использовать конструкцию ниже:
1 |
priority_queue <тип данных> <имя>; |
- В начале нужно написать
priority_queue.
- Потом в скобках указать тип данных, который будет находится в очереди.
- И конечно же в самом конце мы должны дать ей имя.
Для добавления элемента в очередь с приоритетом мы должны использовать функцию push()
. Но чтобы обратится к первому элементу должны использоваться именно функция — top()
(как и в стеке). А не функция — front()
.
Также нельзя использовать функцию back()
для обращения к последнему элементу. Для приоритетной очереди она также не работает, как функция front()
.
Вот пример использования очереди с приоритетом в программе:
1 2 3 4 5 6 7 8 9 10 11 12 |
setlocale(LC_ALL,"rus"); priority_queue <int> priority_q; // объявляем приоритетную очередь cout << "Введите 7 чисел: " << endl; for (int j = 0; j < 7; j++) { int a; cin >> a; priority_q.push(a); // добавляем элементы в очередь } // выводим первый cout << "Первый элемент очереди: " << priority_q.top(); // элемент |
Какой вид создания очереди использовать
Сегодня мы изучили два способа реализации очереди:
- Реализация через шаблон C++.
- Реализация через массив.
Лично мы всегда используем первый способ реализации очереди. Он работает быстрее чем второй способ и реализация совсем простая.
Упражнение
Если вы хотите усвоить данный материал то:
- Создайте очередь.
- Предложите пользователю ввести 7 чисел.
- Добавьте все 7 чисел в очередь.
- Выведите одно число.
- Удалите 1 число из очереди.
- Проверьте пуста ли очередь.
Мы рады, если в этой статье вы узнали что-то новое!
Мы советуем вам изучить еще одну важную структуру данных STL — стек. Ее использование вы можете встретить во многих больших проектах.
Если есть вопрос, то пиши в комментарии, мы с радостью вам ответим. Удачи!
Здравствуйте! У меня вопрос: Что если необходимо будет удалить элемент из середины очереди с приоритетом?
К сожалению, этого сделать нельзя.
Данный функционал поддерживает множество (set) и мультимножество (multiset).
Здравствуйте. Как надо удалять последний элемент из очереди?
Если вам нужно удалить элемент который зашел первым то — pop(). Если же только что вошедший то — никак.
Здравствуйте.Могу ли я вызвать методы класса — который является элементом очереди? и как?
Вам придется использовать функцию front() и функцию класса. Например — q.front().func().
Ошиибкиии в кодеее,Поправь.Спасибо.
Спасибо, исправили!