1. Очереди

Списки - Динамические структуры данных.

Очередь - линейный список, доступ к элементам которого происходит по принципу FIFO (First In and First Out - первым пришел и первым ушел).

Для очереди характерны две операции - Занесение элемента в очередь и выбор элемента из очереди. В очереди доступны две позиции - начало (из этой позиции происходит выбор) и конец (в эту позицию заносится входящий элемент).

Произвольный доступ к элементам, в отличии от массивов, не допускается.

Применение:

диспетчеризация задач операционной системой (системная задача);
буферизация ввода/вывода (системная задача);
моделирование процессов (прикладная задача).

Машина Тьюринга

Пример программы с процедурами постановки и выбора из очереди - Queue_Test.

Функция qretrieve() извлекает из очереди первый элемент; хранившиеся в этом элементе данные разрушаются. Если из очереди удалены все элементы, она становится пустой. На самом деле qretrieve() в этом примере не разрушает информацию, но информацию можно считать удаленной, так как дальнейший доступ к ней невозможен.

Программа создания очереди на языке "Паскаль" // FIFO First In - First Out Очередь // Queue Programm Queue_Test; varq:array[0..30] of Integer; qnext,qindex,qlength:Integer; procedure qstore(i:Integer); beginif (qnext+1)<qlength then beginqnext:=qnext+1; q[qnext]:=i end elsewriteln('Мест нет') end;function qretrieve():Integer; beginif qindex=qnext then begin writeln('Очередь пуста'); qretrieve:=0; end else beginqindex:=qindex+1; qretrieve:=q[qindex] end; end; begin Содержимое очереди qlength:=30; qnext:=0; qindex:=0; qstore(1); 1 qstore(2); 1 2 qstore(3); 1 2 3 qretrieve(); {возвращает 1} 2 3 qstore(4); 2 3 4 qretrieve(); {возвращает 2} 3 4 qretrieve(); {возвращает 3} 4 qretrieve(); {возвращает 4} Очередь пуста end.

Циклическая очередь

Программа Queue_Test останавливается, когда будет достигнут определенный размер массива, используемого для хранения очереди.

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

Индексы сохранения qnext и извлечения qindex циклически возвращаются к началу массива (0). В такую очередь можно поместить любое количество элементов (если они не только помещаются, но и извлекаются из очереди).

Если qindex на 1 больше qnext - очередь заполнена и запись новых элементов невозможна, пока не будут прочитаны элементы, хранящиеся в очереди в данный момент. Если qindex=qnext - очередь пуста. В остальных случаях существует место для помещения по крайней мере еще одного элемента.

Программа создания циклической очереди на языке "Паскаль" // FIFO First In - First Out Очередь // Queue Programm Queue_Test; var q:array[0..30] of Integer; qnext,qindex,qlength:Integer; procedure qstore(i:Integer); beginif (qnext+1)<>qlength then beginq[qnext]:=i; qnext:=qnext+1; if qnext=qlength then qnext:=0 {Циклический переход} end elsewriteln('Мест нет') end;function qretrieve():Integer; beginif qindex=qlength thenqindex:=0; {Циклический переход} if qindex=qnext then beginwriteln('Очередь пуста'); qretrieve:=0; end else begin qretrieve:=q[qindex]; qindex:=qindex+1 end; end; begin Содержимое очереди qlength:=30; qnext:=0; qindex:=0; qstore(1); 1 qstore(2); 1 2 qstore(3); 1 2 3 qretrieve(); {возвращает 1} 2 3 qstore(4); 2 3 4 qretrieve(); {возвращает 2} 3 4 qretrieve(); {возвращает 3} 4 qretrieve(); {возвращает 4} Очередь пуста end.

[ Назад | Вперед ]

Хостинг от uCoz