4.5.2. Очереди.
Очередью называется упорядоченный набор элементов, которые могут удаляться с одного ее конца (называемого началом очереди) и помещаться в другой конец этого набора (называемого концом очереди) (рис. 5.5).
Ее также называют структурой данных, организованной по принципу FIFO (First In First Out, первый вошел — первым вышел). Как и для стека, максимальное число элементов в очереди не должно лимитироваться используемым программным обеспечением: память должна запрашиваться и освобождаться динамически по мере того, как в очередь добавляются новые, и из нее удаляются находящиеся там элементы.
Базовые операции, выполняемые над очередью, очевидны:
insert — добавить в очередь новый элемент
remove — удалить из очереди первый элемент
Интерфейс с программами, обслуживающими очередь, приведен в листинге 5.4.
/* Интерфейс для работы с очередью */
#define QUEUE struct queue // [kju:]
QUEUE
{
int info;
QUEUE *next;
};
extern void insertItem(QUEUE **ppQueue, int nItem);
extern int removeItem(QUEUE **ppQueue, int *nError);
Представленные функции являются аналогами функций push и pop, применяемыми для работы со стеком, и все что говорилось там о передаче параметров и индикации ошибки, в полной мере относится и к представленным функциям.
Работу с очередью можно организовать двумя способами:
1. Используя дополнительные переменные для начала и конца очереди.
2. Используя переменную только для начала очереди, перемещаясь в конец на основе внутренних связей.
Какой из вариантов больше подходит вам — дело вкуса, мы же остановились на втором. Принципы работы с очередью продемонстрированы на рис. 5.6.
/* Реализация функций работы с очередью */
#include <malloc.h>
#include "queue.h"
void insertItem(QUEUE **ppQueue, int nItem)
{
QUEUE *pNewItem;
QUEUE *pCurItem = *ppQueue; // Текущий — начало очереди
QUEUE *pPreItem = 0;
while(pCurItem)
{
// Перемещаемся в конец очереди
pPreItem = pCurItem;
pCurItem = pCurItem->next;
}
// Запрашиваем память под структуру для элемента очереди
pNewItem = (QUEUE *)malloc(sizeof(QUEUE));
// Заполняем информационное поле
pNewItem->info = nItem;
if(pPreItem)
{
// Если очередь пуста, делаем новый элемент ее началом
pNewItem->next = 0;
pPreItem->next = pNewItem;
}
else
{
//В противном случае помещаем его в конец
*ppQueue = pNewItem;
(*ppQueue)->next = 0;
}
} int removeItem(QUEUE **ppQueue, int *nError) {
QUEUE *pOldItem = *ppQueue;
int nOldlnfo = 0;
if(*ppQueue)
{
// Если очередь не пустая — извлекаем элемент
nOldInfo = pOldItem->info;
*ppQueue = (*ppQueue)->next;
//и освобождаем память
free(pOldItem);
*nError = 0;
}
else
// В противном случае ошибка
*nError =1;
return nOldlnfo; }
Обратите внимание, что код функции removeItem полностью совпадает с кодом функции pop для стека, поэтому более подробно рассмотрим функцию insertItem.
Сначала создается локальная переменная *pCurItem, являющаяся указателем на структуру queue, которая инициализируется значением начала очереди — *ppQueue. Затем описывается локальная переменная *pPreItem того же типа, которая инициализируется значением 0. И наконец, создается локальная переменная для хранения адреса нового элемента очереди — *pNewItem.
Далее организуется просмотр очереди до достижения ее конца, после чего указатель pPreItem содержит адрес последнего элемента queue в очереди. Далее запрашивается память под новый элемент очереди pNewItem, полю Info этой структуры присваивается значение nItem. Если очередь не пуста, то полю next новой структуры присваивается значение 0, которое показывает, что это теперь последний элемент в очереди, а полю next бывшего последнего элемента присваивается значение адреса новой структуры pNewitem. Если же очередь пуста, то указатель на начало очереди принимает значение адреса нового элемента.
Мы рассмотрели простейший пример — линейную очередь. Помимо нее часто используется так называемая циклическая очередь, в которой последний элемент указывает на ее начало.