Опашка. Основни операции.

Опашка се нарича списък, при който операцията включване на елемент е допустим само за единия край на списъка, който се нарича край на опашката, а операцията изключване на елемент е допустима само за другия край на списъка, който се нарича начало на опашката. Възможен е пряк достъп само до елемента, който се намира в началото на опашката. Синоним на опашка е термина FIFO (first in – first out).

При организация на последователни опашки се използват два номера на елементи f и r. f указва елемент, който се намира непосредствено преди първия елемент в опашката и r е номерът на последния елемент в опашката.

Алгоритъм за добавяне на елемент:
r = r + 1, x[r] = addvalue

Алгоритъм за изключване на елемент:
f = f + 1, savevalue = x[f]


Тази реализация на основните операции с опашка е твърде разточителна по отношение на памет, тъй като при добавяне и изключване на елементи, опашката се движи в паметта. Удачно е тези алгоритми да се използват когато опашката често става празна и в този случай запълването може да започне отново в началото на участъка от паметта, разпределен за опашката.

Друга реализация на опашка е методът на пръстена – при този метод се счита, че елементите образуват затворен контур в паметта с дължина M елемента – това означава, че след елемента с номер M стои елементът с номер 1. Така ако общия брой на елементите не надхвърля M-1 е възможно добавяне и изключване на елементи без това да води до недостиг на оперативна памет. За удобство ще номерираме елементите от 0 до M-1.

Алгоритъм за добавяне на елемент:
r = (r+1) mod M, x[r] = addvalue

Алгоритъм за изключване на елемент:
f = (f+1) mod M, savevalue = x[f]

Тъй като са възможни конфликтни ситуации при добавяне на елемент към пълна опашка или при изключване на елемент от празна опашка, алгоритмите за добавяне и изключване могат да се модифицират.

Алгоритъм за добавяне на елемент:
ако (r+1) mod M == f, препълване, стоп
иначе r = (r+1) mod M, x[r] = addvalue


Алгоритъм за изключване на елемент:
ако r == f, празна опашка, стоп
иначе f = (f+1) mod M, savevalue = x[f]


Примерна програма:

  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define M 100
  6.  
  7. typedef float ElementType;
  8.  
  9. struct Queue
  10. {
  11.     int r, f;
  12.     ElementType QueueArray[M];
  13. };
  14.  
  15. void pushq(struct Queue *q, ElementType x)
  16. {
  17.     if((q->r + 1) % M == q->f)
  18.     {
  19.         printf ("Препълване! ");
  20.         exit(1);
  21.     }
  22.     q->r = (q->r + 1) % M;
  23.     q->QueueArray[q->r] = x;
  24. }
  25. ElementType popq(struct Queue *q)
  26. {
  27.     if(q->r == q->f)
  28.     {
  29.         printf("Празна опашка! ");
  30.         exit(1);
  31.     }
  32.     q->f = (q->f + 1) % M;
  33.     return q->QueueArray[q->f];
  34. }
  35.  
  36. void main()
  37. {
  38.     struct Queue mem = {0, 0}; //създаване на празна опашка
  39.     ElementType y = 3.14f;
  40.  
  41.  
  42.     int i;
  43.     for(i = 1; i <= 99; i++)
  44.         pushq(&mem, y+=1.1f);
  45.  
  46.     for(i = 1; i <= 99; i++)
  47.         printf("%.2f ", popq(&mem));
  48. }