Applications of Queues

One application of the queue data structure is in the implementation of priority queues required to be maintained by the scheduler of an operating system. It is a queue in which each element has a priority value and the elements are required to be inserted in the queue in decreasing order of priority. This requires a change in the function that is used for insertion of an element into the queue. No change is required in the delete function.

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

struct node
{
	int data;
	int priority;
	struct node *link;
};
void insert(struct node **front, struct node **rear, int value, int priority)
{
	struct node *temp, *temp1;
	temp = (struct node *) malloc(sizeof(struct node));
	/* creates new node using data value
	 passed as parameter */
	if (temp == NULL)
	{
		printf("No Memory available Error\n");
		exit(0);
	}
	temp->data = value;
	temp->priority = priority;
	temp->link = NULL;
	if (*rear == NULL) /* This is the first node */
	{
		*rear = temp;
		*front = *rear;
	}
	else
	{
		if ((*front)->priority < priority)
		/* the element to be inserted has
		 highest priority hence should
		 be the first element*/
		{
			temp->link = *front;
			*front = temp;
		}
		else if ((*rear)->priority > priority)
		/* the element to be inserted has
		 lowest priority hence should
		 be the last element*/
		{
			(*rear)->link = temp;
			*rear = temp;
		}

		else
		{
			temp1 = *front;
			while ((temp1->link)->priority >= priority)
				temp1 = temp1->link; /* find the position and insert the new element */
			temp->link = temp1->link;
			temp1->link = temp;
		}
	}
}

void deleteD(struct node **front, struct node **rear, int *value, int *priority)
{
	struct node *temp;
	if ((*front == *rear) && (*rear == NULL))
	{
		printf(" The queue is empty cannot delete Error\n");
		exit(0);
	}
	*value = (*front)->data;
	*priority = (*front)->priority;
	temp = *front;
	*front = (*front)->link;
	if (*rear == temp)
		*rear = (*rear)->link;
	free(temp);
}

int main()
{
	struct node *front = NULL, *rear = NULL;
	int n, value, priority;
	do
	{
		do
		{
			printf("Enter the element to be inserted and its priority\n");
			scanf("%d %d", &value, &priority);
			insert(&front, &rear, value, priority);
			printf("Enter 1 to continue\n");
			scanf("%d", &n);
		} while (n == 1);

		printf("Enter 1 to delete an element\n");
		scanf("%d", &n);
		while (n == 1)
		{
			deleteD(&front, &rear, &value, &priority);
			printf("The value deleted is %d \n and its priority is %d \n",value,priority);
			printf("Enter 1 to delete an element\n");
			scanf("%d", &n);
		}
		printf("Enter 1 to delete an element\n");
		scanf("%d", &n);
	} while (n == 1);
	getchar();
	return 0;
}