Принципы работы с динамической очередью

Условно очередь можно представить в виде трубки с шариками.

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

1. на начало очереди (возьмём идентификатор BegQ);

2. на конец очереди (возьмём идентификатор EndQ).

Кроме того, для освобождения из памяти удаляемых элементов требуется дополнительный временный указатель (возьмём идентификатор P). Дополнительный указатель также часто используется в других ситуациях для удобства работы с очередью.

• Создание очереди

  1. Исходное состояние:

2. Выделение памяти под первый элемент очереди:

3. Установка указателей на созданный первый элемент:

• Добавление элемента очереди.

1. Исходное состояние:

2. Выделение памяти под новый элемент и занесение в него информации:

3. Установка связи между последним элементом очереди и новым, а также перемещение указателя "конец очереди" EndQ на новый элемент:

• Удаление элемента очереди.

1. Исходное состояние:

2. Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя P:

3. Переустановка указателя начала очереди BegQ на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:

Пример 1.

Hиже приводится пример программы, заносящей в очередь 10 символов, набранных на клавиатуре пользователем, и выдающей их на экран в той же последовательности. В ней используются следующие процедуры:

• процедура AddEl(val:real) используется для добавления к очереди нового элемента val;

• процедура GetDelEl(var val:real) используется для удаления из очереди элемента val.

Program queue;

Type Tptr=^TElem; {Тип указателя на элемент очереди }

TElem=record { Тип элемента очереди : }

inf : char; { информационная часть }

link : Tptr { соединительная часть }

end;

Var begq,endq : Tptr; { Указатели на начало и конец очереди }

value : char;

i : byte;

Procedure AddEl(val : char); { Процедура добавления элемента }

Var p:tptr; { Вспомогательный указатель }

begin

new(p);

p^.inf:=val;

p^.link:=nil;

if endq=nil then begq:=p

else endq^.link:=p;

endq:=p

end;

Procedure GetDelEl(var val : char); { Процедура удаления элемента }

var p : TPtr; { Вспомогательный указатель }

begin

val:=begq^.inf;

p:=begq; begq:=p^.link;

if begq=nil then endq:=nil;

dispose(p)

end;

begin

new(begq); { Создание указателей на начало и конец очереди }

new(endq);

begq:=nil; { Установление указателей на nil }

endq:=nil;

for i:=1 to 10 do

begin

writeln(' введите символ');

readln(value);

addel(value);

end;

i:=1;

while begq<>nil do

begin

getdelel(value);

writeln(i,'-й символ - ',value);

inc(i)

end

end.

Пример 2. Сформировать две очереди по 5 элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди).

Дек

Дональд Кнут ввел понятие усложненной очереди, которая называется дек (от англ. deq - double ended queue, т.е. очередь с двумя концами).

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

В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека.

Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Дек удобнее представлять двусвязным (разнонаправленным) линейным списком.

Операции над деком:

• включение элемента справа;

• включение элемента слева;

• исключение элемента справа;

• исключение элемента слева;

• определение размера;

• очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

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

Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.