На этом шаге мы рассмотрим понятие очереди на базе однонаправленного списка.

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

Рис.1. Схематичное изображение очереди

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

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

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

Над динамической структурой - очередью - выполняются следующие операции:
• начальное формирование очереди (запись первой компоненты);
• добавление компоненты в конец очереди;
• определение первого элемента в очереди с последующим извлечением его из очереди.

    Описание компоненты очереди дадим следующим образом:

 Type
   PtrRec = ^Rec;
   Rec = Record
       Element : TypeElement;	{информационное поле компоненты очереди}
       pNext   : PtrRec;           {ссылка на следующую компоненту очереди}
      End;

    Для формирования очереди и работы с ней необходимо описать три переменные типа указатель: переменная pBegin определяет начало очереди, pEnd - конец очереди, pAux - вспомогательная:

 Var
   pBegin, pEnd, pAux: PtrRec;

    На следующем шаге мы рассмотрим формирование очереди на базе однонаправленного списка.

Предыдущий шаг Содержание Следующий шаг