Одной из моих генеральный компетенций является исследование различных популярных динамических структур данных. Уже на протяжении 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.
Очередь – структура данных типа «список», позволяющая добавлять элементы лишь в конец списка, и извлекать их из его начала. Она функционирует по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»), для которого характерно, что все элементы a1, a2, …, an-1, an, добавленные раньше элемента an+1, должны быть удалены прежде, чем будет удален элемент an+1. Также очередь может быть определена как частный случай односвязного списка, который обслуживает элементы в порядке их поступления. Как и в «живой» очереди, здесь первым будет обслужен тот, кто пришел первым.
Стандартный набор операций (часто у разных авторов он не идентичен), выполняемых над очередями, совпадает с тем, что используется при обработке стеков:
Только, если в отношении стека в момент добавления или удаления элемента допустимо задействование лишь его вершины, то касательно очереди эти две операции должны быть применены так, как это регламентировано в определении этой структуры данных, т. е. добавление – в конец, удаление – из начала. Далее, при реализации интерфейса очереди, список стандартных операций будет расширен.
Выделяют два способа программной реализации очереди. Первый из них основан на базе массива, а второй на базе указателей (связного списка). Первый способ – статический, т. к. очередь представляется в виде простого статического массива, второй – динамический.
Реализация очереди с помощью массива.
Данный способ позволяет организовать и впоследствии обрабатывать очередь, имеющую фиксированный размер. Определим список операций, который будет использоваться как при реализации статической очереди, так и динамической:
В программе каждая из этих операций предстанет в виде отдельной подпрограммы. Помимо того, потребуется описать массив данных data[N], по сути, являющийся хранилищем данных вместимостью N, а также указатель на конец очереди (на ту позицию, в которую будет добавлен очередной элемент) – last. Изначально last равен 0.
В функции main, сразу после запуска программы, создается переменная Q структурного типа Queue, адрес которой будет посылаться в функцию (в зависимости от выбора операции) как фактический параметр. Функция Creation создает очередь, обнуляя указатель на последний элемент. Далее выполняется оператор цикла do..while (цикл с постусловием), выход из которого осуществляется только в том случае, если пользователь ввел 0 в качестве номера команды. В остальных случаях вызывается подпрограмма соответствующая команде, либо выводиться сообщение о том, что команда не определена.
Из всех подпрограмм особого внимания заслуживает функция Delete. Удаление элемента из очереди осуществляется путем сдвига всех элементов в начало, т. е. значения элементов переписываются: в data[0] записывается значение элемента data[1], в data[1] – data[2] и т. д.; указатель конца смещается на позицию назад. Получается, что эта операция требует линейного времени O(n), где n – размер очереди, в то время как остальные операции выполняются за константное время. Данная проблема поддается решению.
Вместо «мигрирующей» очереди, наиболее приемлемо реализовать очередь на базе циклического массива. Здесь напрашивается аналогия с «живой» очередью: если в первом случае покупатели подходили к продавцу, то теперь продавец будет подходить к покупателям (конечно, такая тактика оказалась бы бесполезной, например, в супермаркетах и т. п.). В приведенной реализации очередь считалась заполненной тогда, когда указатель last находился над последней ячейкой, т. е. на расстоянии N элементов от начала.
В циклическом варианте расширяется интерпретация определения позиции last относительно начала очереди. Пусть на начало указывает переменная first. Представим массив в виде круга – замкнутой структуры. После последнего элемента идет первый, и поэтому можно говорить, что очередь заполнила весь массив, тогда когда ячейки с указателями last и first находятся радом, а именно за last следует first. Теперь, удаление элемента из очереди осуществляется простым смещением указателя first на одну позицию вправо (по часовой); чтобы добавить элемент нужно записать его значение в ячейку last массива data и сместить указатель last на одну позицию правее. Чтобы не выйти за границы массива воспользуемся следующей формулой:
(A mod N) + 1
Здесь A – один из указателей, N – размер массива, а mod – операция взятия остатка от деления.
В циклической реализации, как и прежде, очередь не содержит элементов тогда, когда first и last указывают на одну и ту же ячейку. Но в таком случае возникает одно небольшое отличие этой реализации от предшествующей. Рассмотрим случай заполнения очереди, основанной на базе массива, размер которого 5:
Элементы
first
last
—
1
1
1
1
2
1, 2
1
3
1, 2, 3
1
4
1, 2, 3, 4
1
5
В левом столбце записаны произвольные значения элементов, а в двух других значения указателей при соответствующем состоянии очереди. Необходимо заметить, что в массив размером 5 удалось поместить только 4 элемента. Все дело в том, что еще один элемент требует смещения указателя last на позицию 1. Тогда last=first. Но именно эта ситуация является необходимым и достаточным условием отсутствия в очереди элементов. Следовательно, мы не можем хранить в массиве больше N-1 элементов.
В следующей программе реализован интерфейс очереди, основанной на базе циклического массива:
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
1 способ: адресное поле ссылается на объявляемую структуру.
2 способ: адресное поле ссылается на ранее объявленную структуру.
Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередь через объявление линейного двунаправленного списка:
Пример 2. Дана последовательность ненулевых целых чисел. Признаком конца последовательности является число 0. Найдите среди них первый наибольший отрицательный элемент. Если такого элемента нет, то выведите сообщение об этом.
В данной задаче будем использовать основные операции для работы с очередью, рассмотренные ранее. Приведем главную функцию и функцию для реализации поиска первого наибольшего отрицательного элемента.
Ключевые термины
LIFO (Last Input – First Output) – это метод доступа к элементам стека по принципу «последним пришел – первым вышел»
Вершина стека – это доступный элемент стека.
Конец очереди – это позиция доступного для вставки в очередь элемента.
Начало очереди – это позиция доступного для извлечения из очереди элемента.
Всем привет! Для решения задач многие программисты используют структуру данных — очередь. Вы наверно когда-то слышали о ней, а возможно и применяли в своей программе.
Мы попытаемся ответить на несколько вопросов: что такое очередь, принцип работы очереди и какая у нее есть разновидность. Поехали!
Что такое очередь
В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым.
Чтобы понять принцип работы очереди вы можете представить себе магазинную очередь. И вы стоите посреди нее, чтобы вы оказались напротив кассы, сначала понадобится всех впереди стоящих людей обслужить. А вот для последнего человека в очереди нужно, чтобы кассир обслужил всех людей кроме него самого.
На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!
Так например чтобы извлечь число 4 нам понадобится сначала обслужить число 2, а потом уже и само число 4.
Хотя в стеке присутствует функция peek() (она позволяет обратится к элементу по индексу, подробнее вот здесь), в шаблоне очереди невозможно обратится к определенному элементу.
Но если вам нужно иметь доступ ко всем элементам очереди, то можете реализовать очередь через массив. Чуть ниже мы покажем как это сделать.
Как создать очередь в С++
Дальше для объявления очереди нужно воспользоваться конструкцией ниже.
Алгоритмы и структуры данных для начинающих: стеки и очереди
В предыдущих частях мы рассматривали базовые структуры данных, которые, по сути, являлись надстройками над массивом. В этой статье мы добавим к коллекциям простые операции и посмотрим, как это повлияет на их возможности.
Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу.
Наиболее часто встречающаяся аналогия для объяснения стека — стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.
Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.
Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.
Класс Stack
Метод Push
Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.
Метод Pop
Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.
Метод Peek
Метод Count
Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.
Пример: калькулятор в обратной польской записи
Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:
Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.
То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:
То есть, для выражения «4 2 +» действия будут следующие:
В конце на стеке окажется одно значение — 6.
Очередь
Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.
Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.
Класс Queue
Метод Enqueue
Новые элементы очереди можно добавлять как в начало списка, так и в конец. Важно только, чтобы элементы доставались с противоположного края. В данной реализации мы будем добавлять новые элементы в начало внутреннего списка.
Метод Dequeue
Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.
Метод Peek
Метод Count
Двусторонняя очередь
Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.
Класс Deque
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Пример: реализация стека
Двусторонняя очередь часто используется для реализации других структур данных. Давайте посмотрим на пример реализации стека с ее помощью.
У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.
Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.
Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:
Хранение элементов в массиве
Как уже было упомянуто, у реализации очереди с использованием массива есть свои преимущества. Она выглядит простой, но на самом деле есть ряд нюансов, которые надо учесть.
Давайте посмотрим на проблемы, которые могут возникнуть, и на их решение. Кроме того, нам понадобится информация об увеличении внутреннего массива из прошлой статьи о динамических массивах.
При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.
Добавляем элемент в начало
Добавляем элемент в конец
Добавляем еще один элемент в начало
Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).
И еще один в конец
Массив заполнен, поэтому при добавлении элемента произойдет следующее:
Добавляем значение в конец расширенного массива
Теперь посмотрим, что происходит при удалении элемента:
Удаляем элемент из начала
Удаляем элемент с конца
Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди — элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».
Теперь давайте посмотрим на реализацию.
Класс Deque(с использованием массива)
Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля — сам массив, его размер и указатели на «хвост» и «голову» очереди.
Алгоритм роста
Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).
Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Продолжение следует
Вот мы и закончили четвертую часть нашего цикла статей. В ней мы рассмотрели стеки и очереди. В следующий раз мы перейдем к бинарным деревьям поиска.
На рисунке слева находятся 7 чисел: 2, 4, 7, 1, 4, 9, 10. Если нам понадобится их извлечь, то извлекать мы будем в таком же порядке как они находятся на рисунке!
