Введение в информационные системы. Брюхомицкий Ю.А. - 51 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

51
Рис. 4.5. Рост и сокращение стека при связанном представлении
Стековые структуры удобны в тех случаях, когда нужно быстро выпол-
нить операции включения-исключения без оценки смысла данных.
Например, при ведении связанного списка, со временем, в различных
участках памяти образуются многочисленные свободные ячейки. Для того что-
бы непрерывно
использовать эти ячейки в новых структурах данных, их удобно
связать вместе и организовать в виде стека свободной памяти. Алгоритм,
управляющий сбором таких свободных ячеек, называется “сборщиком мусора”.
Стековые структуры широко используются в трансляторах, при реали-
зации вложенных подпрограмм и многоуровневых прерываний, а также при
решении задач, алгоритмы которых хорошо описываются рекурсивным
мето-
дом.
Очередь. Очередь − это линейная структура переменного размера. Ис-
ключение элементов из очереди допускается с одного конца − с начала очереди.
Включение элементов возможно лишь в противоположный конец − в конец
очереди. Данные в такой структуре обрабатываются в порядке их поступления
по принципу: “первым пришел – первым ушел”. Структуру
очереди называют
также FIFO (от англ. First In, First Out). Наглядной иллюстрацией принципа
работы очереди является любая очередь (в обиходном смысле слова) в ожида-
нии какого-либо обслуживания, например очередь автомобилей у светофора,
ожидающая открытия светофора. Автомобиль, первым подъехавший к светофо-
ру, первым проедет перекресток, т.е. первым окажется исключенным из очере-
ди.
Доступ к
элементам очереди осуществляется по указателям начала и
конца. Указатель начала определяет элемент очереди, который первым будет
читаться или исключаться. Указатель конца устанавливается на свободную
ячейку памяти, следующую за последней записью в очереди. Именно в эту
ячейку разместится вновь пришедшая запись.
Для реализации структуры очереди в памяти ЭВМ используется как по-
следовательное, так и связанное представление данных. При последовательном
представлении под очередь резервируется блок памяти, внутри которого оче-

Страницы