Очередь (queue) в C++: реализация и использование

Очередь — это набор элементов, где первый элемент, добавленный в список, должен быть первым элементом, который будет удален следующим. Таким образом, по мере добавления предметов в коллекцию она увеличивается в размерах, то есть в длину. Всякий раз, когда какой-либо элемент должен быть удален, он должен быть добавлен первым. Если элементы удаляются непрерывно, то следующий удаляемый является вторым элементом; третий потом удаляется и т. д.

После удаления первого элемента исходного списка второй становится первым элементом. После удаления второго элемента третий становится первым и так далее.

Хороший пример очереди из реальной жизни — это когда люди выстраиваются в очередь, чтобы дождаться обслуживания или товара. Первый человек обслуживается первым перед последним. Однако очередь, о которой говорилось в этом руководстве, — это программная очередь, разработанная на C ++.

FIFO

FIFO означает «первым пришёл — первым ушёл». Это еще один способ оценить очередь. Это означает, что первый элемент, который попадает в список, будет первым элементом, который будет удален всякий раз, когда удаление должно происходить. Начало списка называется головным или передним; конец списка называется спиной или хвостом.

Основные операции

Программная очередь должна иметь как минимум следующие операции:

push

Эта операция добавляет новый элемент в конец очереди. Эта операция официально называется enqueue.

shift

Эта операция удаляет первый элемент очереди, а второй элемент становится новым первым элементом. Эта операция официально называется удалением из очереди. В C ++ это называется pop.

В этой статье объясняется, как использовать структуру данных очереди C ++. Вы должны знать указатели и ссылки C ++, чтобы понять остальную часть этой статьи.

Класс и объекты

Класс — это набор переменных и функций, которые работают вместе, где переменным не присвоены значения. Когда переменным присваиваются значения, класс становится объектом. Различные значения, присвоенные одному и тому же классу, приводят к разным объектам; то есть разные объекты относятся к одному классу с разными значениями. Считается, что создание объекта из класса создает экземпляр объекта.

Имя, очередь, это класс. Объект, созданный из класса очереди, имеет имя, выбранное программистом.

Функция, принадлежащая классу, необходима для создания экземпляра объекта из класса. В C ++ эта функция имеет то же имя, что и имя класса. Объекты, созданные (экземпляры) из класса, имеют разные имена, данные им программистом.

Создание объекта из класса означает создание объекта; это также означает создание экземпляра.

Программа на C ++, использующая класс очереди, начинается со следующих строк вверху файла:

#include <iostream>
#include <squeue>
using namespace std;

Первая строка предназначена для ввода / вывода. Вторая строка позволяет программе использовать все функции класса очереди. Третья строка позволяет программе использовать имена в стандартном пространстве имен.

Перегрузка функции

Когда две или более разных сигнатур функций имеют одно и то же имя, это имя считается перегруженным. Когда вызывается одна функция, количество и тип аргументов определяют, какая функция фактически выполняется.

Строительство

queue<type> name()

Следующее объявление создает экземпляр очереди с именем que типа int.

queue<int> que;

Очередь пуста. Объявление начинается с зарезервированного слова «очередь», за которым следуют угловые скобки с типом данных. Затем у вас есть имя программиста для очереди.

Конструирование с использованием списка инициализаторов

Следующее определение показывает, как создать очередь со списком инициализаторов:

queue<float> que({1.1, 2.2, 3.3, 4.4});

Уничтожение очереди

Чтобы уничтожить очередь, просто отпустите ее.

Доступ к элементу очереди

push(value)

Очередь — это список «первым пришёл — первым обслужен». Итак, каждое значение добавляется с обратной стороны. Следующий сегмент кода создает пустую очередь, после которой сзади добавляются пять значений с плавающей запятой:

queue<float> que;

que.push(1.1);
que.push(2.2);
que.push(3.3);
que.push(4.4);
que.push(5.5);

size () const

Это возвращает количество элементов в очереди. Следующий код иллюстрирует:

queue<float> que;
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.size() << ‘\n‘;

Выход 5.

front()

Это возвращает ссылку на первый элемент очереди без удаления элемента. Результатом следующего кода является 1.1.

queue<float> que;
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.front() << ‘\n‘;

Элемент не удаляется из очереди.

front() const

Когда конструкции очереди предшествует const, выражение «front () const» выполняется вместо «front ()». Например, он используется в следующем коде.

const queue<float> que ({1.1, 2.2, 3.3, 4.4, 5.5});
cout << que.front() << ‘\n‘;

Возвращается постоянная ссылка. Элемент не удаляется из вектора. Элементы очереди изменить нельзя.

back()

Это возвращает ссылку на последний элемент очереди, не удаляя элемент. Результатом следующего кода будет 5.5.

queue<float> que;
que.push(1.1); que.push(2.2); que.push(3.3); que.push(4.4); que.push(5.5);
cout << que.back() << ‘\n‘;

back() const

Когда конструкции очереди предшествует const, выражение «back () const» выполняется вместо «back ()». Например, он используется в следующем коде.

const queue<float> que ({1.1, 2.2, 3.3, 4.4, 5.5});
cout << que.back() << ‘\n‘;

Возвращается постоянная ссылка. Элемент не удаляется из очереди. С предыдущей константой для построения очереди элементы в очереди не могут быть изменены.

Емкость очереди

size() const

— см. Выше

empty() const

Это возвращает 1 для истины, если в очереди нет элементов, или 0 для false, если очередь пуста. Следующий код иллюстрирует это:

queue<float> que1 ({1.1, 2.2, 3.3, 4.4, 5.5});
cout << que1.empty() << ‘\n‘;
queue<float> que2;
cout << que2.empty() << ‘\n‘;

Результат:

0
1

Модификаторы очереди

pop()

Очередь — это FIFO, поэтому любой элемент, который необходимо удалить, должен быть удален из верхней части (заголовка) очереди. Эта функция-член удаляет первый элемент, не возвращая его. Следующий код иллюстрирует это:

queue<float> que ({1.1, 2.2, 3.3, 4.4, 5.5});
cout << que.front() << ‘\n‘;
que.pop();
cout << que.size() << ‘\n‘;

Результат:

1,1
4

a.swap(b)

Две очереди можно поменять местами, как показано в этом сегменте кода:

queue <float> que1({1.1, 2.2, 3.3, 4.4, 5.5});
queue <float> que2({10, 20});
que1.swap(que2);
cout << «First element and size of que1:
«<< que1.front() <<«, «<< que1.size() << ‘\n‘;
cout << «First element and size of que2 «<<
que2.front() <<«, «<< que2.size() << ‘\n‘;

Результат:

Первый элемент и размер que1: 10, 2

Первый элемент и размер que2: 1.1, 5

Обратите внимание, что при необходимости длина очереди увеличивается. Кроме того, значения, у которых не было замен, заменяются некоторым значением по умолчанию. Типы данных должны быть одного типа.

Операторы равенства и отношения для очередей

Для обычных символов в C ++ в возрастающем порядке числа идут перед прописными буквами, которые идут перед строчными буквами. Пробел стоит перед нулем и всеми ними.

Операторы равенства

Возвращает 1 для истины и 0 для ложи.

The == Operator

Возвращает 1, если две очереди имеют одинаковый размер и соответствующие элементы равны; в противном случае возвращается 0. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 == que2;
cout << num << ‘\n‘;

Результат: 0.

The != Operator

— противоположное вышеуказанному. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 != que2;
cout << num << ‘\n‘;

Результат: 1.

Операторы отношения

Возвращает 1 для истины и 0 для ложи.

The < Operator

Возвращает 1, если первая очередь является начальным подмножеством второй очереди, причем элементы двух равных частей одинаковы и находятся в одном порядке. Если обе очереди имеют одинаковый или разные размеры и перемещаются слева направо, в первой очереди встречается элемент, который меньше соответствующего элемента во второй очереди, то все равно возвращается 1. В противном случае возвращается 0. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 < que2;
cout << num << ‘\n‘;

Вывод 1. <не включает случай, когда размер и порядок совпадают.

The > Operator

— противоположное вышеуказанному. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 > que2;
cout << num << ‘\n‘;

Выход: 0

The <= Operator

— то же, что и <, но включает случай, когда размер и порядок совпадают. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 <= que2;
cout << num << ‘\n‘;

Выход: 1

The >= Operator

— противоположное вышеуказанному. Пример:

queue <const char*> que1({«kind», «something else»});
queue <const char*> que2({«wicked»});
int num = que1 >= que2;
cout << num << ‘\n‘;

Выход: 0

Класс и его экземпляры

Значение относится к типу данных, как созданный объект относится к классу. Конструкция очереди также может принимать класс как тип данных. Следующая программа иллюстрирует это:

#include <iostream>

#include <queue>
using namespace std;
class TheCla
{
public:
int num;
static char ch;
void func (char cha, const char *str)
{
cout << «There are « << num << » books worth « << cha << str << » in the store.» << ‘\n‘;
}
static void fun (char ch)
{
if (ch == ‘a’)
cout << «Official static member function» << ‘\n‘;
}
};
int main()
{
TheCla obj1; TheCla obj2; TheCla obj3; TheCla obj4; TheCla obj5;
queue <TheCla> que;
que.push(obj1); que.push(obj2); que.push(obj3); que.push(obj4); que.push(obj5);
cout << que.size() << ‘\n‘;
return 0;
}

Выход 5.

Связанный список

Список очереди технически называется связанным списком. Для очереди существует два типа связанных списков: односвязный список и двусвязный список.

Элемент односвязного списка может быть реализован структурой из двух членов. Один член содержит указатель на следующий элемент, а другой элемент содержит данные (в единственном числе для данных).

Элемент двусвязного списка может быть реализован структурой из трех членов. Средний элемент содержит данные, а первый и третий элементы содержат указатели на свои смежные элементы.

Приложения очереди

Очередь — это структура данных, работающая в порядке очереди. В вычислениях бывают ситуации, когда данные поступают в виде очереди, что требует поведения «первым пришел — первым обслужен».

Совместное использование компьютерных ресурсов

Ресурс на компьютере — это любой физический или виртуальный компонент с ограниченной доступностью. К ним относятся ЦП, видеокарта, жесткий диск и память. Для совместного использования такого ресурса нужна очередь.

Обработка прерываний

Периферийные устройства компьютера должны время от времени прерывать работу компьютера. Прерывания должны обрабатываться так же, как они поступили. Для этого нужна очередь.

Управляйте информацией

Очередь может использоваться, например, для управления файлами приложения для задания, если файлы хранятся на компьютере.

Заключение

Очередь — это структура данных списка, которая является либо односвязным списком, либо двусвязным списком. Как правило, первый элемент, который входит в список, выходит из него первым. C ++ предоставляет структуру данных очереди в своей стандартной библиотеке. Категории функций-членов и операторов, доступных для этой структуры, включают построение очереди, доступ к элементам очереди, емкость очереди, модификаторы очереди и операторы перегруженной очереди.

Любая структура данных очереди должна обеспечивать как минимум функции-члены push () и pop (). push () означает отправку нового элемента в конец очереди; а pop () означает удаление элемента, находящегося в начале очереди. К сожалению, в C ++ эти функции не возвращают выдаваемое или выталкиваемое значение. Итак, чтобы узнать последний элемент перед нажатием, необходимо использовать дополнительную функцию back (); и чтобы узнать первый элемент перед появлением, необходимо использовать дополнительную функцию front ().

Значение относится к типу данных, как созданный объект относится к классу. Таким образом, конкретный класс можно использовать в качестве типа данных для создания экземпляра шаблона очереди. Разные объекты класса становятся разными значениями класса.

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