Очередь
Очередью называют одномерную структуру данных с дисциплиной обслуживания "первый пришел – первый ушел". Такую дисциплину обслуживания также называют 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) Вычислите значение U1000000, если Un=Un-1+2Un-2-3Un-3 и U0=U1=U2=U3=1
Дата добавления: 2014-12-02; просмотров: 819;