Implementing a Queue

Before implementing a queue, we must know the basic operations that should be available for a queue.

Main Queue Operations:-

• enQueue(int data) :- Inserts an element at the end of the queue.
• int deQueue():- Removes and returns the element at the front of the queue.

Auxiliary Queue Operations:-

• int front():- Returns the first element at the queue, without removing it.
• int queueSize():- Returns the size of the queue.
• int isEmptyQueue():- Indicates whether no elements are present.

We can implement a queue using an ADT (Abstract Data Type). To implement a queue, we can use the structure for the node of a Linked List:-

struct node
{
	int data;
	struct node * next;
};

Further, a Queue is represented by a front end and a rear end. Thus, we can extend the data structure of the Linked List node to use it in our queue.

struct queue
{
	struct node * front;
	struct node * rear;
};

Now, to ENQUEUE, we need to add a node to the original queue. If the queue is initially NULL, we need to allocate new memory and assign the value to a node and update the FRONT and REAR. However, if the queue is already full, we need to add a new node at the REAR and then update the REAR pointer of the queue.

//implementing a function to EnQueue an element
struct queue * enQueue(struct queue * q, int num)
{
	//creating a node to add
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = num;
	temp -> next = NULL;

	//check if the queue is NULL
	if(q==NULL)
	{
		q = (struct queue*)malloc(sizeof(struct queue));

		//overflow check
		if(!q)
		{
			printf("OVERFLOW EXCEPTION");
			return NULL;
		}

		//here we need to update the FRONT pointer
		q -> front = temp;
	}
	else
	{
		//We assign the NEXT of last node to the temp node we created
		q -> rear -> next = temp;
	}

	//We need to update the REAR pointer in both the cases
	q -> rear = temp;

	//return the FRONT
	return q;
}

The DEQUEUE, operation involves to print the FRONT of the node and then UPDATE the FRONT pointer. Printing the value is totally optional.

//implementing a DEQUEUE operation
struct queue * deQueue(struct queue * q)
{

	//underflow check
	if(q == NULL)
	{
		printf("UNDERFLOW EXCEPTION\n");
		return NULL;
	}

	printf("The element dequeued is:- %d\n",q->front->data);

	struct queue * temp = q->front;

	//We need to update the FRONT pointer
	q -> front = q->front->next;

	//free the memory
	free(temp);

	return q;
}

The print operation of the queue can also be implemented as follows.

void printer(struct queue * q)
{
	struct node * x = q->front;
	while(x != NULL)
	{
		printf("%d ",x->data);
		x = x->next;
	}
}

A working demo of the program can be downloaded here containing the main function as well. Use your favorite editor like gEdit, Notepad++, vim to open it.