2. Программная реализация очереди на основе массива

Пример 13.1

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#include <malloc.h>

/////////////// Queue for int positive (x>0)

typedef struct

{

int *queue;

int head;

int tail;

int size;

} QUEUE;

int Init(QUEUE* Queue, int nSize);

int Extract(QUEUE* Queue);

int Add(QUEUE* Queue, int nElement);

void Clear(QUEUE* Queue);

int GetSize(QUEUE* Queue);

void Free(QUEUE* Queue);

Программа реализации кольцевой очереди на основе массива – queue.cpp:

#include "queue.h"

/////////////// Queue for int positive (x>0)

//////////////////////////////////////////

int Init(QUEUE* Queue, int nSize)

{

Queue->queue = (int*)malloc(nSize*(sizeof(int)));

if (Queue->queue == NULL) return -1;

Queue->size = nSize;

Queue->head = 0;

Queue->tail = 0;

return nSize;

}

///////////////////////////////////////////

int Extract(QUEUE* Queue)

{

int w;

if (Queue->head == Queue->tail) return -1;

w = Queue->queue[Queue->head];

       if (Queue->head == Queue->size - 1)

Queue->head = 0;

else

Queue->head++;

return w;

}

///////////////////////////////////////////

int Add(QUEUE* Queue, int nElement)

{

if (Queue->tail +1 == Queue->head)

return -1; // Очередь заполнена - запись невозможна!

if ((Queue->tail == Queue->size )&&( Queue->head>1))

Queue->tail=0; //Достигнут конец памяти, выделенной под очередь

// Следует перейти в начало, если там есть свободные элементы

else return –1; //Свободных элементов нет, вырабатываем отказ

Queue->queue[Queue->tail++] = nElement;

return 1;

}

///////////////////////////////////////////

void Clear(QUEUE* Queue)

{

Queue->head = 0;

Queue->tail = 0;

}

///////////////////////////////////////////

int GetSize(QUEUE* Queue)

{

if (Queue->head == Queue->tail)

return 0; // Очередь пуста

if (Queue->head < Queue->tail)

return (Queue->tail - Queue->head);

else

return (Queue->size - (Queue->head - Queue->tail));

}

///////////////////////////////////////////

void Free(QUEUE* Queue)

{ free(Queue->queue); }

Тестовая программа:

#include "queue.h"

/////////////////////////// Print of queue information

void Print(QUEUE *Queue)

{

if (Queue->head == Queue->tail)

printf("\nQueue is empty!");

else

printf ("\nhead=%u, tail=%u, (%d-%d)", Queue->head, Queue->tail,

Queue->queue[Queue->head], Queue->queue[Queue->tail-1]);

}

void main()

{

QUEUE Queue;

Init(&Queue,4); Print(&Queue);

Add(&Queue,10); Print(&Queue);

Add(&Queue,11); Print(&Queue);

Add(&Queue,12); Print(&Queue);

Extract(&Queue); Print(&Queue);

Add(&Queue,13); Print(&Queue);

Extract(&Queue); Print(&Queue);

Add(&Queue,21); Print(&Queue);

Extract(&Queue); Print(&Queue);

Add(&Queue,22); Print(&Queue);

GetSize(&Queue);

Extract(&Queue); Print(&Queue);

Extract(&Queue); Print(&Queue);

Extract(&Queue); Print(&Queue);

Clear(&Queue); Print(&Queue);

Add(&Queue,31); Print(&Queue);

Extract(&Queue); Print(&Queue);

Free(&Queue);

getch();

}