1. Очереди
Списки - Динамические структуры данных.
Очередь - линейный список, доступ к элементам которого происходит по принципу FIFO (First In and First Out - первым пришел и первым ушел).
Для очереди характерны две операции - Занесение элемента в очередь и выбор элемента из очереди. В очереди доступны две позиции - начало (из этой позиции происходит выбор) и конец (в эту позицию заносится входящий элемент).
Произвольный доступ к элементам, в отличии от массивов, не допускается.
Применение:
Машина Тьюринга
Пример программы с процедурами постановки и выбора из очереди - Queue_Test.
Функция qretrieve() извлекает из очереди первый элемент; хранившиеся в этом элементе данные разрушаются. Если из очереди удалены все элементы, она становится пустой. На самом деле qretrieve() в этом примере не разрушает информацию, но информацию можно считать удаленной, так как дальнейший доступ к ней невозможен.
Программа создания очереди на языке "Паскаль"// FIFO First In - First Out Очередь // Queue Programm Queue_Test; var
qnext,qindex,qlength:Integer; begin
begin
q[qnext]:=i else
begin
begin
qretrieve:=0; else begin
qretrieve:=q[qindex]
|
Циклическая очередь
Программа Queue_Test останавливается, когда будет достигнут определенный размер массива, используемого для хранения очереди.
В циклической очереди используется массив, в котором храняться элементы очереди как циклический список, а не линейный.
Индексы сохранения qnext и извлечения qindex циклически возвращаются к началу массива (0). В такую очередь можно поместить любое количество элементов (если они не только помещаются, но и извлекаются из очереди).
Если qindex на 1 больше qnext - очередь заполнена и запись новых элементов невозможна, пока не будут прочитаны элементы, хранящиеся в очереди в данный момент. Если qindex=qnext - очередь пуста. В остальных случаях существует место для помещения по крайней мере еще одного элемента.
Программа создания циклической очереди на языке "Паскаль"// FIFO First In - First Out Очередь // Queue Programm Queue_Test; var
qnext,qindex,qlength:Integer; begin
begin
qnext:=qnext+1; if qnext=qlength then
else
begin
begin
qretrieve:=0; else begin
qindex:=qindex+1
|