Очередь - это набор идущих друг за другом объектов.

Что такое очередь?

Stfw.Ru: Представь себе длинный-длинный коридор, на правую сторону этого коридора находятся комнаты 1, 2, 3 и т д - это элементы очереди.Но только вот двери в этих комнатах странные... Ты можешь зайти сразу только в первую комнату, а для того что бы попасть во-вторую - тебе надо пройти эту первую комнату.Во второй комнате есть дверь в третью... и т д.Что бы выйти наконец из коридора, тебе надо пройти все эти комнаты.
Да, чуть не забыл очередь реализуется на основе указателей (ссылок), ну так вот дверь в очередную комнату - это ссылка на этот самый следующий элемент очереди.

Теперь о типах очередей.
Конечно, классическое действие очереди формулируется как "Первым зашёл, последним вышел", но на практике иногда бывает полезно это классическое определение "стереть в порошок", и необращать на него ни малейшего внимания. Таким образом моно выделить следующие типы очередей:

1)однонаправленные - это когда движешься от начала очереди в конец последовательно, а как пройдешь очередную комнату - дверь назад... пропадает , и назад пути нету (Вперед, и только вперед - к победе!) - это и есть классическая очередь.
При реализации такой очереди в программе хранится только указатель на первый объект очереди (дверь в первую комнату). Для доступа, например, к 5-ому элементу, необходимо (без этого никак!!!) пройти все предыдущие элементы очереди. При этом в самой записи (элементе очереди) хранится кроме полезной информации, есчо и ссылка (указатель) на следующий элемент.

2)двунаправленные - тут уж как хочешь: пройдешь пять дверей вперед, потом захотел вурнуться - пожалуйста, без проблем, этакое реверсивное движение.
При реализации такой очереди обычно хранится уже две переменные - "голова" и "хвост" очереди. Хотя вполне можно ограничиться только "Головой". В самой записи находится уже два указателя: на предыдущий элемент и на следующий. Первый элемент очереди ссылки на предыдущий элемент не имеет (на паскале ставиться "пустое значение указателя" - Nil), а
послений элемент - ссылки на следующий не имеет и вместо него ставится Nil

3)многонаправленные - ну тут уж совсем сложно: из одной комнаты, можно попасть не только в следующую или предыдущую конаты, а моно пойти налево, или направо - а там свои коридоры с точно такими же комнатами... (так например можно представить плоскую доску, например, шахматную, где с текущей клетки моно пойти по 8 направлениям [если она конечно не граничная]).
В реализации одного элемента такой очереди могут участвовать не два (как в предыдущем случае), а большее количество указателей.

Примеры реализации очередей и работа с ними:
I-ый тип очередей
как я уже говорил, все это дело на основе указателей (чаще всего на записи). Структура такой записи такая: рабочие данные (комната) + ссылки (двери). Сколько будет ссылок, зависит от выбранного типа очереди.
Пример:
Код

Type PItem=^TItem; //Это наш указатель (ссылка) TItem=Record //описание одной ячейки очереди Data:String; // рабочие данные, т е комната. Количество данных и их типы зависят Chislo:Integer; // от конкретной задачи. Здесь используется строковое поле и числовое поле Next:PItem; // указатель на следующий элемент очереди - дверь в следующую комнату End;
Var First:PItem; // переменная, через которую будет общаться с очередью - это и есть "голова" очереди

Первоначально, в очереди нет ни одного элемента, => в First должно быть Nil. Несмотря на то что вроде как утверждается, что многие паскаль-компиляторы при объявлении переменной указателя автоматом засовывают туда Nil, я много раз убеждался, что это не так. Поэтому перед началом работы лучше выполнить следующую команду:
код Pascal/Delphi
1: First:=Nil; // и точка!

Ну теперь давайте по добавляем элементы в очереь. Так как у нас только "голова очереди", то придется добавлять только в начало очереди, постепенно "удаляя" уже существующие элементы от головы к хвосту очереди. Делать это лучше в подпрограмме:
код Pascal/Delphi

Procedure Add(S:String;C:Integer); // в подпрограмму передаются только "полезные" даные Var NewItem:PItem; // Новый элемент очереди
Begin //сначала создадим в памяти наш новый указатель: New(NewItem); //теперь занесем данные: NewItem^.Data:=S; NewItem^.Chislo:=C; //Теперь сделаем ссылку на следующий элемент NewItem^.Next:=First; // "отдаляем" , начало очереди First:=NewItem; // и делаем только-что созданный элемент - головой
End;

При удалении элемента нужно помнить, что если мы удалим головной элемент (голову) очереди, то мы все равно должны дать возможность обращаться к следующему за удаляемым элементу, то есть теперь второй элемент очереди становится первым - головой.
Опять таки лучше оформить это в виде подпрограммы:
код Pascal/Delphi

Procedure Delete; Var DelItem:PItem; // удаляемый элемент
Begin DelItem:=First; // запоминаем удаляемый элемент. Это надо сделать т к мы далее будем сохранять ссылу на следующий элемент, который из 2-ого превратится в 1-ый If DelItem<>Nil Then Begin // да, а может в очереди ничего уже нет. Обязательно надо проверить First:=DelItem^.Next; // Вот теперь 2-ой эл-т станет головой! Dispose(DelItem) // Непосредственно удаление End
End;

А если надо очистить ВЕСЬ список то вот рецепт:
код Pascal/Delphi

Procedure DeleteAll; Var DelItem:PItem; // текущий удаляемый эл-т CurItem:PItem; // текущий "рабочий" эл-т
Begin CurItem:=First; // все начинается естно с начала :) While CurItem<>Nil Do Begin// Пока не ун6ичтожим ЭТО все!! DelItem:=CurItem; // удалить текущий элемент CurItem:=CurItem^.Next; // запомнить, что следующий удаляемый будет следующий по списку Dispose(DelItem) // непосредственно отправление элемента в ад End; First:=Nil; // ето для надежности
End;


Ну и что бы были раждости полные штаны давайте рассмотрим пример, работы со всеми элементами очереди. Например, увеличение каждого Chislo на 1 и вывод на печать всех Data. Для этого надо будет пройтись по всему списку (примерно так как было при удалении всех элементов) от начала до конца,получится примерно следующий код:
код Pascal/Delphi

procedure DoWithAll; Var CurItem:PItem; // ето текущий элемет в очереди 
Begin CurItem:=First; // начинаем с начала While CurIte<>Nil Do Begin // пока не увидим свет в конце тунелля (не выберемся то есть) Inc(CurItem^.Chislo); //увелич на единицу WriteLn(CurItem^.Data); // вывод на печать CurItem:=CurItem^.Next // переходим к следующему элементу End
End;

При вставке элемента где-нить по середине нужно помнить, что при этом мы должны сохранить целостность списка, что бы не получилось так, что некотрые эл-ты у нас потеряются. Например, вот так может выглядеть вставка эл-та в n-ую позицию:
код Pascal/Delphi

procedure Add_N(S:String;C:Integer; N:Integer); Var CurItem:PItem; // текущий эл-т PredItem:PItem; // предыдущий эл-т NewItem:PItem; Curr:Integer;
Begin // Сначала надо найти существующий n-ый элемент: CurItem:=First; Curr:=1; PredItem:=Nil; While (CurItem<>Nil) And (Curr<N) Do Begin PredItem:=CurItem; CurItem:=CurItem^.Next; Inc(N) End; // вроде нашли. Но может получится так, что вставляем мы в 5-ую позицию, а эл-тов всего 3. тогда наш цикл закончится, когда N=4, а CurItem=Nil // Надо все это проверять! If CurItem<>Nil Then // Все хорошо Begin // Добавляем New(NewItem); NewItem^.Data:=S; NewItem^.Chislo:=C; NewItem^.Next:=CurItem^.Next; PredItem^.Next:=NewItem End Else // нет - не нашлось n-ого эл-та. Тогда можно добавить в конец, или не добавлять вовсе.
End;

Для таких "сложных" манипуляций с элементами очереди лучше представлять что мы делаем. Сейчас попробую обяснить зачем нам понадобился PredItem - ссылка на предыдущий эл-т.
Пусть наша очередь:
First -> 1 -> 2 -> 3 -> 4 -> nil
Как видно всего у нас четыре эл-та и вставляем мы новый эл-т на место 3-его. Сразу мы "видим" только первый элемент (переменная First)
После добавления добавления долна получится следующая картина:
First -> 1 -> 2 -> 5 -> 3 -> 4 -> nil
То есть после второго эл-та у нас должен идти 5-ый (только-что вставленный на 3-ье место), а после него - 3-ий.
Т к очередь у нас классическая и ссылок на предыдущие эл-ты нет, то на момент нахождения 3-ео элемента, у нас будет следующее:
CurItem -> 3 -> 4 -> nil
и
First -> 1 -> 2 -> 3 -> 4 -> nil
Естественно мы можем создать новый эл-т и в его поле Next запихнуть то что содержится в CurItem:
код Pascal/Delphi
1:
NewItem^.Next:=CurItem;

NewItem -> 5 -> 3 -> 4 -> nil
CurItem -> 3 -> 4 -> nil
First -> 1 -> 2 -> 3 -> 4 -> nil
это то что у нас получится с переменными. сделать переход
...-> 2 -> 5 -> .
не представляется возможным, поэтому и пришлось использовать еще одну переменную, в которую запоминался предыдущий эл-т. Тогда, на момент выполнения всех действий у нас бедет следующая картина:
NewItem -> 5 -> 3 -> 4 -> nil
CurItem -> 3 -> 4 -> nil
PredItem -> 2 -> 3 -> 4 -> nil
First -> 1 -> 2 -> 3 -> 4 -> nil
Вот используя PredItem^.Next (Это и есть наша связка 2 ->) и реализовали нашу задачу.

Ну вот кажись и все насчет первого типа очередей.

II-ый тип очередей
Тип записи следующий:
код Pascal/Delphi

Type PItem=^TItem; TItem=Record Data:String; Pred:PItem; // Указатель на предыдущий эл-т Next:PItem; // Следующий End;
Var First,Last:PItem; // Голова и хвост соответственно

Как раньше договаривались, перед началом делаем:
код Pascal/Delphi

First:=Nil;
Last:=Nil

Теперь, когда у нас два указателя, процедура добавления может выгладеть двояко:
код Pascal/Delphi

// в начало очереди
Procedure AddAtBegin(D:String); Var NewItem:PItem;
Begin New(NewItem); NewItem^.Data:=D; NewItem^.Pred:=Nil; // раз в начало, то есть это будет первый эл-т => предыдущего эл-та не будет NewItem^.Next:=First; First:=NewItem; If Last=Nil Then // если последного эл-та нет, => добавляется 1-ый эл-т, => он же и последний Last:=NewItem
End;
//В конец
Procedure AddAtEnd(D:String); Var NewItem:PItem;
Begin New(NewItem); NewItem^.Data:=D; NewItem^.Next:=Nil; // раз в конец - нет следующих элементов NewItem^.Pred:=Last; // но зато есть предыдущие Last:=NewItem; If First=Nil Then // если первого эл-та нет, => добавляется 1-ый эл-т, => он же и первый First:=NewItem
End;

Вставка в серёдку:
код Pascal/Delphi

Procedure Insert_N(D:String; N:Integer); Var NewItem:PItem; // хочу заметить, что CurItem:PItem; // "предыдущий" эл-т мы Curr:Integer; // не сохраняем - он у нас уже есть: CurItem^.Pred 
// но тут есть одна закорючка, которую не все понимают!!!
Begin CurItem:=First; Curr:=1; While (CurItem<>Nil) And (Curr<N) Do Begin CurItem:=CurItem^.Next; Inc(Curr) End; If CurItem<>Nil Then // все хорошо Begin // добавляем New(NewItem); NewItem^.Data:=D; NewItem^.Next:=CurrItem^.Next; CurrItem^.Next^.Pred:=NewItem; // ЗАКОРЮЧКА! (объяснение ниже) CurrItem^.Next:=NewItem; NewItem^.Pred:=CurrItem; End
End;

Закорючка. На первый взляд выражение CurrItem^.Next^.Pred или CurrItem^.Pred^.Next вызывает недоумение. Что это вообще такое и с чем его едят, а может быть это одно и тоже? Спокойно! Счас всё объясню.
Представляем снова наши диаграмки. Например у нас очередь из четырех - элементов. (Не забываем что очередь двунаправленная):
First->1->2->3->4->nil
nil<-1<-2<-3<-4<-Last
Например, мы вставляем новый элемент после 2-ого, т е у нас должно получиться:
First->1->2->5->3->4->nil
nil<-1<-2<-5<-3<-4<-Last
То что после первого же прогона цыкла While в переменной CurItem Будет наш второй эл-т, я думаю ясно. Что происходит далее:
Создаётся новый элемент:
NewItem->5->Nil (next)
(pred) Nil<-5
Затем начинают формироваться ссылки на другие эл-ты очереди, и ссылки элементов очереди (следующего и предыдущего) на новый элемент.
Строка NewItem^.Next:=CurrItem^.Next; приведет к следующему:
NewItem->5->3->. (next)
(pred) Nil<-5
Хотя ссылка на предыдущий эл-т третьего эл-та остаётся прежней: ...<-2<-3<-...
первая закорючка CurrItem^.Next^.Pred:=NewItem делает ссылку на новый элемент в качестве предыдущего элемента для следующего, относительно текущего: ( :p ;-) - вы понимаете??? :D ), То сть:
Текущий элемент: <-2->, его следующий(3): <-3-> ну так вот изменяется связь <-3, предыдущий для третьего становится новый элемент:
...->2->3->
nil<-5<-3<после этих двух строчек связи
...2->3..
...2<-3..
теряются и на их место становятся:
...2... 5->3...
...2... 5<-3...
как видите двойка у нас еще в неопределенности, а нам надо, что бы после двойки была 5, а до 5 - двойка. Что и делают следующие строчки:
CurrItem^.Next:=NewItem;
NewItem^.Pred:=CurrItem;
После первой из них:
...2->5->3...
..2.. 5->3..
Ну и после второй:
...2->5->3...
...2<-5->3..
Получили то к чему стремились. :D

Ну а для просмотра всех элементов можно опять-таки поступить двояко: идти от начала к концу или от кноца к началу. Благо у нас теперь есть два указателя!
код Pascal/Delphi

Procedure GoFromBeginToEnd; Var CurItem:PItem;
Begin CurItem:=First; While CurItem<>Nil Do begin // действия с текущим элементом CurItem:=CurItem^.Next //переход к следующему. End;
End;
Procedure GoFromEndToBegin; Var CurItem:PItem;
Begin CurItem:=Last; While CurItem<>Nil Do begin // действия с текущим элементом CurItem:=CurItem^.Pred //переход к предыдущему. End;
End;

Аналогично можно сделать и удаление всех элементов: или от начала, или от конца.

При удалении одного элемента, нужно помнить, что должны остаться переходы от предыдущего элемента к следующему и от следующего к предыдущему:
код Pascal/Delphi

var DelItem; // удаляемый эл-т
... DelItem^.Pred^.Next:=DelItem^.Next; // переход от предыдущего к следующему DelItem^.Next^.Pred:=DelItem^.Pred; // от следующего - к предыдущему // ссылки сохранены - можно удалять: Dispose(DelItem);
...


ну вот и очереди второго типа вроде разобрались.

III-ый тип очередей
Тип записи (количество ссылок) зависит от задачи. Например, в случае решения какой-нить задачи, связанной с шахматной доской, где ходить разрешается только в четыре строны можно воспользоваться следующей записью:
код Pascal/Delphi

Type PItem=^TItem; TItem=Record Data:String; Up:PItem; // клетка вверх Down:PItem; // клетка вниз Left:PItem; // клетка влево Right:PItem // клетко вправо End;

Реализации работ с такой структурой оставляется читателю :D
Скажу только что граничные клетки, не будут иметь ссылок или вниз (Down=Nil), или вверх (Up=Nil), влево (left=Nil), вправо (Right=Nil). А четыре клетки не будут иметь сразу по две ссылки (Down=Nil,Left=Nil; Down=Nil,Reght=Nil; и т д).

Pascal и Delphi   Теги: Delphi



Редакция портала:

Благодарим за просмотр этой информации на нашем компьютерном портале. Надеемся, что обзор Что такое очередь?, в разделе Pascal и Delphi вам понравился. Есть небольшая рекомендация, если вы хотите быть в курсе всех событий сферы информационных технологий, то рекомендуем зарегистрироваться на портале www.stfw.ru.


Живая лента

•  Google: счет идет на недели и многие сайты попадут в Mobile-first index - 25.02.2018: STFW.Ru: К примеру, один из самых частых вопросов, который в эти дни адресовался


•  Темной темы в Android 9 не будет - 25.02.2018: STFW.Ru: На днях в сети появились слухи о том, что в Android 9 появится темная тема, она же


•  Рендеры планшета Huawei MediaPad M5 Pro опубликованы в сети - 25.02.2018: STFW.Ru: В интернете получили распространение полуофициальные рендеры планшетного


•  Представлен сильно переоцененный смартфон Land Rover Explore - 25.02.2018: STFW.Ru: Компания Land Rover, производитель известных своей надежностью внедорожников


•  В смартфон Energizer Power Max P490S встроили большой дисплей и четыре камеры - 25.02.2018: STFW.Ru: На Mobile World Congress 2018, выставке, которая откроется уже завтра, состоится анонс


•  Бюджетный Huawei Y3 (2018) работает на Android 8.1 - 25.02.2018: STFW.Ru: Смартфон Huawei Y3 (2018) готовится прийти на замену прошлогоднему Huawei Y3 (2017),