Queue Data Structure

queue.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*
Coada normala (liniara) implementata ca VECTOR FIFO First In First Out

head = pozitia primului element
tail = urmatoarea pozitie libera pentru inserara
size = numarul de elemente din coada

enqueue --->insereaza la sfarsit
dequeue -----> elimina de la inceput
*/

typedef struct
{
int * array ;
int capacity;
int size ;
int head , tail ;
} QUEUE ;

/* initializare */

void queue_init(QUEUE *q, int capacity) {

        if( capacity <= 0 ) {

        	fprintf(stderr, "Err: capacity invalida\n");

        	exit(EXIT_FAILURE);
        }

        q->array = (int*)malloc((size_t)capacity * sizeof(int));

        if( q->array == NULL ) {

        	fprintf(stderr, "Err: malloc failed\n");

        	exit(EXIT_FAILURE);
        }


        q->capacity = capacity;

        q->size = 0;

        q->head = 0;

        q->tail = 0;
}

/*FREE coada*/
void queue_destroy(QUEUE *q) {

	free(q->array);

	q->array = NULL;

	q->capacity = 0;

	q->size = 0;

	q->head = 0;

	q->tail = 0;
}

bool queue_is_empty(const QUEUE *q) {

	  return q->size == 0;
}

/*
coada liniara este plina daca tail a ajuns la capatul vectorului
*/

bool queue_is_full(const QUEUE *q) {

     return q->tail == q->capacity;
}

void enqueue(QUEUE *q, int key) {

	if(queue_is_full(q)) {
		fprintf(stderr, "Err: overflow - coada este plina\n");
		return;
	}
 
    //tail, rear
	//front , head
	q->array[ q->tail ] = key;
	q->tail++;
	q->size++;
}

int dequeue(QUEUE *q) {

	if(queue_is_empty(q)) {

		fprintf(stderr, "Err: underflow - coada este goala\n");
		return -1;		
	}

	int key = q->array[ q->head ];
	q->head++;
	q->size--;

	return key;
}

/*
Citeste primul element fara sa-l elimne din coada
*/

int front(const QUEUE *q) {

	if(queue_is_empty(q)) {
		fprintf(stderr, "Err: coada este goala\n");
		return -1;
	}

	return q->array[ q->head ];
}

/* Afisare */

void queue_print(const QUEUE *q) {

   if(queue_is_empty(q)) {
   	printf("Coada este goala! {}\n");
   	return;
   }

   printf("HEAD -> ");

   for(int i = q->head; i < q->tail; ++i) {

   	  printf("%d", q->array [ i ]);//*(array + 0) ,*(array + 1) 

   	  if(i < q->tail - 1) {
   	  	 printf(", ");
   	  }

   }

   printf(" <- tail [head = %d, tail = %d, size = %d/%d]\n", q->head, q->tail, q->size, q->capacity);

}

int main(int argc, char const *argv[])
{

	QUEUE q;

	int x;

	queue_init(&q, 8);

	enqueue(&q, 4);
	enqueue(&q, 15);
	enqueue(&q, 2);
	enqueue(&q, 7);

	printf("Coada initiala: \n");
    queue_print(&q);

    printf("\nDupa enqueue(14): \n");
	enqueue(&q, 14);	
	queue_print(&q);


	printf("\ndequeue() = %d\n", dequeue(&q));
	printf("\ndequeue() = %d\n", dequeue(&q));

	printf("\nDupa doua eliminari: \n");
	queue_print(&q);


	printf("\nFRONT = %d\n", front(&q));


	//test overflow

    printf("\nTEST Overflow: \n");
	while(!queue_is_full(&q)) {

		enqueue(&q, 100);
	}

    enqueue(&q, 200);

    queue_print(&q);

    printf("\nGolire coada:\n");

    while(!queue_is_empty(&q)) {

    	x = dequeue(&q);
    	
    	printf("dequeue() = %d\n", x);
    }

    queue_print(&q);

    dequeue(&q);

    queue_destroy(&q);	
	
	return 0;
}