Курсовая работа: Динамические структуры данных. Решение задач. Стек. Очередь. Дек

Очередь можно представить в виде звеньев, каждая из которых состоит из двух полей: первое – поле элемента, второе – поле ссылки на следующий элемент очереди.

Для очередей применимы следующие операции:

· Сделать пустой.

· Добавить в очередь.

· Взять из очереди.

· Очередь пуста.

· Очередной элемент.

Реализация очереди на основе линейного списка

Описание типа переменных для реализации очереди: пользуемся рекурсивным описанием полей:

Type typeelem=Integer; тип элемента очереди

connect=^data; рекурсивное определение указателя

data=Record

elem:typeelem; тип информационной ячейки

next:connect тип указателя

End;

В этом случае каждое звено содержится в указателе предыдущего звена.

Процедура инициализации очереди включает в себя выделение памяти для создания новой ячейки, указатели присваиваются равными новой ячейке, указатель на следующее звено равно nil:

Процедура распечатки содержимого очереди: независимой переменной присваиваем значение указателя начала, задаем цикл, до того момента как указатель не будет равен nil; выписываем содержимое звена и указателю задаем значение следующего звена:

S: =Sn;

While s<>nil do begin

Write;

S: =s^. Next; end;

Функция проверки на пустоту очереди выглядит следующим образом:

Empty : = Sn = SK ;

Функция может принимать два значения. Если начало и конец совпадают, то функция равна правде, и наоборот: не совпадают – лжи.

Процедура вставки:

new;

P ^. Next : = nil ;

P^. Elem: =x;

Sk^. Next: =p;

sk := p ;

создается новое звено, указатель которого равен nil, информационной ячейке придается какое-то значение, и указатель конца передвигается к этому звену.

Очередной элемент очереди: функции присваивается значение первого элемента, указатель начала передвигается на одно звено.

Remove= Sn^. Elem;

Sn: =Sn^. Next ;

Sk