Home Misc Implementing a Queue

Implementing a Queue

by nikoo28
0 comment

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.

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More