Очередь (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>
.
Дальше для объявления очереди нужно воспользоваться конструкцией ниже.
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().
Ошиибкиии в кодеее,Поправь.Спасибо.
Спасибо, исправили!
Добрый день. В начале строки чуть-чуть перепутали терминологию LILO — это термин из морских грузоперевозок. Вы наверно имели ввиду FIFO.
Спасибо, исправил.
как вычислить сумму элементов очереди?пожалуйста помогите?
Вам нужно пройтись по очереди, суммируя элементы, пока очередь не станет пустой.
элемент не может быть «самым первым» xD