Торговый зал

Рис. 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. Пример