Способы реализации очереди с

BestProg

Пример реализации очереди с приоритетами для шаблонного класса. Реализация в виде динамического массива

Перед изучением данной темы рекомендуется ознакомиться со следующей темой:

Содержание

Поиск на других ресурсах:

1. Способы реализации очереди с приоритетами

Очередь с приоритетами может быть реализована одним из двух способов:

• как очередь с приоритетным включением (рисунок 1). При этом способе элемент добавляется в очередь в соответствии с его приоритетом. Вытягивается элемент обычным способом – от начала очереди;
• как очередь с приоритетным исключением (рисунок 2). При этом способе элемент добавляется в конец очереди а вытягивается в соответствии с его приоритетом. В случае равенства приоритетов, первым вытягивается тот элемент, который был первым размещен в очереди (элемент, более близкий к началу очереди).

Рисунок 1. Очередь с приоритетным включением

Рисунок 2. Очередь с приоритетным исключением

2. Пример реализации очереди с приоритетами для шаблонного класса в виде динамического массива

2.1. Общее описание работы программы

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

В классе QueueP объявляются:

• A – динамический массив элементов типа T . Эти элементы образовывают очередь;
• P – динамический массив приоритетов каждого элемента из массива A . Элементу A[0] соответствует приоритет P[0] , элементу A[1] соответствует приоритет P[1] и т.д. Количество элементов в массивах A и P одинаково;
• count – текущее количество элементов в очереди;
• конструктор по умолчанию QueueP() ;
• конструктор копирования QueueP(const QueueP&) ;
• деструктор

QueueP() ;

оператор копирования operator=(const QueueP&) ;

функция Push() , добавляющая новый элемент в очередь;

функция Pop() , вытягивающая элемент из очереди;

функция Clear() – реализующая очистку очереди;

функция Count() – возвращает количество элементов в очереди.

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

2.2. Исходный код программы

Исходный код программы, которая реализует класс QueueP следующий.

Источник

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

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

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

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

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

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

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

push

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

shift

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

push(value)

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

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 ‘ ;

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 ()». Например, он используется в следующем коде.

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

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 ()». Например, он используется в следующем коде.

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

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

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 ‘ ;

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

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 ‘ ;

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 ‘ ;

The != Operator

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

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

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

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

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

Вывод 1. Читайте также: Случайный выбор из списка Python

The > Operator

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

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

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

The >= Operator

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Источник

Читайте также:  Способы повышения концентрации веществ