Очередь — это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры, а удаление (извлечение) — только с начала. В англоязычной литературе этот принцип называется FIFO (First Input — First Output, т.е. первый пришёл — первый ушёл).
Примером из реальной жизни может быть очередь из покупателей к кассе в магазине.
Как не трудно понять, очередь — это линейный список, для которого определены всего две основные операции: добавление в конец и извлечение с начала. Значит, удобно иметь два указателя: на начало и конец этой динамической структуры. Но списки бывают односвязные и двухсвязные. Какой использовать? Подойдёт только двухсвязный список. В этом можно будет убедиться при рассмотрении основных алгоритмов для работы с очередью.
На рисунке ниже показано графическое представление очереди. Как и в предыдущих темах, очередь будем строить из целых чисел, например: 3, 5, 1.
Для работы используем структуры Data (данные) и Queue (очередь):
struct Data
{
int a;
};
struct Queue
{
Data d;
Queue *prev; // указатель на предшествующий элемент
Queue *next; // указатель на последующий элемент
};
Затем в программе определяем два указателя:
Queue *Begin = NULL; // Начало очереди
Queue *End = NULL; // Конец очереди
После этого можно начать работать с очередью.
Для очереди используется две основные операции: добавление в конец и извлечение из начала очереди.
1.Добавление в конец очереди:
void Add(Queue **Begin, Queue **End, Data &x)
{
Queue *t = new Queue; // Память под новый элемент
t->d.a = x.a; // Заполнение полей
if(*Begin == NULL || *End == NULL)
{
// Если очередь была пуста
t->prev = NULL;
t->next = NULL;
*Begin = *End = t;
return;
}
// В очереди был хотя бы один элемент
t->prev = *End; // Подключаем новый элемент к имеющимся
(*End)->next = t;
t->next = NULL;
*End = t; // Перенастройка начала очереди
}
Обратиться к функции можно так:
Add(&Begin, &End, x);
где x — объект типа Data.
Как видим, хотя для добавления надо знать только положение конца очереди, здесь в функцию передаётся и её начало. Зачем? А чтобы правильно обработать ситуацию, когда данные добавляются в пустую очередь. Ведь в этом случае требуется настроить указатель Begin на начало очереди.
2. Извлечение данных из начала очереди:
bool Del(Queue **Begin, Queue **End, Data &x)
{
if(*Begin == NULL)
{
cout << "Pustaj Ocheredj" << endl;
return false;
}
Queue *t = *Begin;
x.a = t->d.a; // Заполнение полей
*Begin = t->next;
if(*Begin == NULL) // Удаляется единственный элемент очереди
*End = NULL;
delete t;
return true;
}
Обратиться к функции можно так:
Del(&Begin, &End, x);
где x — объект типа Data.
Разновидностью очередей является двухсторонняя очередь или дек. Она отличается от обычной очереди тем, что добавление и удаление данных допустимо с обоих концов очереди.
Для реализации алгоритмов работы с двухсторонней очередью можно использовать те же структуры, что и для обычной очереди (Data (данные) и Queue (очередь)), необходимо только дополнить основные операции.
Для работы с деком необходимы следующие действия: добавление в начало и конец очереди (последнюю можно взять из примеров для обычной очереди), удаление из начала очереди (берем как для обычной очереди) и с конца очереди.
Всё это несложно реализовать самостоятельно по аналогии с обычной очередью, поэтому ни каких примеров не привожу.
Это очень интересная разновидность очередей. В ней добавление новых данных производится также в конец очереди, а вот выборка — в зависимости от какого-либо правила.
Примером может служить очередь в кассу магазина, где людей с какими-нибудь удостоверениями, например, ветеранов или инвалидов, обслуживают без очереди.
Для представления данных можно использовать те же структуры, что и для обычной очереди, добавление в конец очереди будет таким же, а вот извлечение из очереди требует основательной переделки. При каждом извлечении вначале надо поискать в очереди «внеочередников» (есть такой — его и извлекаем, на этом очередной запрос исчерпан) и только потом работать с остальными в обычном режиме.
Пример. Имеется очередь с приоритетом, в которой хранятся целые числа. Пусть удаление отрицательных чисел будет более приоритетным. Так, если в очереди находятся числа 3, -4, 2, -6, то удаляться они могут только в последовательности: -4, -6, 3, 2.
Всё это не так сложно реализовать самостоятельно, поэтому ни каких программных примеров не приводится.
