Инициализация очереди
Пример
ТОРГОВЫЙ ЗАЛ
Операция 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; |