Последователна опашка. Основни операции.

Последователна опашка. Основни операции.

<картинка>
Два указателя( или 2 номера на елементи на опашка ). F сочи елемента, който се намира преди първия елемент на опашката. R - сочи края на опашката.( има фиктивен елемент преди първия ).

Динамика на опашката
Добавяне: R = R + 1, A(R) = x.
Изключване: F = F + 1, x = A(F).

Този метод на включване и изключване на елемент е твърде разточителен по отношение на ОП, ако се включват и изключват много елементи, опашката се движи в ОП и очевидно ще се създават конфликтни ситуации. Удачно е да се използва, когато опашката често остава празна( F == R ). В този случай запълването става от началото на свободен участък от паметта. Друга реализация - метод на пръстена - счита се, че елементите образуват затворен контур с дължина М, елемента след този с номер М е елемента с номер 1. Така, ако общия брой никога не надхвърля М - 1, е възможно добавяне на елемент в опашката без недостиг на ОП.

Динамика на опашката( метод на пръстена ):

Добавяне:
if R == M then R = 1 else R = R + 1;
if R == F then overflow and stop
else A(R) = x;

Изключване:
if R == F then empty and stop
if F == M then F = 1
else F = F + 1
x = A(F)

За пореден път: Не се прави така. За домашно: всеки да погледне и да намери какво точно е грешно в долния код.

#define M 150
typedef double ELEMENT_TYPE
 
struct Queue
{
    int f;
    int r;
    ELEMENT_TYPE queue_array[M];
};
 
void enqueue( Queue *q, ELEMENT_TYPE x )
{
    if ( q->r == M )
        q->r = 1;
    else
        q->r++;
    if ( q->r == q->f )
    {
        printf( " \n Препълване" );
        exit(1);
    }
 
    q->queue_array[q->r - 1] = x;
}
 
ELEMENT_TYPE dequeue( Queue *q )
{
    if ( q->r == q->f )
    {
        printf( " \n Празна Опашка " );
        exit(1);
    }
    if ( q->f == M )
        q->f = 1;
    q->f++;
    return q->queue_array[q->f - 1];
}
 
void main()
{
    Queue mem = {1,1};
    ELEMENT_TYPE x = 3.14, y;
    y = dequeue( &mem );
    y = dequeue( &mem ); // ще се изведе "празна опашка" и тн..
}

Проверка дали опашката е празна и съобщението за грешка могат да се реализират с отделни функции.