очередь c++ пример

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

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

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

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

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

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

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

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

очередь c++ примерНа рисунке слева находятся 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.cpp
Пользователь пожалуйста введите 7 чисел:
6 4 2 1 6 3 6
Первый элемент в очереди: 6
Новый первый элемент (после удаления): 4
Очередь не пуста!
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

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

Как мы говорили выше, очередь можно реализовать через массив. Обычно, если кто-то создает такую очередь, то массив называют 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 — стек. Ее использование вы можете встретить во многих больших проектах.

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




Комментарии к записи “Очередь (queue) в C++: легко и просто!”

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

Ваш адрес email не будет опубликован.

  • Дмитрий:

    Здравствуйте! У меня вопрос: Что если необходимо будет удалить элемент из середины очереди с приоритетом?

    • Дмитрий:

      К сожалению, этого сделать нельзя.
      Данный функционал поддерживает множество (set) и мультимножество (multiset).

  • Полина:

    Здравствуйте. Как надо удалять последний элемент из очереди?

    • Дмитрий:

      Если вам нужно удалить элемент который зашел первым то — pop(). Если же только что вошедший то — никак.

  • Денис:

    Здравствуйте.Могу ли я вызвать методы класса — который является элементом очереди? и как?

    • Дмитрий:

      Вам придется использовать функцию front() и функцию класса. Например — q.front().func().

  • Иван:

    Ошиибкиии в кодеее,Поправь.Спасибо.

  • Василий:

    Добрый день. В начале строки чуть-чуть перепутали терминологию LILO — это термин из морских грузоперевозок. Вы наверно имели ввиду FIFO.

  • Aizada:

    как вычислить сумму элементов очереди?пожалуйста помогите?

    • Дмитрий:

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

  • Максим:

    элемент не может быть «самым первым» xD