Структуры и алгоритмы обработки данных. Ключарев А.А - 43 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

43
end;
end;
procedure ClearStack(var ptrStack: PElement);
{Очистка стека}
begin
while ptrStack <> nil do
Del_LineSingleList(ptrStack, ptrStack); {удаляем вершину}
end;
function EmptyStack(var ptrStack: PElement): boolean;
{Проверка пустоты стека}
begin
if ptrStack = nil then EmptyStack := true
else EmptyStack := false;
end;
1.2.10. Очередь
Очередь – это структура данных, представляющая собой последова-
тельность элементов, образованная в порядке их поступления. Каждый
новый элемент размещается в конце очереди; элемент, стоящий в нача-
ле очереди, выбирается из нее первым. Здесь используется принцип
«первым пришел – первым вышел» (FIFO: First Input – First Output).
Очередь можно реализовывать как статическую структуру данных в
виде одномерного массива, а можно как динамическую структуру – в
виде линейного списка (рис. 9).
При реализации очереди в виде статического массива необходимо ре-
зервировать массив, длина которого равна максимально возможной длине
очереди, что приводит к неэффективному использованию памяти.
При такой реализации начало очереди будет располагаться в первом
элементе массива, а рост очереди будет осуществляться в сторону уве-
личения индексов. Однако, поскольку добавление элементов происхо-
дит в один конец, а выборка – из другого конца очереди, то с течением
времени будет происходить миграция элементов очереди из начала мас-
сива в сторону его конца. Это может привести к быстрому исчерпанию
массива и невозможности добавлении новых элементов в очередь при
наличии свободных мест в начале массива. Предотвратить это можно
двумя способами:
– после извлечения очередного элемента из начала очереди осуще-
ствлять сдвиг всей очереди на один элемент к началу массива. При
этом необходимо отдельно хранить значение индекса элемента массива,

Страницы