Инициализация очереди

Пример

ТОРГОВЫЙ ЗАЛ

Операция insert(q,x)

ПОКУПАТЕЛИ

Операция empty(q)

КАССА

НАБЛЮДАТЕЛЬ

J

z

с^°^г

операция x=remove(q)

Рис. 2.9. Графическое представление очереди Объявление пустой очереди

#define Maxg 5

float git[Maxg];

frnt=l; rear=0;

Игнорируя возможность переполнения очереди, операцию insert(g, x) запишем следующим образом:

геаг++; git[rear] = х;,

а операцию х = remove(g) так:

x = git[frnt\;

frnt++;.

На рис. 2.10 показано, что произойдет при таком представлении.

	git		git		git		git
5 4 3 2		5 4 3 2 1		5 4 3 2 1	с	5 4 3 2 1	e d с
	с
	b a
frnt= rear=	1 rear= 0 frnt=	3 frnt= 1 rear=	1 rear= 3 frnt=:	5 3

Рис. 2.10. Элементы в очереди

Изначально очередь пуста. Размер массива git будет 5. В результате выполнения операции insert и remove в очереди будут находиться три элемента. Больше поместить нельзя.

Одним из решений этой проблемы является модификация операции remove таким образом, чтобы при удалении элемента смещать очередь к началу.

х = git[0];

for(i=0; i<rear-l; i + +[ {

git [i

git[i+1];

rear-

Переменной frnt не требуется, так как первый элемент — начало очереди. Для пустой очереди rear = 0. Метод непроизводителен, так как требует перемещение оставшихся элементов.

Другой способ предлагает рассматривать массив в виде циклического связанного списка. Недостаток — трудно определить, когда очередь пуста, так как условие rear <frnt не выполняется.

Рассмотрим следующий пример (рис. 2.11). Одним из способов решения проблемы является соглашение о том, что frnt является индексом элемента, предшествующего первому элементу. В этом случае для пустой очереди frnt = rear.

	e	5-ти элементный		е	frnt=3
4 3 2	масив. Если необходимо разместить элемент f, то он пишется в первую	4 3 2	rear=1 rear<frnt, rear=1 rear<fmt, но
d	d
с	с
			f	очередь
	позицию.	не пуста
frnt=		frnt-
rear=0	rear=3

Рис. 2.11. Пример

#define Maxg
float	git[Maxg];
f rnt =	= Maxg;
rear =	= Maxg;

Операция empty

if(frnt == rear) empty=l; else empty =0;

Операция remove

if	(empty	== 1)
	printf(	"Очередь	пуста")	r
if	(frnt =	= Maxg-1)	frnt =	0;
else frnt	= frnt +	1;
remove = g	it[frnt];

При реализации вставки необходимо контролировать ситуацию переполнения, при которой frnt = rear. Это же условие характеризует пустую очередь. Одно из решений проблемы — очередь растет до Maxg-\.

Операция insert

/^выделение места для элемента*/ if (rear == Maxg - 1) rear = 0; else rear = rear + 1;

/^проверка	на переполнение	*/
if (rear =	= frnt)
printf(	"Переполнение."	);
git [rear]	= x;

Дата добавления: 2014-11-29