Динамическая структура данных очередь
Я - репетитор, готовый помочь в реализации структуры данных очередь
Здравствуйте! Меня зовут Александр Георгиевич. Я - профессиональный рейтинговый репетитор по информатике, математике, алгоритмам, базам данных и программированию.
Одной из моих генеральный компетенций является исследование различных популярных динамических структур данных. Уже на протяжении 10 лет я помогаю всем желающим разобраться с такой структурой данных, как очередь. Программирую структуру данных очередь на одном из следующих языков программирования: Pascal, Delphi, C, C++, C#, Basic, VBA.
Очень часто ко мне обращаются студенты из технических вузов РФ и повествуют о том, что у них в некоторых лабораторных требуется провести реализацию структуры данных очередь. Вы должны понимать, что подобная реализация не может стоить очень дешево! После ознакомления с постановкой задачи, я начинаю задавать клиенту уточняющие вопросы. Затем называю конечную стоимость вашего проекта. Мои цены адекватные, поэтому клиент в 99% незамедлительно соглашается.
Если вы хотите разобраться максимально дифференцированно со структурой данных очередь, тогда берите телефон, дозванивайтесь до меня, задавайте любые тематические вопросы и записывайтесь на первый пробный урок. Мои репетиторские уроки проходят в различных территориальных форматах - выбирайте!
А сейчас я предлагаю вашему вниманию видеопрезентацию, в которой тезисно и доступно поясняю все тонкие моменты нашего взаимовыгодного сотрудничества. Особое внимание обратите на отзывы клиентов под этим видео, заказавших у меня работу по программированию.
Что такое структура данных очередь
Структура данных очередь - частный случай линейного односвязного списка (ЛОС), для которого определены две фундаментальные операции:
Добавление элемента в конец очереди.
Удаление элемента из начала очереди.
Также еще существует обязательная вспомогательная операция - печать элементов очереди на экран, а если быть более точным, то происходит визуализация значений информационных полей элементов очереди, так как в любом случае потребуется печать очереди на экран пользователя, чтобы просмотреть, насколько корректно реализованы операции добавления и удаления элементов.
Фактически, никакие другие операции, кроме трех перечисленных выше, над структурой данных очередь не разрешены: ни сортировка, ни слияние двух однородных очередей, ни расщепление данной очереди на две подочереди. Но на деле, происходит нарушение данного правила, и, очень часто, в школах или вузах дают задания, связанные с обработкой очереди, включающей недопустимые операции. Поэтому, уже нет четкой детерминации на допустимые и недопустимые операции возможные над очередью.
Указатель на начало очереди
Для корректной обработки структуры данных очередь вводят понятие - указатель на начало очереди. Как правило, именуется в программе подобный указатель словом begQ (в переводе с английского означает begin queue - начало очереди). Данный указатель обязан указывать или ссылаться только на самый первый элемент очереди, иначе очередь будет находиться в несогласованном состоянии.
В программе на языке Pascal декларация указателя на первый элемент очереди выглядит примерно так:
{указатель на начало очереди, по сути, указатель на первый элемент очереди}
begQ : Tptr;
Вы должны очень хорошо понимать, что собою представляет тип данных Tptr.
Примечание: зачастую в дидактической литературе можно встретить упоминание об указателе на конец очереди endQ (end queue - конец очереди). То есть иногда обработка очереди строится с применением двух указателей: begQ и endQ. Во всех представленных ниже программах я буду оперировать исключительно одним указателем - указателем на начало очереди, то есть только begQ.
Организация взаимосвязей в связанных динамических данных
Любые динамические данные характеризуются высокой гибкостью создания различных структур данных всевозможных конфигураций. Это достигается благодаря возможности выделять и освобождать память под элементы в любой момент времени работы программы и возможности установить связь между любым набором элементов с помощью специальных указателей.
Для правильной организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал, кроме информационных значений, как минимум один указатель. Зачастую, в качестве информационных полей используют записи (Record), которые могут консолидировать в единое целое разнородные значения.
Рассмотрим объявление динамической структуры данных на языке программирования Pascal 7.0.:
{указательный тип данных на элемент очереди}
Tptr = ^Telem;
{запись, состоящая из двух полей, описывающая элемент очереди}
Telem = record
{информационное поле элемента - хранит символьные значения}
inf : char;
{указательное поле на следующий элемент очереди}
link : Tptr;
{конец описания записи}
end;
ВАЖНО!
Правило последовательности описаний в Pascal требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Если посмотреть на декларацию, представленную выше, то очевидно, что идентификатор Tptr имеет указательный тип данных Telem, но ведь Telem еще не объявлен. Однако ошибки не возникает, так как для описания типов элементов динамических структур данных сделано исключение.
Вспомогательные инструменты для проведения операций над очередью
Абсолютно во всех операциях, производимых над структурой данных очередь, требуется вспомогательный указатель, помимо указателя begQ, ссылающего на первый элемент очереди. Во всех программах и фрагментах программного кода, представленных ниже, будем обозначать вспомогательный указатель идентификатором p. Почему "p"? Потому что с английского слово pointer переводится на русский как указатель.
Что же такое "NIL"
NIL - специальный зарезервированный участок памяти, служащий "бухтой" для динамических переменных - указателей. Чтобы указатели "не болтались" в памяти, их обычно "привязывают" к NIL.
 |
То есть в данном примере begQ является нулевым указателем. Подобное состояние имеет каждая очередь, не содержащая ни одного элемента. Ошибкой является ситуация, когда указательная переменная begQ ссылается на неизвестный участок памяти. Такие ссылки называют висячими ссылками. |
Добавление новых элементов в очередь связано с динамическим выделением памяти. В языке программирования Pascal для распределения динамической памяти употребляют процедуру new.
В самом широком смысле выделение памяти и инициализация полей производится так:
new(add);
{линковочное поле добавляемого элемента устанавливаем в NIL}
add^.link := NIL;
{диалог пользователю о предстоящем вводе символьного значения}
write('Введите значение добавляемого элемента: ');
{считываем информацию от пользователя с клавиатуры}
readln(add^.inf);
то есть видно, что сначала происходит выделение памяти под сам добавляемый элемент, а затем инициализация информационного поля соответствующим значением, а линковочное поле устанавливается в NIL.
Добавление элемента в очередь
Необходимо понимать, что существует две разновидности добавления элемента в структуру данных очередь:
Добавление элемента в пустую, то есть не содержащую ни одного элемента очередь.
Добавление элемента в непустую, то есть содержащую определенное количество элементов очередь.
Итак, сначала разберем добавление элемента в пустую очередь
| Исходное состояние пустой очереди. Указатель begQ ссылается в NIL. | |
| add - указатель на добавляемый элемент. Линковочное поле добавляемого элемента ссылается в NIL - правило хорошего тона. |  |
|
Поскольку в структуре данных очередь нет ни одного элемента, то происходит смещение указателя begQ на добавляемый элемент. В итоге очередь состоит из одного элемента и указатель begQ ссылается именно на первый и единственный элемент. В результате проведения данной операции очередь находится в согласованном состоянии. |
 |
Разберем добавление элемента в непустую очередь
|
Как видно из представленной схемы, очередь содержит три элемента и находится в согласованном состоянии, так как указатель begQ ссылается на первый элемент. |
 |
| add - указатель на добавляемый элемент. Линковочное поле добавляемого элемента ссылается в NIL - правило хорошего тона. | |
|
Чтобы произвести добавление элемента в непустую очередь, необходимо позиционироваться в конец очереди, а если быть более точным, то необходим дополнительный указатель, который позиционируется на последний элемент очереди. Устанавливаем вспомогательный указатель p на первый элемент очереди. |
 |
|
Циклически передвигаем указатель p на последний элемент очереди. Например, в языке программирования Pascal для передвижения указателя p можно использовать цикл с предусловием или цикл While-Do. |
 |
| Указательная переменная p ссылается на последний элемент очереди, следовательно, можно переходить непосредственно к операции добавления нового элемента в структуру данных очередь. |  |
|
Как видно из представленной схемы, операция добавления элемента в конец очереди выполняется элементарно. Необходимо указатель последнего элемента переставить на добавляемый элемент. В итоге очередь находится в согласованном состоянии, так как последний элемент ссылается в NIL, а begQ указывает на первый элемент. Вывод: операция добавления элемента в очередь успешно проведена. |
 |
Общий программный вывод: добавление элемента в очередь любого типа: пустую или непустую является универсальной операцией, так как во всех случаях приходится реализовывать идентичные события, а, следовательно, операцию добавления элемента в конец структуры данных очередь можно запрограммировать.
Удаление элемента из очереди
Удаление физически возможно только тогда, когда в очереди присутствуют элементы, минимум один элемент, иначе, когда очередь является пустой, то есть не содержит элементы, данная операция невозможна. Все последующие выкладки будут проистекать из положения, что мы взаимодействуем с непустой очередью.
Разберем удаление элемента из непустой очереди
|
Как видно из представленной схемы, очередь содержит три элемента и находится в согласованном состоянии, так как указатель begQ ссылается на первый элемент. Напомню, что удаление элемента осуществляется из начала очереди, то есть уничтожается первый элемент очереди. Технология операции удаления первого элемента из очереди не зависит от количества элементов во всей очереди. |
|
|
Первым действием необходимо воспользоваться вспомогательным указателем p и установить данный указатель на первый элемент очереди. То есть фактически обе указательных переменных p и begQ ссылаются на один и тот же элемент - первый элемент структуры данных очередь. |
 |
|
Вторым действием переводим указатель на начало очереди begQ на следующий, по факту - второй элемент очереди. Для перехода на следующий элемент очереди используются линковочные поля, которые обеспечивают связь между динамическими узлами структуры данных очередь. |
 |
|
Полностью "отвязываем" удаляемый элемент из очереди, чтобы не осталось ни одной связи с другими элементами. Для этого линковочное поле первого элемента устанавливаем в NIL. Многие программисты пренебрегают данной операцией и считают ее лишней, но я все-таки рекомендую перед удалением элемента из очереди полностью его "освободить" от каких-либо реляций. |
 |
|
Производим собственно удаление первого элемента из очереди. Удаление происходит абсолютно безболезненно, не разрушает внутренние связи очереди и после операции удаления очередь находится в согласованном состоянии: begQ - ссылается на первый элемент, а линковочное поле последнего элемента указывает в NIL. Для удаления ранее выделенной динамической памяти в языке программирования Pascal используется процедура Dispose, а в языке программирования С - free, в языке С++ - delete. |
 |
|
Конечное состояние очереди после удаления первого элемента. Вывод: операция удаления элемента из очереди успешно проведена. Общий программный вывод: удаление элемента из непустой очереди является универсальной операцией, так как во всех случаях приходится реализовывать идентичные события, а, следовательно, операцию удаления элемента из очереди можно запрограммировать. |
 |
Схема печати всех элементов очереди
| Печать элементов структуры данных очередь будет физически возможной, если в очереди имеется хотя бы один элемент. | |
|
Вообще печать элементов очереди нельзя относить к фундаментальным операциям, а лишь к вспомогательным операциям. Предположим, что начальная очередь содержит три элемента. Для визуализации значения информационных полей элементов очереди необходим дополнительный указатель. Введем идентификатор p. Справа представлен полный процессинг всех итераций по печати элементов очереди на экран пользователя. Важно заметить следующее, что распечатка всех элементов на экран - итерационный процесс, следовательно, при программировании используют циклы, как правило, цикл с предусловием, то есть цикл While-Do. Как видно из представленной схемы, как только вспомогательный указатель p достигнет NIL, операция вывода будет официально завершена. После окончания печати всех элементов очереди, сама структура данных очередь остается в согласованном состоянии. |
|
|
|
|
|
|
|
 |
Печать элементов очереди от замыкающего к начальному элементу, используя рекурсивный вызов
| Печать элементов очереди будет физически возможной, если в очереди имеется хотя бы один элемент. Если очередь пуста (нулевая очередь), то операцию визуализации элементов невозможно произвести. | |
|
Как видно из представленной схемы рекурсивной печати элементов для обхода структуры данных очередь, требуется вспомогательный указатель. Им является идентификатор pp. На схеме показаны вложенные копии вызова рекурсивной процедуры, причем в каждой версии процедуры существует "свой" указатель pp, указывающий на соответствующий элемент очереди. Для обхода очереди, состоящей из трех элементов, потребовалось четыре раза вызвать рекурсивную процедуру, что, несомненно, является затратным с точки зрения использования динамической памяти программы. Как видно из изображения, рекурсия закончилась, когда указатель pp достиг критического значения, то есть вышел в NIL. Как только это случилось, рекурсивные копии процедур начали закрываться и именно в этот момент происходит визуализация значений информационных полей на дисплей пользователя. Подобный вариант рекурсии имеет название рекурсия на возврате (для справки: существует также вариация рекурсии на спуске и обобщенный или смешанный вариант рекурсии). В каждой копии процедуры имеется элемент, на который ссылается указатель pp, вот именно информационное поле данного элемента и будет распечатано на экране. Причем элементы структуры данных очередь будут визуализированы от конца к началу. |
|
Реализация динамической очереди на языке программирования Turbo Pascal
Предлагаю вашему вниманию программу на языке высокого уровня Pascal - реализация структуры данных очередь без обработки исключительных ситуаций, используя глобальный указатель, ссылающийся на вершину очереди, то есть не используется парадигма передачи параметров между подпрограммами и главной программой. Очередь способна обрабатывать только символьные значения. Как я ранее указывал в данной статье, выбор типа данных не является критичным и легко может быть заменен на нужный тип данных.
Программа реализует следующие операции над структурой данных очередь:
-
Добавление элемента в конец очереди.
-
Удаление элемента из начала очереди.
-
Печать элементов очереди на дисплее пользователя (от начала к концу).
-
Печать элементов очереди на дисплее пользователя от конца к началу (рекурсивно).
-
Получение общего количества элементов в очереди.
Скачать программу реализации динамической очереди на языке программирования Pascal
Если вас интересует реализация дополнительного функционала по структуре данных очередь, или вы хотите познакомиться с какой-либо функцией или процедурой, не представленной в этой статье, то сообщите об этом мне, написав на электронный адрес administrator@videoege.ru.
program QUEUE;
{раздел подключения модулей}
uses
{подключаем модуль crt - console run time, чтобы можно было использовать
подпрограммы для работы с консолью}
crt;
{раздел объявления пользовательских типов данных}
type
{указательный тип данных на элемент очереди}
Tptr = ^Telem;
{запись, состоящая из двух полей, описывающая элемент очереди}
Telem = record
{информационное поле элемента - хранит символьные значения}
inf : char;
{указательное поле на следующий элемент очереди}
link : Tptr;
{конец описания записи}
end;
{раздел декларации глобальных переменных}
var
{указатель на начало очереди, по сути, указатель на первый элемент очереди}
begQ : Tptr;
{---------------------------------------------------------------------------}
{Процедура: добавление элемента в конец очереди}
{---------------------------------------------------------------------------}
procedure addElem;
var
{указатель на добавляемый элемент}
add : Tptr;
{вспомогательный указатель, помогающий произвести операцию добавления}
p : Tptr;
{начало тела процедуры}
begin
{выделям память под добавляемый элемент}
new(add);
{линковочное поле добавляемого элемента устанавливаем в NIL}
add^.link := NIL;
{диалог пользователю о предстоящем вводе символьного значения}
write('Введите значение добавляемого элемента: ');
{считываем информацию от пользователя с клавиатуры}
readln(add^.inf);
{если в очереди нет ни одного элемента, то}
if(begQ = NIL) then
{устанавливаем указатель начало очереди begQ на добавляемый элемент}
begQ := add
{иначе в очереди имеется хотя бы один элемент}
else
begin
{вспомгательный указатель позиционируется на первый элемент очереди}
p := begQ;
{цель указателя р добраться до последнего элемента, но поскольку количество
элементов неизвестно, то приходится использовать цикл с предусловием. Цикл
продолжается до тех пор, пока указатель р не будет ссылаться на последний
элемент текущей очереди}
while(p^.link <> NIL) do
{переходим на следующий элемент очереди}
p := p^.link;
{устанавливаем связь между последним элементом очереди и добавляемым
элементом, то есть, новый элемент оказался в самом конце очереди}
p^.link := add;
end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Процедура: удаление элемента из начала очереди}
{---------------------------------------------------------------------------}
procedure delElem;
var
{вспомогательный указатель, помогающий произвести операцию удаления}
p : Tptr;
{начало тела процедуры}
begin
{устанавливаем вспомогательный указатель на первый элемент очереди}
p := begQ;
{перемещаем указатель начала очереди begQ на следующий элемент (второй)}
begQ := begQ^.link;
{полностью "отвязываем" удаляемый элемент из очереди, чтобы он не имел
абсолютно никаких связей с остальными элементами очереди. Данная "отвязка"
не является обязательной, так как после удаления все связи будут
автоматически уничтожены}
p^.link := NIL;
{удаляем первый элемент из очереди}
dispose(p);
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Процедура: печать элементов очереди от начала к концу}
{---------------------------------------------------------------------------}
procedure printQ;
var
{вспомогательный указатель, помогающий произвести печать элементов очереди}
p : Tptr;
{начало тела процедуры}
begin
{позиционируем вспомогательный указатель на первый элемент очереди}
p := begQ;
{чтобы распечатать информацию всех элементов очереди, необходимо посетить
все эти элементы, то есть, надо циклически просмотреть каждый элемент. Цикл
будет продолжаться до тех пор, пока указатель р не выйдет в NIL}
while(p <> NIL) do
begin
{выпечатываем символьное значение текущего элемента}
write(p^.inf:3);
{указатель р переходит к следующему элементу}
p := p^.link;
end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Рекурсивная процедура: печать всех элементов очереди от конца к началу.
Форма выполнения рекурсии - на возврате, т е действия, выполняются после
рекурсивного вызова}
{---------------------------------------------------------------------------}
procedure recPrintQ(pp : Tptr);
begin
{как известно, любая рекурсия не может выполняться вечно, следовательно,
должен быть случай (его называют элементарным случаем), когда рекурсия
завершает свое выполнение. В данном случае, рекурсивный вызов завершается,
когда указатель-параметр оказывается в NIL, то есть за последним элементом
очереди. То есть, если указатель ссылается на элемент, то}
if(pp <> NIL) then
begin
{происходит рекурсивный вызов процедуры, причем в качестве параметра,
передается указатель на следующий элемент}
recPrintQ(pp^.link);
{выпечатываем на экран пользователя значение текущего элемента}
write(pp^.inf:3);
end;
{конец тела процедуры}
end;
{---------------------------------------------------------------------------}
{Функция: вывод меню программы}
{---------------------------------------------------------------------------}
function mainMenu : integer;
var
{отвечает за пункт меню выбранный пользователем}
sel : integer;
{начало тела функции}
begin
{в цикле с постусловием визуализируем пункты меню программы}
repeat
clrscr;
writeln('1 - ДОБАВИТЬ ЭЛЕМЕНТ В ОЧЕРЕДЬ');
writeln('2 - УДАЛИТЬ ЭЛЕМЕНТ ИЗ ОЧЕРЕДИ');
writeln('3 - ПЕЧАТЬ ЭЛЕМЕНТОВ ОЧЕРЕДИ ОТ НАЧАЛА К КОНЦУ');
writeln('4 - РЕКУРСИВНАЯ ПЕЧАТЬ ЭЛЕМЕНТОВ ОЧЕРЕДИ ОТ КОНЦА К НАЧАЛУ');
writeln('5 - ПОЛУЧИТЬ КОЛИЧЕСТВО ЭЛЕМЕНТОВ ОЧЕРЕДИ');
writeln('6 - ВЫХОД');
{диалог пользователю о предстоящем вводе}
write('Выберите один из пунктов меню: ');
{считывание информации вводом с клавиатуры}
readln(sel);
{выход из цикла осуществляется только тогда, когда пользователь выберет
допустимый пункт меню, то есть, по сути, небольшая защита от ошибок}
until((sel >= 1) and (sel <= 6));
{отступ для повышения читабельности}
writeln;
{возвращение ответа указанного пользователем}
mainMenu := sel;
{конец тела функции}
end;
{---------------------------------------------------------------------------}
{Функция: определение количества элементов в очереди}
function getCountElem : integer;
var
{вспомогательный указатель, помогающий определить общее количество элементов}
p : Tptr;
{отвечает за количество элементов в очереди}
k : integer;
{начало тела функции}
begin
{до обработки количество элементов равно 0}
k := 0;
{устанавливаем вспомогательный указатель на первый элемент очереди}
p := begQ;
{чтобы определить общее количество элементов в очереди необходимо циклически
просмотреть все элементы, поэтому начинаем цикл, который будет продолжаться
до тех пор, пока указатель р не выйдет за последний элемент, то есть пока
не выйдет в NIL}
while(p <> NIL) do
begin
{увеличиваем счетчик количества элементов на единицу}
k := k + 1;
{переходим к следующему элементу очереди}
p := p^.link;
end;
{в качестве ответа функция возвращает подсчитанное количество элементов}
getCountElem := k;
{конец тела функции}
end;
{---------------------------------------------------------------------------}
var
{отвечает за пункт меню, выбранный пользователем}
sel : integer;
{начало главного блока программы}
begin
{очистка экрана от прошлых выводов}
clrscr;
{изначально в очереди нет элементов, следовательно, чтобы указатель начала
очереди не "висел" в памяти, необходимо его установить в NIL}
begQ := NIL;
{циклически отрисовываем меню и просим выбрать пользователя одно из действий
над очередью до тех пор, пока пользователь не выйдет из программы}
repeat
{пользователь сделал выбор пункта меню}
sel := mainMenu;
{используя оператор множественного выбора определяем какую процедуру
необходимо вызвать}
case sel of
1:
begin
{добавление элемента в конец очереди}
addElem;
writeln;
writeln('Элемент успешно добавлен в конец очереди!');
readkey;
end;
2:
begin
{удаление элемента из начала очереди}
if(begQ = NIL) then
writeln('В очереди нет ни одного элемента! Удаление невозможно!')
else
begin
delElem;
writeln('Элемент успешно удален из начала очереди!');
end;
readkey;
end;
3:
begin
{печать элементов очереди из начала в конец}
if(begQ = NIL) then
writeln('В очереди нет ни одного элемента! Печать невозможна!')
else
begin
write('Элементы очереди имеют вид: ');
printQ;
end;
readkey;
end;
4:
begin
{рекурсивная печать элементов очереди из конца в начало}
if(begQ = NIL) then
writeln('В очереди нет ни одного элемента! Печать невозможна!')
else
begin
write('Элементы очереди имеют вид: ');
recPrintQ(begQ);
end;
readkey;
end;
5:
begin
{определяем количество элементов в очереди}
writeln('Количество элементов в очереди: ', getCountElem);
readkey;
end;
end;
{производим выход из цикла, когда пользователь выбрал пункт меню "ВЫХОД"}
until(sel = 6);
{конец тела главного блока}
end.
