Разработка программного обеспечения требует от программиста использования различных инструментов, библиотек, а также структурных элементов. Некоторые задачи предусматривают применение так называемых очередей. Соответствующий элемент встречается в C, С++, C# и других языках разработки.
Далее предстоит познакомиться с компонентом queue C более подробно. Предложенные материалы ориентированы на широкую публику. Они подойдут как разработчикам-новичкам, так и более опытным специалистам.
Очередь – это…
Очередь – структура данных, которая содержит в своем составе один или несколько элементов одного и того же типа. Работает она по принципу FIFO («first in – first out» или «первый вошел – первый вышел»). Отличается от списков и массивов тем, что не поддерживает произвольного доступа к своим элементам. Чтение рассматриваемого «инструмента» осуществляется с первого элемента и до самого конца по порядку.
Стоит обратить внимание на то, что в процессе разработки в очередь нельзя поместить новый элемент произвольно. В данную структуру очередные составляющие записываются только в самый конец. Каждая новая запись заменит последний элемент. В C++ для реализации рассматриваемого компонента используется готовый STL-контейнер. Он называется queue.
Принцип работы
При использовании enqueue первый элемент очереди (тот, что вошел первым), тоже выйдет самым первым. Так, если программист добавит 4 составляющие, первый добавленный «уйдет» тоже первым.
Для того, чтобы лучше разобраться в принципах работы рассматриваемого элемента разработки, можно представить себе пример из реальной жизни. А именно – очередь в магазине. Покупатель стоит посреди нее. Чтобы оказать напротив кассы, сначала требуется дождаться обслуживания всех впереди стоящих посетителей. Для последнего человека в очереди» требуется, чтобы кассир «поработал» со всеми, кроме него самого.
Вот – наглядный пример enqueue:
Здесь:
- Расположены 7 чисел.
- Если требуется извлечь данные, делать это придется в том же порядке, в котором они располагаются на рисунке выше.
- Для получения элемента со значением «4» сначала обслуживается 2.
- В стеке поддерживается функция peek, которая позволяет обращаться к элементам по их индексам. В шаблоне enqueuer невозможно обратиться к определенной составляющей.
- Доступ ко всем элементам может быть реализован через массив.
Создание
Очередь в C требует предварительного подключения библиотеки <queue>. Далее происходит объявление самой структуры. Для этого разработчику требуется использовать такую форму представления:
Здесь:
- С начала пишется ключевое слово enqueue.
- Далее в <тип данных> указывает тип, которым будет заполнена пустая очередь.
- В самом конце объявляется имя (название) структуры.
Пример: queue int t. Соответствующая запись указывает на создание очереди с целочисленными компонентами, которая называется t.
Методы
Метод в C++ – это функция, которая работает с STL-контейнерами. Сюда можно отнести не только очереди, но и стеки.
Для работы с рассматриваемой информационной структурой требуется запомнить несколько функций:
- Push. Добавляет в структуру новый элемент. В круглых скобках указывается значение, которое вносится в queue.
- Pop. С его помощью удаляем первый компонент в записи. В скобках ничего не указывается. Согласно действующим правилам C++, они все равно должны присутствовать в методе.
- Front. Используется для обращения к первому компоненту в информационной структуре.
- Back. Требуется, чтобы обратиться к последней составляющей очереди.
- Empty. Используется, чтобы определить, есть ли в рассматриваемой структуре то или иное количество элементов. Если queue пустая, результат вернется в виде true. В противном случае система выдаст false.
Вот – наглядный пример использования всех перечисленных методов:
Выше можно увидеть результат, который отобразится на экране после запуска предложенного фрагмента.
Создание через массивы
Очереди в C ++ могут быть созданы при помощи массива. Обычно он называется queue. В C++ соответствующее слово является зарезервированным, поэтому далее будет использоваться имя q.
Для реализации потребуется использовать две переменные:
- start – для указания первого компонента (int i) в очереди;
- ends – последняя составляющая структуры.
Для обращения к последнему компоненту предстоит использовать конструкций queue [ends], а к первому – queue [start].
Если необходимо стереть элемент из очереди, переменная start уменьшается на единицу. Для проверки на пустоту используется условие start == ends.
Выше – пример реализации очереди через массив с использованием нескольких методов.
Приоритеты
В C++ поддерживаются очереди с приоритетом. В ней новый элемент будет добавляться так, чтобы очередь была отсортирована по убыванию. Самый большой компонент расположится в начале, маленький – в конце.
Синтаксическая форма записи в данном случае окажется такой:
Здесь сначала пишется ключевое слово, затем – тип используемых данных, а после – имя структуры. Для добавления элемента используется push. Чтобы обратиться к первому компоненту очереди используется top (как в случае со стеками).
Вот пример очереди с приоритетом:
Необходимо запомнить – функция back() для обращения к последнему компоненту информационной структуры не используется. То же самое касается front().
