Программирование на языке высокого уровня. Марапулец Ю.В. - 70 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

2.9.4.Очереди
Очередь - частный случай однонаправленного списка, добавление в который про-
изводится с одного, а исключение - с другого конца. Для способа хранения данных в
очереди есть общепринятый термин -
FIFO (first in - first out, «первый пришел - первый
ушел»).
Простейший способ представления очереди последовательностью, размещенной от
начала списка, не совсем удобен, поскольку при извлечении из очереди первого элемен-
та все последующие придется постоянно передвигать к началу. Альтернатива: у очереди
должно быть два указателя - на ее начало в списке и на ее конец. По мере постановки
элементов в очередь ее конец будет продвигаться к концу списка, то же самое будет
происходить с началом при исключении элементов. Выход из создавшегося положения -
«зациклить» очередь, то есть считать, что за последним элементом списка следует опять
первый. Подобный способ организации очереди еще иногда называют циклическим бу-
фером (рис. 2.5).
Рис. 2.5. Структура очереди
В отличие от стека указатель на конец очереди ссылается не на последний занятый,
а на первый свободный элемент списка. В программировании очереди наиболее часто
применяются в моделировании, диспетчеризации задач, буферизированном вво-
де/выводе.
Рассмотрим пример очереди. Как и ранее допустим, что очередь состоит из целых
чисел Value, то есть описание элемента очереди выглядит следующим образом:
struct X
{
int Value;
X *p;
};
Первоначально создадим первый элемент очереди с помощью функции FirstEle-
ment(), исходный код которой аналогичен приведенному ранее при инициализации сте-
ка. Функция создает первый элемент, получая его значение A в качестве параметра и
выделяя под него память:
X * FirstElement(int A)
70
      2.9.4.Очереди

      Очередь - частный случай однонаправленного списка, добавление в который про-
изводится с одного, а исключение - с другого конца. Для способа хранения данных в
очереди есть общепринятый термин - FIFO (first in - first out, «первый пришел - первый
ушел»).
      Простейший способ представления очереди последовательностью, размещенной от
начала списка, не совсем удобен, поскольку при извлечении из очереди первого элемен-
та все последующие придется постоянно передвигать к началу. Альтернатива: у очереди
должно быть два указателя - на ее начало в списке и на ее конец. По мере постановки
элементов в очередь ее конец будет продвигаться к концу списка, то же самое будет
происходить с началом при исключении элементов. Выход из создавшегося положения -
«зациклить» очередь, то есть считать, что за последним элементом списка следует опять
первый. Подобный способ организации очереди еще иногда называют циклическим бу-
фером (рис. 2.5).




                               Рис. 2.5. Структура очереди

     В отличие от стека указатель на конец очереди ссылается не на последний занятый,
а на первый свободный элемент списка. В программировании очереди наиболее часто
применяются в моделировании, диспетчеризации задач, буферизированном вво-
де/выводе.
     Рассмотрим пример очереди. Как и ранее допустим, что очередь состоит из целых
чисел Value, то есть описание элемента очереди выглядит следующим образом:

struct X
{
        int Value;
        X *p;
};

     Первоначально создадим первый элемент очереди с помощью функции FirstEle-
ment(), исходный код которой аналогичен приведенному ранее при инициализации сте-
ка. Функция создает первый элемент, получая его значение A в качестве параметра и
выделяя под него память:

X * FirstElement(int A)


                                           70

Страницы