Очередь

Очередью называют одномерную структуру данных с дисци­плиной обслуживания "первый пришел – первый ушел". Такую дисциплину обслу­живания также называют FIFO (First In – First Out), что озна­чает то же самое. Все включения в очередь делаются на одном конце, а все исключения – на другом. Очередь может быть пред­став­лена массивом или списком. В этом разделе рассматривается представление очереди массивом (рис 1).

Рис 2. Очередь в массиве

Простейшее решение состоит в том, чтобы иметь два указателя для начала и конца очереди - F и R. F указывает место на начало очереди; R указывает на последний элемент очереди.

При самом простодушном подходе к выполнению операций включение и исключение выполняются следующим образом:

/* Поместить в очередь */ R=R+1; X[R]=Y;

/* Взять из очереди */ F=F+1; Y=X[F];

Заметим, что в процессе выполнения серии включений и исключений, очередь будет ”ползти” вдоль памяти, так как F и R непрерывно увеличиваются. Это означает чрезвычайно расточительное использование памяти. Проблему можно решить, отводя под очередь M позиций и неявно замыкая её в кольцо, так, что за последней позицией следует первая. Пусть очередь представлена структурой:

#define M 8 // длина массива, отводимого под очередь

struct QUEUE{

int Q[M]; // массив, используемый для хранения очереди

int F; // ИНДЕКС первого элемента очереди

int L; // ИНДЕКС ПОСЛЕДНЕГО

bool IsEmpty; // признак пустой очереди

};

QUEUE T; // экземпляр очереди над которой выполняются операции

Тогда включение и исключение примут вид:

bool PutInQueue(int x){

// поместить элемент x в очередь

// возвращает истину в случае успеха

T.L=(T.L==M-1) ? 0 : T.L+1;

if(!T.IsEmpty && T.F==T.L){

return false;

}

T.Q[T.L]=x;

T.IsEmpty=false;

return true;

}

int TakeFromQueue(){

// Взять элемент из очереди T

// функция возвращает взятый из очереди элемент

// если очередь пуста, то возвращается INT_MAX (defined в limits.h)

int z;

bool fl=T.F==T.L;

if(!T.IsEmpty){

z=T.Q[T.F];

T.F=T.F==M-1 ? 0 : T.F+1;

T.IsEmpty=fl;

} else {

z=INT_MAX;

}

return z;

}

Контрольные вопросы

1) По каким правилам элементы помещаются в очередь и удаляются из очереди?

2) Как избежать перемещения очереди по памяти?

3) Вычислите значение U_1000000, если U_n=U_n-1+2U_n-2-3U_n-3 и U₀=U₁=U₂=U₃=1