Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


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

Поиск:
Очередь - это набор идущих друг за другом объектов.Представь себе длинный-длинный коридор, на правую сторону этого коридора находятся комнаты 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, я много раз убеждался, что это не так. Поэтому перед началом работы лучше выполнить следующую команду:
Код

  First:=Nil; // и точка!

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

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

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

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

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

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. Для этого надо будет пройтись по всему списку (примерно так как было при удалении всех элементов) от начала до конца,получится примерно следующий код:
Код

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-ую позицию:
Код

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:
Код

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-ый тип очередей
Тип записи следующий:
Код

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

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

First:=Nil;
Last:=Nil

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

// в начало очереди
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;

Вставка в серёдку:
Код

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

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

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;

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

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

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


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

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

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; и т д).
Автор: SPrograMMer






Просмотров: 3744

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную