REN

Queue is a data structure which allows data in it come or go with a FIFO (First In First Out) sequence. Queue could either be implemented with arrays or linked lists. In this article, I'll use array to describe queue in C Language.

Compared with being implemented in linked list, the queue implemented in array has a queue size and we set a "head pointer" head and a "tail pointer" rear always indicates the head and tail of the queue respectively; Note that head and rear are not real pointers, they're just indices of the array. Note that there're a lot of methods of representing queue empty or full, I just use, in my opinion, the most simple way to represent: When the queue is empty, the head equals rear, which means the rear is always indicating the next index of available slot of queue. Now the problem is that with some data are moved out from queue and some data are inserted into queue, when the head reaches the length of queue, although the queue has empty slots, we cannot use it because rear will exceed the array boundary.

To solve this problem, we use module operation to make the queue circular. That means when head or rear will exceed the array boundary, it wraps around to the first index. Note that we need an idle slot, otherwise the condition on queue empty and queue full is the same.

The data structure of queue is quite simple. Note that the type of base field could be any other types, even a struct.

typedef struct Queue {
	type* base;
	int head;
	int rear;
	int size;
} Queue;

Initialize

To initialize the queue, we need to set the size of the queue, applying for the dynamic memory space for it; And set head equals to -1 and rear equals to 0

int initialQueue(Queue *q, int size){
	if (NULL == q)
		return -1;
	q->base = (elementType*)malloc(size*sizeof(elementType))	
	if (NULL == q->base)
		return -1;
	q->size = size + 1;
	q->head = 0;
	q->rear = 0;
	return 0;
}

Enter Queue

Insert an element into the tail of queue. Before inserting, we need to check whether the queue is full or not. when (rear + 1) % size = head, the queue is full.

int enQueue(Queue *q, elementType element){
	if (NULL == q)
		return -1;
	if ((q->rear + 1) % q->size == q->head)
		return -1;	// full
	q->base[q->rear] = element;
	q->rear = (q->rear + 1) % q->size;
	return 0;
}

Leave Queue

Pull an element from the head of queue. Before pulling, we need to check whether the queue is empty or not. when head = rear, the queue is empty.

int deQueue(Stack *q, elementType *element){
	if (NULL == q)
		return -1;
	if (q->head == q->rear)
		return -1;	// empty
	q->head = (q->head + 1) % q->size;
	*element = q->base[q->head];
	return 0;
}

Get Queue Length

Get the length of the queue.

int getLength(Queue q) {
	if (NULL == q.base)
		return -1;
	return (q.rear + q.size - q.head) % q.size;
}

Destroy

Free the dynamic memory for the queue.

void destroyQueue(Queue q){
	if (NULL == q.base)
		return;
	free(q.base);
}