что такое структура очереди

Типы очередей в структуре данных

Простая очередь

Как видно из самого названия, простая очередь позволяет нам просто выполнять операции. то есть вставка и удаление выполняются аналогичным образом. Вставка происходит в конце (конце) очереди, а удаления выполняются в начале (начале) списка очереди.

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

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

Круговая Очередь

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

Очередь приоритетов

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

Хотя удаление выполняется в соответствии с номером приоритета (элемент данных с наивысшим приоритетом удаляется первым), вставка выполняется только по порядку.

Двусторонняя очередь (Dequeue)

Двусторонняя очередь позволяют операции вставки и удаления с обоих концов (передний и задний) очереди.

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

Источник

Динамическая структура данных очередь

Содержание:

Одной из моих генеральный компетенций является исследование различных популярных динамических структур данных. Уже на протяжении 10 лет я помогаю всем желающим разобраться с такой структурой данных, как очередь. Программирую структуру данных очередь на одном из следующих языков программирования: Pascal, Delphi, C, C++, C#, Basic, VBA.

Очень часто ко мне обращаются студенты из технических вузов РФ и повествуют о том, что у них в некоторых лабораторных требуется провести реализацию структуры данных очередь. Вы должны понимать, что подобная реализация не может стоить очень дешево! После ознакомления с постановкой задачи, я начинаю задавать клиенту уточняющие вопросы. Затем называю конечную стоимость вашего проекта. Мои цены адекватные, поэтому клиент в 99% незамедлительно соглашается.

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

Что такое структура данных очередь

Добавление элемента в конец очереди.

Удаление элемента из начала очереди.

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

Указатель на начало очереди

В программе на языке Pascal декларация указателя на первый элемент очереди выглядит примерно так:

Вы должны очень хорошо понимать, что собою представляет тип данных Tptr.

Организация взаимосвязей в связанных динамических данных

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

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

Рассмотрим объявление динамической структуры данных на языке программирования Pascal 7.0.:

ВАЖНО!
Правило последовательности описаний в Pascal требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Если посмотреть на декларацию, представленную выше, то очевидно, что идентификатор Tptr имеет указательный тип данных Telem, но ведь Telem еще не объявлен. Однако ошибки не возникает, так как для описания типов элементов динамических структур данных сделано исключение.

Вспомогательные инструменты для проведения операций над очередью

Абсолютно во всех операциях, производимых над структурой данных очередь, требуется вспомогательный указатель, помимо указателя begQ, ссылающего на первый элемент очереди. Во всех программах и фрагментах программного кода, представленных ниже, будем обозначать вспомогательный указатель идентификатором p. Почему «p»? Потому что с английского слово pointer переводится на русский как указатель.

Что же такое «NIL»

То есть в данном примере begQ является нулевым указателем. Подобное состояние имеет каждая очередь, не содержащая ни одного элемента.

Ошибкой является ситуация, когда указательная переменная begQ ссылается на неизвестный участок памяти. Такие ссылки называют висячими ссылками.

Добавление новых элементов в очередь связано с динамическим выделением памяти. В языке программирования Pascal для распределения динамической памяти употребляют процедуру new.

В самом широком смысле выделение памяти и инициализация полей производится так:

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

Добавление элемента в очередь

Необходимо понимать, что существует две разновидности добавления элемента в структуру данных очередь:

Добавление элемента в пустую, то есть не содержащую ни одного элемента очередь.

Добавление элемента в непустую, то есть содержащую определенное количество элементов очередь.

Итак, сначала разберем добавление элемента в пустую очередь

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

В результате проведения данной операции очередь находится в согласованном состоянии.

Разберем добавление элемента в непустую очередь

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

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

Устанавливаем вспомогательный указатель p на первый элемент очереди.

Циклически передвигаем указатель p на последний элемент очереди.

Например, в языке программирования Pascal для передвижения указателя p можно использовать цикл с предусловием или цикл While-Do.

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

Как видно из представленной схемы, операция добавления элемента в конец очереди выполняется элементарно. Необходимо указатель последнего элемента переставить на добавляемый элемент. В итоге очередь находится в согласованном состоянии, так как последний элемент ссылается в NIL, а begQ указывает на первый элемент.

Вывод: операция добавления элемента в очередь успешно проведена.

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

Удаление элемента из очереди

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

Разберем удаление элемента из непустой очереди

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

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

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

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

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

Многие программисты пренебрегают данной операцией и считают ее лишней, но я все-таки рекомендую перед удалением элемента из очереди полностью его «освободить» от каких-либо реляций.

Конечное состояние очереди после удаления первого элемента.

Вывод: операция удаления элемента из очереди успешно проведена.

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

Схема печати всех элементов очереди

Вообще печать элементов очереди нельзя относить к фундаментальным операциям, а лишь к вспомогательным операциям.

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

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

Как видно из представленной схемы, как только вспомогательный указатель p достигнет NIL, операция вывода будет официально завершена.

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

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

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

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

На схеме показаны вложенные копии вызова рекурсивной процедуры, причем в каждой версии процедуры существует «свой» указатель pp, указывающий на соответствующий элемент очереди.

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

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

Подобный вариант рекурсии имеет название рекурсия на возврате (для справки: существует также вариация рекурсии на спуске и обобщенный или смешанный вариант рекурсии).

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

Реализация динамической очереди на языке программирования Turbo Pascal

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

Добавление элемента в конец очереди.

Удаление элемента из начала очереди.

Печать элементов очереди на дисплее пользователя (от начала к концу).

Печать элементов очереди на дисплее пользователя от конца к началу (рекурсивно).

Получение общего количества элементов в очереди.

Если вас интересует реализация дополнительного функционала по структуре данных очередь, или вы хотите познакомиться с какой-либо функцией или процедурой, не представленной в этой статье, то сообщите об этом мне, написав на электронный адрес administrator@videoege.ru.

РЕПЕТИТОР
ПО ИНФОРМАТИКЕ
И ПРОГРАММИРОВАНИЮ

ЧИТАТЬ
ОТЗЫВЫ МОИХ
УЧЕНИКОВ

АДРЕС
ЭЛЕКТРОННОЙ ПОЧТЫ
РЕПЕТИТОРА

ЗАКАЗАТЬ
РАБОТУ ПО
ПРОГРАММИРОВАНИЮ

Источник

Очередь (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, если очередь пуста. Следующий код иллюстрирует это:

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

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

a.swap(b)

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

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

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

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

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

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

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

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

The == Operator

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

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

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

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

Вывод 1. Читайте также: Как научиться программировать на Swift: полное руководство

The > Operator

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

The >= Operator

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Источник

• ← что делать при появлении симптомов коронавируса у человека
• к какому врачу нужно идти с лимфоузлами →

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