Лекция: FIFO (FIRST INPUT — FIRST OUTPUT)

Рис. 2.12

1. Операция проверки пустоты очереди empty

if(frnt == NULL && rear == NULL; printf(«Очередь пуста.»);

2. Операция удаления элемента из очереди remove (рис. 2.13)

x=frnt->infо; p=frnt;

frnt=frnt->ptrn; free(p);

in\Wn —A info ptrn—■*■

frnt

•1Г

frnt

Начало очереди

Рис. 2.13

3. Операция помещения элемента в очередь insert (рис. 2.14)

p=(struct NODE*)malloc(sizeof(struct NODE)); p->ptrn=NULL;

p->info=x;

rear->ptrn=p;

rear=p;

ptrn

Л

Rear

ptrn=NULL ---►I info ptrn i

Rear

Конец очереди

Рис. 2.14

Недостатки представления очереди и стека в виде связанного списка:

• Элемент списка занимает в оперативной памяти больше места, чем элемент массива.

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