Очереди. Реализация в виде массива.

Отметим некоторые случаи особого представления очередей при последовательном распределении памяти. У очереди имеется «голова», откуда извлекаются ранее помещенные в очередь элементы, и «хвост», куда помещаются новые элементы очереди.

N
…	«хвост»
…
…
2	«голова»
1

«Хвост» двигается к концу отведенного массива, а голова освобождает место снизу. Неминуемо переполнение массива, то есть «хвост» нарушит границы массива. Возможно несколько решений:

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

• Позволить очереди подниматься до тех пор, пока останется место для выполнения очередной операции дополнения; как только места больше не будет, сдвинуть всю очередь на все свободное пространство. Это решение более экономично, но тоже требует «бесполезных» усилий по перемещению очереди.

• «Соединить» голову и хвост, и по достижении вершины массива перенести хвост в начало массива (если оно свободно). Этот прием называется использованием «кольцевого буфера». Но в этом случае необходимо постоянно контролировать непересечение хвоста и головы очереди.

Программно кольцевой буфер может быть реализован следующим образом:

typedef struct

{

int anBuffer[CYC_BUF_SIZE];

int nHead;

int nTail;

} CYC_BUF_STRUCT;

void EmptyBuf(CYC_BUF_STRUCT *pBuf)

{

pBuf->nHead = -1;

pBuf->nTail = 0;

}

int AddToBuf(CYC_BUF_STRUCT *pBuf, int nItem)

{

if (GetBufCount(pBuf) < CYC_BUF_SIZE)

{

pBuf->anBuffer[pBuf->nTail++] = nItem;

if (pBuf->nTail == CYC_BUF_SIZE)

pBuf->nTail = 0;

if (pBuf->nHead == -1)

pBuf->nHead = 0;

return SUCCESS;

}

return ERROR;

}

int RemoveFromBuf(CYC_BUF_STRUCT *pBuf, int *pItem)

{

if (GetBufCount(pBuf) > 0)

{

if (pItem != NULL)

*pItem = pBuf->anBuffer[pBuf->nHead];

pBuf->nHead++;

if (pBuf->nHead == CYC_BUF_SIZE)

pBuf->nHead = 0;

if (pBuf->nHead == pBuf->nTail)

EmptyBuf(pBuf);

return SUCCESS;

}

return ERROR;

}

int GetBufCount(CYC_BUF_STRUCT *pBuf)

{

if (pBuf->nHead == -1)

return 0;

else

if (pBuf->nTail > pBuf->nHead)

return pBuf->nTail - pBuf->nHead;

else

return pBuf->nTail - pBuf->nHead + CYC_BUF_SIZE;

}

В приведенном примере для определения области массива, занимаемой элементами, хранящимися в буфере, используются две переменные: Head – индекс первого элемента в очереди, т.е. элемента, который будет первым извлечен из нее; и Tail – индекс первого свободного элемента очереди, т.е. элемента, куда будет помещен следующий добавляемый в очередь элемент. Для того чтобы отличать случай полностью заполненного буфера от случая пустого буфера, используется специальное значение Head = -1, говорящее о том, что буфер пуст (иначе это состояние нельзя было бы отличить от состояния Head = Tail – буфер полностью заполнен).